Halting and equivalence of program schemes in models of arbitrary theories

DOI10.1007/978-3-642-15025-8_22MaRDI QIDQ3586015zbMATH OpenOpenAlexFDO

Authors Dexter Kozen

Publication date 3 September 2010

Published in Fields of Logic and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15025-8_22

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70) Other Turing degree structures (03D28) Turing machines and related notions (03D10)

Recommendations

• scientific article; zbMATH DE number 2090017
• Program schemes with constants
• scientific article; zbMATH DE number 862230
• Publication:3469081
• Well-structured program equivalence is highly undecidable

Cites work

• scientific article; zbMATH DE number 3550181 (Why is no real title available?)
• scientific article; zbMATH DE number 1556014 (Why is no real title available?)
• A programming language for the inductive sets, and applications
• The computational complexity of logical theories

Cited in

(6)

• scientific article; zbMATH DE number 5827855 (Why is no real title available?)
• The problem of equivalence in commutative s-models for programs
• Axiomatization of if-then-else over possibly non-halting programs and tests
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• scientific article; zbMATH DE number 3898846 (Why is no real title available?)
• scientific article; zbMATH DE number 2090017 (Why is no real title available?)

This page was built for publication: Halting and equivalence of program schemes in models of arbitrary theories

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