A note on the expressibility problem for modal logics and star-free regular expressions |
| |
Authors: | Balder ten Cate |
| |
Affiliation: | University of Amsterdam, Informatics Institute, Kruislaan 403, Amsterdam, the Netherlands |
| |
Abstract: | The purpose of this note is to (i) raise attention for an interesting type of decision problem for logics, known under different names such as the expressibility problem and the uniform clone membership problem, (ii) disseminate a remarkable and powerful negative result of M.F. Ra?ǎ from the 1980s that seems to have escaped attention of many researchers, and (iii) show, with the help of Ra?ǎ's theorem, that the problem is undecidable for star-free regular expressions.In Section 1 we introduce the expressibility problem, taking Boolean formulas as an example. In Section 2, we present, and improve upon, Ra?ǎ's theorem for transitive modal logics. In Section 3, we derive, as a consequence of Ra?ǎ's theorem, the undecidability of the expressibility problem for star-free regular expressions. Finally, we conclude in Section 4 with some open questions. |
| |
Keywords: | Expressibility Modal logic Temporal logic Star-free expressions Formal languages Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|