The expressibility of languages and relations by word equations

Citation
J. Karhumaki et al., The expressibility of languages and relations by word equations, J ACM, 47(3), 2000, pp. 483-505
Citations number
18
Categorie Soggetti
Computer Science & Engineering
Journal title
Volume
47
Issue
3
Year of publication
2000
Pages
483 - 505
Database
ISI
SICI code
Abstract
Classically, several properties and relations of words, such as "being a po wer of the same word", can be expressed by using word equations. This paper is devoted to a general study of the expressive power of word equations. A s main results we prove theorems which allow us to show that certain proper ties of words are not expressible as components of solutions of word equati ons. In particular, "the primitiveness" and "the equal length" are such pro perties, as well as being "any word over a proper subalphabet".