Technical Reports
The report FIMU-RS-99-01
On the Pattern Equations
by Ivana Černá, Ondřej Klíma, Jiří Srba, This is a full version of the paper accepted to SOFSEM`99. July 1999, 11 pages.
FIMU-RS-99-01. Available as Postscript, PDF.
Abstract:
Word equation in a special form X=A, where X is a sequence of variables and A is a sequence of constants, is considered. The problem whether X=A has a solution over a free monoid (PATTERN EQUATION problem) is shown to be NP--complete. It is also shown that disjunction of a special type equation systems and conjunction of the general ones can be eliminated. Finally, the case of stuttering equations where the word identity is read modulo xx=x is mentioned.
Responsible contact:
vedaXDjbU2LSW@fiQ1T5fpnNE.muni8CVI=SRv5.cz
Please install a newer browser for this site to function properly.