You are here: Faculty of Informatics » Research and Development » Technical Reports » FIMU-RS-99-02

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.