Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
We consider several open problems of Karhumäki, Mignosi and Plandowski, cf. [KMP], con-cerning 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 negatively 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].
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
109--118
Opis fizyczny
bibliogr. 15 poz.
Twórcy
autor
- Turku Centre for Computer Science TUCS, FIN-20520 Turku, Finland, lucili@cs.utu.fi
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS1-0007-0033