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

DOI10.1016/0304-3975(83)90038-5zbMATH Open0538.03035OpenAlexW1995317845MaRDI QIDQ793017FDOQ793017

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

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

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)

Cites Work

• Alternation
• Title not available (Why is that?)
• The polynomial-time hierarchy
• Complexity of Boolean algebras
• The complexity of logical theories
• The computational complexity of logical theories
• Title not available (Why is that?)
• On time-space classes and their relation to the theory of real addition
• On Languages Accepted in Polynomial Time
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

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

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)