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

DOI10.1016/0304-3975(83)90038-5MaRDI QIDQ793017zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Improving the classification of complexities
• Reversal Complexity Classes for Alternating Turing Machines
• Simple sentences that are hard to decide
• scientific article; zbMATH DE number 3868618
• SOFSEM 2004: Theory and Practice of Computer Science

Cites work

• scientific article; zbMATH DE number 3685448 (Why is no real title available?)
• scientific article; zbMATH DE number 3767637 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• Alternation
• Complexity of Boolean algebras
• On Languages Accepted in Polynomial Time
• On time-space classes and their relation to the theory of real addition
• The complexity of logical theories
• The computational complexity of logical theories
• The polynomial-time hierarchy

Cited in

(8)

• The complexity of almost linear diophantine problems
• Computational complexity of logical theories of one successor and another unary function
• Simple sentences that are hard to decide
• On the complexity of queries in the logical data model
• scientific article; zbMATH DE number 3995646 (Why is no real title available?)
• The role of rudimentary relations in complexity theory
• Complexity of logical theories involving coprimality
• A uniform method for proving lower bounds on the computational complexity of logical theories

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

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