Informace o projektu
Algebraické metody v teorii automatů a formálních jazyků II
- Kód projektu
- GA201/09/1313
- Období řešení
- 1/2009 - 12/2011
- 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, jazykové rovnice
Projekt je zaměřen na rozvoj algebraických metod v teorii formálních jazyků.
Budeme dále zkoumat třídy syntaktických struktur regulárních jazyků, tj.
(uspořádaných) syntaktických monoidů a polookruhů a syntaktických
homomorfismů s cílem efektivní charakterizace příslušnosti k důležitým
třídám jazyků. Budeme vyšetřovat třídy průsekových automatů.
Hodláme pokračovat ve studiu implicitních jazykových rovnic, především
vlastností jejich maximálních řešení, s cílem určit, pro které typy systémů
jazykových rovnic jsou všechna maximální řešení vždy regulární. Rovněž se
zaměříme na algebraický přístup k problému stavové složitosti operací na
regulárních jazycích při reprezentaci dvoucestnými automaty.
Obohatíme tzv. q-teorii dalšími poznatky. Budeme se věnovat možnostem
různých logik pro charakterizace významných tříd jazyků.
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.
Výsledky
viz http://www.math.muni.cz/~polak/Grant.html
Publikace
Počet publikací: 20
2016
-
On the irreducibility of pseudovarieties of semigroups
Journal of Pure and Applied Algebra, rok: 2016, ročník: 220, vydání: 4, DOI
2012
-
Identity checking problem for transformation monoids
Semigroup Forum, rok: 2012, ročník: 84, vydání: 3, DOI
-
On Biautomata
RAIRO - Theoretical Informatics and Applications, rok: 2012, ročník: 46, vydání: 4, DOI
2011
-
Describing periodicity in two-way deterministic finite automata using transformation semigroups
Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings, rok: 2011
-
Identity Problems, Solvability of Equations and Unification in Varieties of Semigroups Related to Varieties of Groups
Algebraic Foundations in Computer Science, rok: 2011
-
On Biautomata
Non-Classical Models for Automata and Applications, rok: 2011
-
Piecewise Testable Languages via Combinatorics on Words
Discrete Mathematics, rok: 2011, ročník: 311, vydání: 20, DOI
-
Rewriting in Varieties of Idempotent Semigroups
Algebraic Informatics, rok: 2011
-
State complexity of operations on two-way deterministic finite automata over a unary alphabet
Descriptional Complexity of Formal Systems: 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings, rok: 2011
-
State complexity of union and intersection for two-way nondeterministic finite automata
Fundamenta Informaticae, rok: 2011, ročník: 110, vydání: 1-4, DOI