Parallel and serial hypercoherences
type: Item
instance of: scholarly article
title: Parallel and serial hypercoherences
zbMATH Open document ID: 0949.68097
DOI: 10.1016/S0304-3975(00)00173-0
published in: Theoretical Computer Science
publication date: 2000-10-26T00:00:00Z
review text: It is known that the strongly stable functions which arise in the semantics of PCF can be realized by sequential algorithms, which can be considered as deterministic strategies in games associated to PCF types. Studying the connection between strongly stable functions and sequential algorithms, two dual classes of hypercoherences naturally arise: the parallel and serial hypercoherences. The objects belonging to the intersection of these two classes are in bijective correspondence with the so-called ``serial--parallel'' graphs, that can essentially be considered as games. We show how to associate to any hypercoherence a parallel hypercoherence together with a projection onto the given hypercoherence and present some properties of this construction. Intuitively, it makes explicit the computational time of a hypercoherence.
Mathematics Subject Classification ID: 68Q55
zbMATH DE Number: 1521727
zbMATH Keywords: denotational semantics
zbMATH Keywords: sequentiality
zbMATH Keywords: linear logic
author: Thomas Ehrhard
MaRDI profile type: Publication
cites work: Q4490717
cites work: Graph Classes: A Survey
cites work: Fully abstract semantics for observably sequential languages
cites work: On the symmetry of sequentiality
cites work: Localisation and interaction in one dimension
cites work: Projecting sequential algorithms on strongly stable functions
cites work: A relative PCF-definability result for strongly stable functions and some corollaries
cites work: The system \({\mathcal F}\) of variable types, fifteen years later
cites work: Q4842966
cites work: On full abstraction for PCF: I, II and III
cites work: Q4395610
cites work: The sequentially realizable functionals
cites work: Q4501156
cites work: Q4938567
full work available at URL: s0304-3975(00)00173-0
OpenAlex ID: W2029659108
description: scientific article; zbMATH DE number 1521727