A note on the expressibility problem for modal logics and star-free regular expressions

DOI10.1016/j.ipl.2009.01.012zbMath1197.03021OpenAlexW1965837810MaRDI QIDQ987808

Balder ten Cate

Publication date: 16 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.01.012

zbMATH Keywords

computational complexitymodal logicexpressibilitytemporal logicformal languagesstar-free expressions

Mathematics Subject Classification ID

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)

Cites Work

• Rewriting of regular expressions and regular path queries
• An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on the expressibility problem for modal logics and star-free regular expressions