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

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.