Parallel and serial hypercoherences

DOI10.1016/S0304-3975(00)00173-0MaRDI QIDQ1583243zbMATH OpenOpenAlexFDO

Authors Thomas Ehrhard

Publication date 26 October 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(00)00173-0

zbMATH Keywords

denotational semanticslinear logicsequentiality

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55)

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.

Recommendations

• Sequential algorithms and strongly stable functions
• Towards a theory of parallel algorithms on concrete data structures
• Projecting sequential algorithms on strongly stable functions
• Automata, Languages and Programming
• Foundations of Software Science and Computation Structures

Cites work

• A relative PCF-definability result for strongly stable functions and some corollaries
• Fully abstract semantics for observably sequential languages
• Graph Classes: A Survey
• scientific article; zbMATH DE number 1163983 (Why is no real title available?)
• scientific article; zbMATH DE number 1479606 (Why is no real title available?)
• scientific article; zbMATH DE number 1499102 (Why is no real title available?)
• scientific article; zbMATH DE number 786485 (Why is no real title available?)
• scientific article; zbMATH DE number 1405588 (Why is no real title available?)
• Localisation and interaction in one dimension
• On full abstraction for PCF: I, II and III
• On the symmetry of sequentiality
• Projecting sequential algorithms on strongly stable functions
• The sequentially realizable functionals
• The system \({\mathcal F}\) of variable types, fifteen years later

Cited in

(8)

• Degrees of parallelism in the continuous type hierarchy
• Relative definability of boolean functions via hypergraphs
• Comparing hierarchies of types in models of linear logic
• Sequential algorithms and strongly stable functions
• Non-uniform (hyper/multi)coherence spaces
• scientific article; zbMATH DE number 7561616 (Why is no real title available?)
• Foundations of Software Science and Computation Structures
• Automata, Languages and Programming

This page was built for publication: Parallel and serial hypercoherences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583243)