The Complexity of Regularity in Grammar Logics and Related Modal Logics

DOI10.1093/logcom/11.6.933zbMath1002.03018MaRDI QIDQ4529491

Stéphane P. Demri

Publication date: 24 July 2002

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/logcom/11.6.933

zbMATH Keywords

computational complexity; modal logic; decidability; regular language; finite automaton; multimodal logic; formal grammar; modal reduction principle; regular grammar logic

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

03B45: Modal logic (including the logic of norms)

03D05: Automata and formal grammars in connection with logical questions

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

68Q42: Grammars and rewriting systems

Related Items

A Tableau Calculus for Regular Grammar Logics with Converse, Modal Logics with Hard Diamond-Free Fragments, An Extension of Complex Role Inclusion Axioms in the Description Logic $\mathcal{SROIQ}$, ExpTime tableau decision procedures for regular grammar logics with converse, Decidability of SHIQ with complex role inclusion axioms, Deciding regular grammar logics with converse through first-order logic, On Hierarchical Task Networks, Analytic Cut-Free Tableaux for Regular Modal Logics of Agent Beliefs