Ondřej Klíma
 

List of publications:
1) I.Černá, O.Klíma, J.Srba. Pattern Equations and Equations
with Stuttering. In SOFSEM'99: Theory and Practise of Informatics. Heidelberg:Springer, 1999., 369-378. LNCS 1725 (online )

2) O. Klíma. On the solvability of equations in semigroups with $x^r=x$.
Contributions to General Algebra 12, Proc. of Vienna Conf., June 3--6, 1999, Verlag Johannes Heyn, Klagenfurt 2000.

3) O.Klíma, J.Srba.Matching Modulo Associativity and Idempotency is NP--complete.
M.Nielsen, B.Rovan (Eds.): MFCS 2000, LNCS 1893, 246--266, (online )

4) O.Klíma.  Unification Modulo Associativity and Idempotency is NP-complete
K.Diks, W. Rytter(Eds.): MFCS 2002, LNCS 2420, 423--432 (online )

5) O.Klíma, P.Tesson and D.Thérien. Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups
  Theory of Computing Systems( online ) Vol 40, Num. 3 (2007)

6) O.Klíma, B.Larose and P.Tesson. Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
R.Královič, P.Urzyczyn (Eds.): MFCS 2006, LNCS 4162, 584--595 (online )

7) O.Klíma  Complexity Issues of Checking Identities in Finite Monoids
Semigroup Forum( online) Vol 79, Num 3 (2009) 435-444

8) O.Klíma, L.Polák. On varieties of literally idempotent languages
RAIRO - Theoretical Informatics and Applications Vol. 42 (2008), No. 3, p. 583 - 598 (online )

9) O.Klíma, L.Polák. Splitting conditions for classes of meet automata
Proc. AutoMathA 2007, Palermo, Italy (CD) pdf

10) O.Klíma, L.Polák. Literal Varieties of Languages Induced by Homomorphisms onto Nilpotent Groups,
Proc. LATA 2008, LNCS 5196, 299-310 (online )

11) O.Klíma, L.Polák. Literally idempotent languages and their varieties - two letter case
Proceedings Automata Formal Languages (AFL) 2008, 200-231 pdf
Full version: IJFCS, Vol 21 (5) (2010), 761-780 ( online )

12) O.Klíma, L.Polák. Hierarchies of piecewise testable languages,
Development Language Theory (DLT) 2008, LNCS 5257 (2008) 479-490 ( online )
Full version: IJFCS, Vol 21 (4) (2010), 517-533 ( online )

13) O.Klíma, L.Polák. On varieties of meet automata,
Theoretical Computer Science, 407 (2008) 278-289 ( online )

14) O.Klíma, L.Polák. Polynomial Operators on Classes of Regular Languages,
Algebraic Informatics (CAI) 2009, LNCS 5725, 260-277 ( online )

15) J.Almeida, O.Klíma. A counterexample to some conjectures concerning concatenation hierarchies,
Information Processing Letters, Vol 110 (2009) 4-7 ( online )

16) J.Almeida, O.Klíma. New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages,
Discrete Mathematics and Theoretical Computer Science, Vol 12 (2010), No 4 (Special issue - Authomatha 2009) 41-58 ( online )

17) O.Klíma, L.Polák. On Schützenberger products of semirings,
Development Language Theory (DLT) 2010, LNCS 6224 (2010), 279-290 ( online )

18) O.Klíma, L.Polák. Descriptional Complexity of the Languages KaL: Automata, Monoids and Varieties,
DCFS 2010, EPTCS 31 (2010) 130-138 (online )

19) O.Klíma, M.Korbelář, L.Polák. Rewriting in Varieties of Idempotent Semigroups,
Algebraic Informatics (CAI) 2011, LNCS 6742, 185-200 ( online )

20) O.Klíma, L.Polák. On Biautomata,
Proceedings Non-Classical Models of Automata and Applications (NCMA) 2011, (preprint)
Full version: RAIRO - Theor. Inf. and Applic., 46 (4) (2012), 573-592 ( online)

21) O.Klíma. Piecewise Testable Languages via Combinatorics on Words
Proceedings WORDS'09 - preprint
Full version: Discrete Mathematics, 311 (20) (2011), 2124-2127 ( online)

22) O.Klíma, L.Polák. Subhierarchies of the Second Level in the Straubing-Thrien Hierarchy,
International Journal of Algebra and Computation, 21, 7, (2011) 1195-1215, (preprint)

23) O.Klíma, L.Polák. Identity Problems, Solvability of Equations and Unification in Varieties of Semigroups Related to Varieties of Groups,
Proceedings of Algebraic Foundations in Computer Science 2011, LNCS 7020, 214-227 ( online )

24) O.Klíma  Identity checking problem for transformation monoids
Semigroup Forum, Vol. 84, Num. 3 (2012), 487-498 (online)

25) O.Klíma, L.Polák. Biautomata for k-Piecewise Testable Languages,
Proceedings of DLT 2012, LNCS 7410, 344-355 ( online )
Preliminary version with appendix

26) G. Jirásková, O.Klíma. Descriptional Complexity of Biautomata,
Proceedings of DCFS 2012, LNCS 7386, 196-208 ( online )

27) O.Klíma, L.Polák. Alternative Automata Characterization of Piecewise Testable Languages,
Proceedings of DLT 2013, LNCS 7907, 289-300 ( online )

28) J.Almeida, O.Klíma. On the Irreducibility of Pseudovarieties of Semigroups
Journal of Pure and Applied Algebra, Vol. 220, Issue 4 (2016), 1517–1524, doi:10.1016/j.jpaa.2015.09.015 ( preprint , journal - online)

29) O.Klíma. On Varieties of Automata Enriched with an Algebraic Structure (Extended Abstract),
AFL 2014, EPTCS 151 (2014) 49-54 (online )

30) J.Almeida, A.Cano, O.Klíma, J.-É.Pin. On Fixed Points of the Lower Set Operator
International Journal of Algebra and Computation, 25 (1-2), (2015) 259-292 ( online )

31) J.Almeida, J.Bartoňová, O.Klíma, M.Kunc. On Decidability of Intermediate Levels of Concatenation Hierarchies.
Proceedings of DLT 2015, LNCS 9168, 58-70 ( online ) Best Paper Award DLT 2015

32) J.Almeida, O.Klíma: Reducibility versus definability for pseudovarieties of semigroups.
International Journal of Algebra and Computation, 26 (7), (2016) 1483-1495 ( online )

33) J.Almeida, O.Klíma, M.Kunc: The omega-inequality problem for concatenation hierarchies of star-free languages.
Forum Mathematicum - accepted, (2017) ( online )

Submitted:

 34) J.Almeida, O.Klíma: Representations of relatively free profinite semigroups, irreducibility, and order primitivity

 35) O.Klíma, M.Kunc, L.Polák: Deciding k-piecewise testability

 36) O.Klíma, L.Polák: Syntactic Structures of Regular Languages
  CAI 2017 paper

 37) O.Klíma, L.Polák: On varieties of ordered automata

 38) J.Almeida, O.Klíma: Towards a pseudoequational proof theory

Preliminary versions, notes:

 O.Klíma: Complexity Issues of Checking Identities in Finite Monoids
(preliminary version of paper 7), Prop. 6,7 are not contained in final version of 7)

 O.Klíma: Complexity of Checking Identities in Monoids of Partial Transformations
(part is published as paper 24)

Slides:

  O.Klíma: On Varieties of Automata Enriched with an Algebraic Structure (AFL 2014) - pdf
Seznámení se základy lineární algebry a analytické geometrie.Introduction to linear algebra and analytical geometry.