Simple interpretations among complicated theories

DOI10.1016/0020-0190(90)90051-XzbMath0712.03006MaRDI QIDQ923068

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)

Cites Work

• Unnamed Item
• 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

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