Simple interpretations among complicated theories

DOI10.1016/0020-0190(90)90051-XMaRDI QIDQ923068zbMATH OpenFDO

Authors Erich Grädel

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

number of quantifier alternationscomplexity of quantifier bounded fragmentsdecision complexityexistential monadic second order theory of finite linear ordersexponential upper bounds of space complexityextensions of Presburger arithmeticfirst order theories of m-ary trees with m successorsformal theoriesquantified propositional temporal logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1136071
• The complexity of propositional linear temporal logics
• On the expressivity and complexity of quantitative branching-time temporal logics
• scientific article; zbMATH DE number 2084388
• Temporal logics over linear time domains are in PSPACE

Cites work

• scientific article; zbMATH DE number 3562520 (Why is no real title available?)
• A uniform method for proving lower bounds on the computational complexity of logical theories
• The complementation problem for Büchi automata with applications to temporal logic
• The complexity of propositional linear temporal logics

Cited in

(2)

• An example of a new simple theory
• Simple theories

This page was built for publication: Simple interpretations among complicated theories

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