Article ID Journal Published Year Pages File Type
439115 Theoretical Computer Science 2009 10 Pages PDF
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