Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
439115 | Theoretical Computer Science | 2009 | 10 Pages |
Abstract
We consider equations on the monoid of factorial languages on the binary alphabet. We use the notion of a canonical decomposition of a factorial language and previous results by Avgustinovich and the author to solve several simple equations on binary factorial languages including Xn=Yn, the commutation equation XY=YX and the conjugacy equation XZ=ZY. At the end of the paper, we discuss the difficulties hindering the reduction of equations on factorial languages to equations on words and the extension of the alphabet considered.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics