i) Publikace rozpracované v predchozím období a dokončené v roce 2009.



Tyto publikace jsou zmíněny též v předchozím grantu (GA201/06/0936).

[1] J. Karhumaki, M. Kunc a A. Okhotin, Computational power of two stacks with restricted
communication, přijato v Information and Computation.

[2] O. Klíma a L. Polák, Literally idempotent languages and their varieties - two letter case,
přijato v International Journal of Foundations of Computer Science.

[3] O. Klíma a L. Polák, Polynomial operators on classes of regular languages, v Proceedings
International Conference on Algebraic Informatics CAI 2009, Springer LNCS 5725, 260 - 277.

[4] O. Klíma a L. Polak, Hierarchies of piecewise testable languages and related languages,
zasláno do International Journal of Foundations of Computer Science.

see Grant-1

ii) Publikace zpracované v roce 2009.

[5] J. Almeida a O. Klíma, A counterexample to a conjecture concerning concatenation hierarchies,
Information Processing Letters 110, 4 - 7 (2009).

[6] J. Almeida a O. Klíma, New decidable upper bound of the second level in the Straubing-
Thérien concatenation hierarchy of star-free languages, zasláno do Discrete Mathematics and
Theoretical Computer Science (speciální vydání věnované konferenci AutoMathA 2009).

[7] O. Klíma, Piecewise testable languages via combinatorics on words, sborník z konference
WORDS (na CD), časopisecká verze zaslána do časopisu Discrete Mathematics.

see www.math.muni.cz/~klima