Technical Reports
The report FIMU-RS-99-02
Complexity Issues of the Pattern Equations in Idempotent Semigroups
by Ondøej Klíma, Jiøí Srba, August 1999, 14 pages.
FIMU-RS-99-02. Available as Postscript, PDF.
Abstract:
A pattern equation is a word equation of the form X=A where X is a sequence of variables and A is a sequence of constants. The problem whether X=A has a solution in a free idempotent semigroup (free band) is shown to be NP--complete.
Responsible contact:
vedaXDjbU2LSW@fiQ1T5fpnNE.muni8CVI=SRv5.cz
Please install a newer browser for this site to function properly.