**Area of interest
**

**Over
the last years
the main area of my interest was semigroup theory
and its applications to theoretical computer science.
I have studied complexity of equational
unification problem which is solving of equations in
free algebras in certain varieties.
Further I have dealt with solving of equations
and checking identities in finite semigroups.
In future I plan to work (in cooperation with M. Kunc and our
L. Polák (my former PhD supervisor))
also in the area of automata theory and algebraic
theory of formal languages.
**

Main results

**We showed that the unification
problem for the theory of one
associative and idempotent binary function symbol (AI-unification),
i.e. the
problem of solving systems of equations in free idempotent semigroups,
is
NP-complete. [MFCS'02]
**

**We also described the complexity
of the unification problems for all
equational theories of a binary function symbol that consist of
associativity and idempotency together with any set of additional
identities. We showed that the unification problem for such
a theory is decidable in polynomial time if the function symbol
satisfies
the identity $xyzx=xzyx$ and it is NP-complete otherwise.
[to appear, IJAC]
**

**In cooperation with P. Tesson and
D. Thérien
we established certain dichotomy results for the problem of solving
of equations in fixed finite semigroups.
(submitted, TOCS)
**

**We prove that the problem of
determining whether a given identity holds in 6-element Brandt monoid
is co-NPcomplete.
(unpublished)
**

**Grant participation
**

**1)
grant 201/06/0936 of the
Grant Agency of the Czech Republic,
Name: Algebraic Methods in Automata and Formal Language Theory,
Investigator: L. Polák, Duration: 2006-2008.
**

**2) project MSM 143100009 of the
Ministry of Education of the Czech Republic.
Name: Mathematical Structures and Physical Applications,
Leader: J. Rosický, Duration: 2005-2011.
**

**3)
project 1M0021620808 of the
Ministry of Education of the Czech Republic.
Name: National Research Center
"Institute for Theoretical Computer Science",
Leader: J. Nešetřil, Duration: 2005-2008.
**

4) Our group (O. Klíma, M. Kunc, L. Polák) is going to collaborate in the program AutoMathA of ESF from 2005.

**Previous grant participation
**

**1) grant 201/01/0323 of the
Grant Agency of the Czech Republic,
Name:Equational logic of semigroups and applications
Investigator: L. Polák, Duration: 2001-2003.
**

**2) project MSM 143100009 of the
Ministry of Education of the Czech Republic.
Name: Mathematical Structures of Algebra and Geometry
Leader: J. Rosický, Duration: 1999-2004.
**