The Complexity of Regularity in Grammar Logics and Related Modal Logics

DOI10.1093/LOGCOM/11.6.933zbMATH Open1002.03018OpenAlexW1970040536MaRDI QIDQ4529491FDOQ4529491

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

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

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)

Cited In (13)

• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

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)