The Complexity of Regularity in Grammar Logics and Related Modal Logics

DOI10.1093/logcom/11.6.933zbMath1002.03018OpenAlexW1970040536MaRDI 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 complexitymodal logicdecidabilityregular languagefinite automatonmultimodal logicformal grammarmodal reduction principleregular grammar logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Modal logic (including the logic of norms) (03B45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42)

Related Items (8)

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

This page was built for publication: The Complexity of Regularity in Grammar Logics and Related Modal Logics