Alternation and the Ackermann case of the decision problem
From MaRDI portal
Publication:1159190
zbMath0474.03005MaRDI QIDQ1159190
Publication date: 1981
Published in: L'Enseignement Mathématique. 2e Série (Search for Journal in Brave)
universal quantificationalternating Turing machinesdeterministic lower time boundexistential quantificationsatisfiability of formulas of the Ackermann prefix class
Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Related Items (4)
Alternation and \(\omega\)-type Turing acceptors ⋮ Alternating automatic register machines ⋮ 0-1 laws and decision problems for fragments of second-order logic ⋮ On reasoning about structural equality in XML: a description logic approach
This page was built for publication: Alternation and the Ackermann case of the decision problem
