Alternation and the Ackermann case of the decision problem

zbMath0474.03005MaRDI QIDQ1159190

Martin Fuerer

Publication date: 1981

Published in: L'Enseignement Mathématique. 2e Série (Search for Journal in Brave)

zbMATH Keywords

universal quantificationalternating Turing machinesdeterministic lower time boundexistential quantificationsatisfiability of formulas of the Ackermann prefix class

Mathematics Subject Classification ID

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