The Complexity of Decomposing Modal and First-Order Theories

DOI10.1145/2699918zbMath1354.03053OpenAlexW2054803027MaRDI QIDQ5892176

Jean Christoph Jung, Stefan Göller, Markus Lohrey

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2699918

zbMATH Keywords

modal logictwo-dimensional modal logicFeferman-Vaught decompositionGaifman's theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20) Basic properties of first-order languages and structures (03C07)

Related Items (1)

Feferman-vaught decompositions for prefix classes of first order logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic uses of the Feferman-Vaught theorem
• The complexity of reasoning about knowledge and time. I: Lower bounds
• Multi-dimensional modal logic
• Many-dimensional modal logics: theory and applications
• Parametrized complexity theory.
• Products, or how to create modal logics of high complexity
• The first order properties of products of algebraic systems
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Complexity of products of modal logics
• On the Decision Problem for Two-Variable First-Order Logic
• Products of modal logics, part 1
• On modal logics betweenK × K × KandS5 × S5 × S5
• On compositionality and its limitations
• Model Theory Makes Formulas Large
• Products of ‘transitive” modal logics
• On direct products of theories
• The Complexity of Decomposing Modal and First-Order Theories

This page was built for publication: The Complexity of Decomposing Modal and First-Order Theories