Project information
Algebraic Methods in Automata and Formal Language Theory
- Project Identification
- GA201/06/0936
- Project Period
- 1/2006 - 12/2008
- Investor / Pogramme / Project type
-
Czech Science Foundation
- Standard Projects
- MU Faculty or unit
-
Faculty of Science
- doc. RNDr. Libor Polák, CSc.
- doc. Mgr. Ondřej Klíma, Ph.D.
- doc. Mgr. Michal Kunc, Ph.D.
- Keywords
- automata, regular languages, varieties, semirings, infinite words, traces
The projects developes the algebraic methods in formal language theory.
In particular we will further investiagate the classes of
syntactic structures of a given regular language
like (ordered) syntactic monoids, syntactic semirings, syntactic
homomorphisms, syntactic semirings with the image of the language, etc.
with the goal consisting in effective characterizations of membership
to important classes of languages. We will also consider the graph structures
of the canonical automata.We will also deal with generalizations of the classical languages of finite
words to the so-called tree languages, languages of infinite words
and trace languages.
Within the project we are going to continue our broad international
cooperation.
The results will be presented at prestigious conferencies and acknoledged
journals.
Publications
Total number of publications: 12
2009
-
Complexity issues of checking identities in finite monoids
Semigroup Forum, year: 2009, volume: 79, edition: 3
2008
-
Hierarchies of piecewise testable languages
Developments in Language Theory, year: 2008
-
Literal varieties of languages induced by homomorphisms onto nilpotent groups
Language and Automata Theory and Applications, year: 2008
-
Literally idempotent languages and their varieties - two letter case
Automata and Formal Languages, year: 2008
-
On varieties of literally idempotent languages
RAIRO - Theoretical Informatics and Applications, year: 2008, volume: 42, edition: 3
-
On varieties of meet automata
Theoretical Computer Science, year: 2008, volume: 407, edition: 1-3
2007
-
Hierarchies of piecewise testable languages
Year: 2007, type: Appeared in Conference without Proceedings
-
On classes of meet automata
Year: 2007, type: Appeared in Conference without Proceedings
-
Splitting conditions for classes of meet automata
Proceedings AutoMathA 2007, June 18-22, 2007, Palermo, Italy (CD), year: 2007
-
The simplest language where equivalence of finite substitutions is undecidable
Fundamentals of Computation Theory: 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007. Proceedings, year: 2007