Project information
Aplikace algebry a kombinatoriky v teorii formálních jazyků
- Project Identification
- GA15-02862S
- Project Period
- 3/2015 - 12/2017
- Investor / Pogramme / Project type
-
Czech Science Foundation
- Standard Projects
- MU Faculty or unit
-
Faculty of Science
- 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.
Publications
Total number of publications: 10
2020
-
Forbidden patterns for ordered automata
Journal of Automata, Languages and Combinatorics, year: 2020, volume: 25, edition: 2-3, DOI
-
Representations of relatively free profinite semigroups, irreducibility, and order primitivity
Transactions of the American Mathematical Society, year: 2020, volume: 373, edition: 3, DOI
2019
-
On the insertion of n-powers
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, year: 2019, volume: 21, edition: 3
-
On Varieties of Ordered Automata
Language and Automata Theory and Applications, year: 2019
-
The generalized rank of trace languages
International Journal of Foundations of Computer Science, year: 2019, volume: 30, edition: 1, DOI
2018
-
The omega-inequality problem for concatenation hierarchies of star-free languages
Forum Mathematicum, year: 2018, volume: 30, edition: 3, DOI
-
Towards a pseudoequational proof theory
Portugaliae mathematica, year: 2018, volume: 75, edition: 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, year: 2017
2016
-
Reducibility vs. definability for pseudovarieties of semigroups
International Journal of Algebra and Computation, year: 2016, volume: 26, edition: 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, year: 2015