scientific article; zbMATH DE number 3685448

MaRDI QIDQ3880807zbMATH OpenFDO

Authors Klaus Fleischmann, Dirk Siefkes, Bernd Mahr

Publication date 1977

zbMATH Keywords

bounded concatenation theorybounded word theorylogical theorieslower complexity bounds

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Cited in

(6)

• Complexity of Boolean algebras
• On time-space classes and their relation to the theory of real addition
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• The recognition complexity of decidable theories
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
• A uniform method for proving lower bounds on the computational complexity of logical theories

This page was built for publication:

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