A polynomial space construction of tree-like models for logics with local chains of modal connectives

DOI10.1016/S0304-3975(02)00082-8zbMath1028.68064MaRDI QIDQ1399966

Stéphane P. Demri

Publication date: 30 July 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

modal logicComputational complexityagreementlocalLA-logicsLadner-like algorithmlocal agreement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Related Items

Complexity of modal logics with Presburger constraints

Uses Software

• KL-ONE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Attributive concept descriptions with complements
• DAL -- a logic for data analysis
• Automata-theoretic techniques for modal logics of programs
• A class of decidable information logics
• A guide to completeness and complexity for modal logics of knowledge and belief
• The polynomial-time hierarchy
• Propositional dynamic logic of regular programs
• The computational complexity of the satisfiability of modal Horn clauses for modal propositional logics
• Reasoning about infinite computations
• The complexity of concept languages
• The price of universality
• The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
• Single step tableaux for modal logics. Computational properties, complexity and methodology
• Using the Universal Modality: Gains and Questions
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• A hierarchy of modal logics with relative accessibility relations
• On model checking for the \(\mu\)-calculus and its fragments
• Incomplete information: Structure, inference, complexity
• An overview of tableau algorithms for description logics