Finitary PCF is not decidable
From MaRDI portal
Recommendations
- Unary PCF is decidable
- Decision algorithms for checking definability of order-2 finitary PCF
- Decidability and undecidability of marked PCP
- A decidable variety that is finitely undecidable
- A sufficient condition for finite decidability
- Profiniteness in finitely generated varieties is undecidable
- Decidability of finite forcing companion
- A decidable subclass of finitary programs
- TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
Cites work
- Decidability of all minimal models
- Extensions to type systems can preserve operational equivalences
- Full abstraction for PCF
- Fully abstract models of typed \(\lambda\)-calculi
- scientific article; zbMATH DE number 431771 (Why is no real title available?)
- scientific article; zbMATH DE number 1231510 (Why is no real title available?)
- scientific article; zbMATH DE number 512783 (Why is no real title available?)
- Kripke logical relations and PCF
- LCF considered as a programming language
- Logical relations and the typed λ-calculus
- On full abstraction for PCF: I, II and III
- Polymorphic rewriting conserves algebraic confluence
- Unary PCF is decidable
Cited in
(23)- Operational domain theory and topology of sequential programming languages
- Natural non-dcpo domains and f-spaces
- Unary PCF is decidable
- Decidability of behavioural equivalence in unary PCF
- Relative definability of boolean functions via hypergraphs
- The sequentially realizable functionals
- Full abstraction for PCF
- An approach to deciding the observational equivalence of Algol-like languages
- Decidability and syntactic control of interference
- A relational account of call-by-value sequentiality
- Exploratory functions on nondeterministic strategies, up to lower bisimilarity
- Definability and full abstraction
- Decision algorithms for checking definability of order-2 finitary PCF
- An observationally complete program logic for imperative higher-order functions
- Program equivalence in a simple language with state
- The recursion hierarchy for PCF is strict
- Extensional and intensional semantics of bounded and unbounded nondeterminism
- Computing with Functionals—Computability Theory or Computer Science?
- The far side of the cube. An elementary introduction to game semantics
- Retracing some paths in categorical semantics: from process-propositions-as-types to categorified reals and computers
- Disentangling parallelism and interference in game semantics
- Fully abstract normal form bisimulation for call-by-value PCF
- The extensional ordering of the sequential functionals
This page was built for publication: Finitary PCF is not decidable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958762)
