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

DOI10.1016/J.IPL.2009.01.012MaRDI QIDQ987808zbMATHOpenAlexFDO

Authors 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 complexityformal languagesmodal logictemporal logicexpressibilitystar-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)

Recommendations

• scientific article; zbMATH DE number 1138201
• scientific article; zbMATH DE number 4164803
• Star free expressions over the reals
• Nonexistence of algorithms for recognizing syntactic expressibility in logic calculi. With a foreword by Iu. Reabuhin
• scientific article; zbMATH DE number 3861119

Cites work

• scientific article; zbMATH DE number 1003731 (Why is no real title available?)
• scientific article; zbMATH DE number 2129214 (Why is no real title available?)
• scientific article; zbMATH DE number 3861119 (Why is no real title available?)
• An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• Nonexistence of algorithms for recognizing syntactic expressibility in logic calculi. With a foreword by Iu. Reabuhin
• Rewriting of regular expressions and regular path queries
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

Cited in

(1)

• scientific article; zbMATH DE number 1962787 (Why is no real title available?)

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

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