## A List by Author: Ondřej Klíma

- e-mail:
- klima(a)math.muni.cz

### 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.

### 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.