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 complexityregular languagedecidabilitymodal logicmultimodal logicfinite automatonformal grammarmodal reduction principleregular grammar logic

Mathematics Subject Classification ID

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

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

(13)

• scientific article; zbMATH DE number 1189095 (Why is no real title available?)
• Constructing Finite Least Kripke Models for Positive Logic Programs in Serial Regular Grammar Logics
• Modal logics with hard diamond-free fragments
• Deciding regular grammar logics with converse through first-order logic
• Decidability of SHIQ with complex role inclusion axioms
• An extension of complex role inclusion axioms in the description logic \(\mathcal{SROIQ}\)
• Analytic Cut-Free Tableaux for Regular Modal Logics of Agent Beliefs
• On hierarchical task networks
• scientific article; zbMATH DE number 559034 (Why is no real title available?)
• A Tractable Rule Language in the Modal and Description Logic that Combines CPDL with Regular Grammar Logic
• A Tableau Calculus for Regular Grammar Logics with Converse
• ExpTime tableau decision procedures for regular grammar logics with converse
• scientific article; zbMATH DE number 1989649 (Why is no real title available?)

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)