Practical decidability

DOI10.1016/S0022-0000(75)80060-2zbMath0329.02020OpenAlexW2911396724MaRDI QIDQ1227003

Andrzej Ehrenfeucht

Publication date: 1975

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(75)80060-2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10) Algorithms in computer science (68W99)

Related Items (6)

On k-stable functions ⋮ Classifying the computational complexity of problems ⋮ On the complexity of 2-output Boolean networks ⋮ Compositional complexity of Boolean functions ⋮ Interpolation of functions over a measure space and conjectures about memory ⋮ Natural limitations of decision procedures for arithmetic with bounded quantifiers

Cites Work

• Interpolation of functions over a measure space and conjectures about memory
• On boolean functions and connected sets
• On the Forms of the Predicates in the Theory of Constructive Ordinals
• Unnamed Item
• Unnamed Item

This page was built for publication: Practical decidability