Sequential algorithms on concrete data structures

DOI10.1016/S0304-3975(82)80002-9zbMath0497.68012OpenAlexW1978840985MaRDI QIDQ1170880

Pierre-Louis Curien, Gérard Berry

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(82)80002-9

zbMATH Keywords

concrete data structurescartesian closed categoryrecursive domain equationssequential denotational semanticssequential programming languages

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Data structures (68P05) Closed categories (closed monoidal and Cartesian closed categories, etc.) (18D15) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (58)

Comparing hierarchies of types in models of linear logic ⋮ On the symmetry of sequentiality ⋮ Sequential functions on indexed domains and full abstraction for a sub-language of PCF ⋮ Another approach to sequentiality: Kleene's unimonotone functions ⋮ On dialogue games and graph games ⋮ Prime algebraicity ⋮ Synchronization trees ⋮ Universal domains and the amalgamation property ⋮ On Church's formal theory of functions and functionals. The \(\lambda\)- calculus: Connections to higher type recursion theory, proof theory, category theory ⋮ Game theoretic analysis of call-by-value computation ⋮ Projecting sequential algorithms on strongly stable functions ⋮ Event structures and domains ⋮ Full abstraction and the Context Lemma (preliminary report) ⋮ Stable bistructure models of PCF ⋮ Decidability results for primitive recursive algorithms ⋮ Continuous functions and parallel algorithms on concrete data structures ⋮ Interpreting Localized Computational Effects Using Operators of Higher Type ⋮ Game semantics of Martin-Löf type theory ⋮ Resource modalities in tensor logic ⋮ Non-deterministic information systems and their domains ⋮ An algebraic approach to stable domains ⋮ Sequential algorithms for unbounded nondeterminism ⋮ Game-theoretic analysis of call-by-value computation ⋮ Sequential algorithms on concrete data structures ⋮ From Qualitative to Quantitative Semantics ⋮ Unnamed Item ⋮ Universal homogeneous event structures and domains ⋮ What is a universal higher-order programming language? ⋮ Unnamed Item ⋮ Towards a theory of parallel algorithms on concrete data structures ⋮ Symmetry and Interactivity in Programming ⋮ I-categories as a framework for solving domain equations ⋮ Preface to the special volume ⋮ Typed event structures and the linear \(\pi \)-calculus ⋮ Unnamed Item ⋮ On the reification of semantic linearity ⋮ Probabilistic coherence spaces as a model of higher-order probabilistic computation ⋮ Axiomatization and characterization of BSP algorithms ⋮ A stable programming language ⋮ Domains via graphs ⋮ On the asymptotic behaviour of primitive recursive algorithms ⋮ Some Programming Languages Suggested by Game Models (Extended Abstract) ⋮ An Algebraic Account of References in Game Semantics ⋮ Non-uniform (hyper/multi)coherence spaces ⋮ Nondeterminism and Observable Sequentiality ⋮ Recursive domain equations for concrete data structure ⋮ On the logic of unification ⋮ A game-semantic model of computation ⋮ Non-Uniform Hypercoherences ⋮ Locally Boolean domains ⋮ Sequential algorithms and strongly stable functions ⋮ The sequentially realizable functionals ⋮ Full abstraction for PCF ⋮ Definability and Full Abstraction ⋮ Historical introduction to ``Concrete domains by G. Kahn and G. D. Plotkin ⋮ Probabilistic π-Calculus and Event Structures ⋮ Redexes are stable in the λ-calculus ⋮ Information categories

Uses Software

• LCF

Cites Work

• Petri nets, event structures and domains. I
• The lambda calculus, its syntax and semantics
• Sequential algorithms on concrete data structures
• An algebraic interpretation of the \(\lambda\beta K\)-calculus; and an application of a labelled \(\lambda\)-calculus
• LCF considered as a programming language
• Fully abstract models of typed \(\lambda\)-calculi
• The Category-Theoretic Solution of Recursive Domain Equations
• The Relation between Computational and Denotational Properties for Scott’s ${\text{D}}_\infty $-Models of the Lambda-Calculus
• Minimal and Optimal Computations of Recursive Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sequential algorithms on concrete data structures