Subwords and Power-Free Words are not Expressible by Word Equations

We consider several open problems of Karhumäki, Mignosi, and Plandowski, cf. [KMP], concerning the expressibility of languages and relations as solutions of word equations. We show first that the (scattered) subword relation is not expressible. Then, we consider the set of k-power-free finite words and solve it negativelly for all nontrivial integer values of k. Finally, we consider the Fibonacci finite words. We do not solve the problem of the …