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, 30 (3), (2018) 663-679 ( online )

34) J. Almeida, O. Klíma: Towards a pseudoequational proof theory
Portugal. Math., 75 (2), (2018) 79–119 ( online ) DOI 10.4171/PM/2012, Preprint

35) O. Klíma, L. Polák: Syntactic Structures of Regular Languages.
preliminary version CAI 2017 , full version TCS, 800 (2019) 125-141

36) O. Klíma, L. Polák: On varieties of ordered automata.
Proceedings of LATA 2019, LNCS 11417, 108-120 ( online )
preliminary and extended version available here

37) G. Jirásková, O. Klíma: Deterministic biautomata and subclasses of deterministic linear languages
Proceedings of LATA 2019, LNCS 11417, 315-327 ( online )

38) J. Almeida, O. Klíma: On the insertion of n-powers
Discrete Mathematics & Theoretical Computer Science, February 5, 2019, Vol. 21 no. 3, ( online ), Preprint

39) J. Almeida, O. Klíma: Pseudovarieties of ordered completely regular semigroups
Results in Mathematics, June 2019, online , https://doi.org/10.1007/s00025-019-0998-7, Preprint

40) J. Almeida, O. Klíma: Representations of relatively free profinite semigroups, irreducibility, and order primitivity
Trans. Amer. Math. Soc. 373 (2020), (doi.org/10.1090/tran/7951), preprint

41) O. Klíma, P. Kostolányi: Geometrically Closed Positive Varieties of Star-Free Languages
Proceedings of LATA 2020, LNCS 12038, 328–340 (online)

42) O. Klíma, L. Polák: Forbidden patterns for ordered automata
Proceedings of NCMA 2018, extended version: Journal of Automata, Languages and Combinatorics 25 (2020) 2–3, 141 – 169 (online)

43) J. Kaďourek, O. Klíma: Obituary - Libor Polák (1950-2020)
Semigroup Forum 102 (2021), 315-321 (online)

44) O. Klíma, P. Kostolányi: Geometrically closed positive varieties of languages (accepted)
Information and Computation 288 (2021) 104709 (online) - extended version of 41

45) G. Jirásková, O. Klíma: On linear languages recognized by deterministic biautomata (accepted)
Information and Computation 286 (2021) 104778 (online) - extended version of 37

46) J. Almeida, O. Klíma: Locally countable pseudovarieties
Publicacions Matemàtiques 67(1) (2023) 127-172 (online), ( preprint )

47) J. Almeida, O. Klíma: Binary patterns in the Prouhet-Thue-Morse sequence
Discrete Mathematics & Theoretical Computer Science (2021) 23(3) (online)

48) O. Klíma, J. Kolegar: Well quasi-orders arising from finite ordered semigroups
Proceedings of DLT 2022, LNCS 13257, 201-212 (online), (preprint)

49) J. Almeida, H. Goulet-Oullet, O. Klíma: What makes a Stone topological algebra profinite
Algebra Universalis 84(1) (2023) art. n. 6 (online) (preprint)

50) J. Almeida, O. Klíma: Profinite congruences and unary algebras (accepted) (preprint)

Submitted:

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

 52) J. Almeida, O. Klíma: Stone pseudovarieties (preprint)

 53) O. Klíma, J. Kolegar: Characterization of ordered semigroups generating well quasi-orders of words

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