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

DOI10.1016/J.IPL.2009.01.012zbMATH Open1197.03021OpenAlexW1965837810MaRDI QIDQ987808FDOQ987808

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

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

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)

Cites Work

• Title not available (Why is that?)
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Rewriting of regular expressions and regular path queries
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonexistence of algorithms for recognizing syntactic expressibility in logic calculi. With a foreword by Iu. Reabuhin

Cited In (1)

• Title not available (Why is that?)

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)