Informace o projektu
Algebraické metody v teorii automatů a formálních jazyků
- Kód projektu
- GA201/06/0936
- Období řešení
- 1/2006 - 12/2008
- Investor / Programový rámec / typ projektu
-
Grantová agentura ČR
- Standardní projekty
- Fakulta / Pracoviště MU
-
Přírodovědecká fakulta
- doc. RNDr. Libor Polák, CSc.
- doc. Mgr. Ondřej Klíma, Ph.D.
- doc. Mgr. Michal Kunc, Ph.D.
- Klíčová slova
- automaty, regulární jazyky, variety, polookruhy, nekonečná slova, stopy
Projekt je zaměřen na rozvoj algebraických metod v teorii formálních jazyků.
Zejména budeme dále zkoumat třídy syntaktických struktur regulárních jazyků,
jako (uspořádaných) sytaktických monoidů, syntaktických polookruhů,
syntaktických homomorfismů, syntaktických polookruhů s obrazem jazyka, atd. s cílem efektivní charakterizace přísluąnosti k důleľitým třídám jazyků. Budeme
téľ uvaľovat grafovou strukturu kanonických automatů. Chystáme se pokračovat v naąem studiu implicitních jazykových rovnic. Hlavně se zaměříme na hledání
společných rysů různorodých výsledků zajią»ujících regularitu řeąení s cílem
fomulace jednotné teorie. Budeme se téľ věnovat návrhům algoritmů pro výpočet
maximálních řeąení v těch případech, kdy jsou tato regulární. Téľ se budeme
zabývat zobecněními klasických jazyků konečných slov na takzvané stromové
jazyky, jazyky nekonečných slov a jazyky stop. V rámci projektu budeme
pokračovat v naąí ąiroké mezinárodní spolupráci. Výsledky budou prezentovány
na prestiľních konferencích a publikovány v uznávaných časopisech.
Publikace
Počet publikací: 12
2009
-
Complexity issues of checking identities in finite monoids
Semigroup Forum, rok: 2009, ročník: 79, vydání: 3
2008
-
Hierarchies of piecewise testable languages
Developments in Language Theory, rok: 2008
-
Literal varieties of languages induced by homomorphisms onto nilpotent groups
Language and Automata Theory and Applications, rok: 2008
-
Literally idempotent languages and their varieties - two letter case
Automata and Formal Languages, rok: 2008
-
On varieties of literally idempotent languages
RAIRO - Theoretical Informatics and Applications, rok: 2008, ročník: 42, vydání: 3
-
On varieties of meet automata
Theoretical Computer Science, rok: 2008, ročník: 407, vydání: 1-3
2007
-
Hierarchies of piecewise testable languages
Rok: 2007, druh: Další prezentace na konferencích
-
On classes of meet automata
Rok: 2007, druh: Další prezentace na konferencích
-
Splitting conditions for classes of meet automata
Proceedings AutoMathA 2007, June 18-22, 2007, Palermo, Italy (CD), rok: 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, rok: 2007