Informace o projektu
Aplikace algebry a kombinatoriky v teorii formálních jazyků
- Kód projektu
- GA15-02862S
- Období řešení
- 3/2015 - 12/2017
- Investor / Programový rámec / typ projektu
-
Grantová agentura ČR
- Standardní projekty
- Fakulta / Pracoviště MU
-
Přírodovědecká fakulta
- doc. Mgr. Ondřej Klíma, Ph.D.
- doc. Mgr. Michal Kunc, Ph.D.
- doc. RNDr. Libor Polák, CSc.
Cílem projektu je získat výsledky směřující k vyřešení tří významných otevřených problémů v teorii formálních jazyků, kterými jsou rozhodnutelnost zřetězovacích hierarchií, nerozložitelnost pseudovariet pologrup a řešitelnost jazykových rovnic. Tohoto cíle hodláme dosáhnout použitím rozličných algebraických a kombinatorických technik, a to především konečné univerzální algebry, rovnostních teorií, přepisování, teorie konečných a profinitních pologrup, kombinatoriky na slovech a dobrých předuspořádání. Na základě našich dřívějších výsledků budeme tyto matematické techniky dále rozpracovávat se zřetelem na možné aplikace na nové otázky studované v teorii formálních jazyků. Výstupem budou odborné publikace, které budou prezentovány na prestižních mezinárodních konferencích teoretické informatiky a publikovány v uznávaných matematických časopisech.
Publikace
Počet publikací: 10
2020
-
Forbidden patterns for ordered automata
Journal of Automata, Languages and Combinatorics, rok: 2020, ročník: 25, vydání: 2-3, DOI
-
Representations of relatively free profinite semigroups, irreducibility, and order primitivity
Transactions of the American Mathematical Society, rok: 2020, ročník: 373, vydání: 3, DOI
2019
-
On the insertion of n-powers
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, rok: 2019, ročník: 21, vydání: 3
-
On Varieties of Ordered Automata
Language and Automata Theory and Applications, rok: 2019
-
The generalized rank of trace languages
International Journal of Foundations of Computer Science, rok: 2019, ročník: 30, vydání: 1, DOI
2018
-
The omega-inequality problem for concatenation hierarchies of star-free languages
Forum Mathematicum, rok: 2018, ročník: 30, vydání: 3, DOI
-
Towards a pseudoequational proof theory
Portugaliae mathematica, rok: 2018, ročník: 75, vydání: 2, DOI
2017
-
The generalized rank of trace languages
Developments in Language Theory. 21st International Conference, DLT 2017, Liege, Belgium, August 7-11, 2017, Proceedings, rok: 2017
2016
-
Reducibility vs. definability for pseudovarieties of semigroups
International Journal of Algebra and Computation, rok: 2016, ročník: 26, vydání: 7, DOI
2015
-
On decidability of intermediate levels of concatenation hierarchies
Developments in Language Theory : 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings, rok: 2015