Abstract | ||
---|---|---|
Classically, several properties and relations of words, such as “being a power 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. As main results we prove theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations. In particular, “the primitiveness” and “the equal length” are such properties, as well as being “any word over a proper subalphabet”. |
Year | DOI | Venue |
---|---|---|
1997 | 10.1145/337244.337255 | Journal of the ACM (JACM) |
Keywords | DocType | Volume |
main result,word equation,general study,certain property,expressive power,word equations,equal length,proper subalphabet | Conference | 47 |
Issue | ISSN | Citations |
3 | 0004-5411 | 11 |
PageRank | References | Authors |
0.86 | 8 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Juhani Karhumäki | 1 | 1115 | 152.77 |
Filippo Mignosi | 2 | 569 | 99.71 |
Wojciech Plandowski | 3 | 603 | 47.22 |