Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories

DOI10.1016/0304-3975(83)90038-5zbMath0538.03035OpenAlexW1995317845MaRDI QIDQ793017

Hugo Volger

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90038-5

zbMATH Keywords

alternating Turing machinebounded concatenationcomplexity classdecision problem of first order theories

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10)

Related Items (7)

Computational complexity of logical theories of one successor and another unary function ⋮ A uniform method for proving lower bounds on the computational complexity of logical theories ⋮ On the complexity of queries in the logical data model ⋮ Complexity of logical theories involving coprimality ⋮ The role of rudimentary relations in complexity theory ⋮ The complexity of almost linear diophantine problems ⋮ Simple sentences that are hard to decide

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of Boolean algebras
• On time-space classes and their relation to the theory of real addition
• The complexity of logical theories
• The polynomial-time hierarchy
• The computational complexity of logical theories
• Alternation
• On Languages Accepted in Polynomial Time

This page was built for publication: Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories