The Complexity of Regularity in Grammar Logics and Related Modal Logics
DOI10.1093/logcom/11.6.933zbMath1002.03018MaRDI QIDQ4529491
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
computational complexity; modal logic; decidability; regular language; finite automaton; multimodal logic; formal grammar; modal reduction principle; regular grammar logic
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