×

On the system of word equations \(x^ i_ 1 x^ i_ 2\dots x^ i_ m=y^ i_ 1 y^ i_ 2\dots y^ i_ n\) \((i=1,2,\dots)\) in a free monoid. (English) Zbl 0877.68073

Summary: It is proved that the system of word equation \(x^i_1= y^i_1y^i_2\dots y^i_n\), \(i= 1,2,\dots,\lceil n/2\rceil+1\), has only cyclic solutions. Some sharpenings concerning the cases \(n= 5, 7\) and \(n\geq 9\) are derived as well as results concerning the general system of equations \(x^i_1x^i_2\dots x^i_m= y^i_1y^i_2\dots y^i_n\), \(i=1,2,\dots\;\). Applications to test sets of certain bounded languages are considered.

MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI