The Complexity of Regularity in Grammar Logics and Related Modal Logics

DOI10.1093/LOGCOM/11.6.933MaRDI QIDQ4529491zbMATH OpenOpenAlexFDO

Authors Stéphane 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 complexitydecidabilityfinite automatonformal grammarmodal logicmodal reduction principlemultimodal logicregular grammar logicregular language

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4202248
• scientific article; zbMATH DE number 1989649
• ExpTime tableau decision procedures for regular grammar logics with converse
• Automated Reasoning with Analytic Tableaux and Related Methods
• Constructing Finite Least Kripke Models for Positive Logic Programs in Serial Regular Grammar Logics

Cited in

(14)

• Deciding regular grammar logics with converse through first-order logic
• On hierarchical task networks
• A Tractable Rule Language in the Modal and Description Logic that Combines CPDL with Regular Grammar Logic
• scientific article; zbMATH DE number 4202248 (Why is no real title available?)
• Analytic Cut-Free Tableaux for Regular Modal Logics of Agent Beliefs
• scientific article; zbMATH DE number 1189095 (Why is no real title available?)
• scientific article; zbMATH DE number 559034 (Why is no real title available?)
• scientific article; zbMATH DE number 1989649 (Why is no real title available?)
• A Tableau Calculus for Regular Grammar Logics with Converse
• Modal logics with hard diamond-free fragments
• Constructing Finite Least Kripke Models for Positive Logic Programs in Serial Regular Grammar Logics
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4529491)