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.