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

Article type: Research Article

Authors: Ilie, Lucian

Affiliations: Turku Centre for Computer Science TUCS, FIN-20520 Turku, Finland. e-mail: lucili@cs.utu.fi

Note: [] Research supported by the Academy of Finland, Project 137358. On leave of absence from Faculty of Mathematics, University of Bucharest, Str. Academiei 14, R-70109 Bucharest, Romania. Address for correspondence: Turku Centre for Computer Science TUCS, FIN-20520 Turku, Finland.

Abstract: 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 expressibility of the set of these words but prove that a negative answer (as believed) cannot be given using the tools in [KMP].

Keywords: word equation, subword, power-free, Fibonacci

DOI: 10.3233/FI-1999-381209

Journal: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 109-118, 1999