Simple interpretations among complicated theories

DOI10.1016/0020-0190(90)90051-XzbMATH Open0712.03006MaRDI QIDQ923068FDOQ923068

Authors: Erich Grädel 

Publication date: 1990

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

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

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)

Cites Work

• The complexity of propositional linear temporal logics
• The complementation problem for Büchi automata with applications to temporal logic
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Title not available (Why is that?)

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)