Effective characterizations of classes of finite semigroups and formal languages
Project goals
The goal of the project is to obtain results aiming at potential solutions of important questions in the theory of regular languages and finite semigroups, namely, decidability of concatenation hierarchies of regular languages, alternative descriptions of important pseudovarieties of semigroups and principal questions of the theory of pseudovarieties. We plan to reach this goal using various algebraic and combinatorial techniques, in particular, finite universal algebra, equational theories, finite and profinite ordered semigroups and combinatorial manipulation of terms. Based on our previous results, we will further develop these mathematical techniques, with the view of potential applications to other questions studied in formal language theory. The output will consist of scientific publications, which will be presented at prestigious international conferences in theoretical computer science and published in respected mathematical journals.
Keywords
varieties of regular languagespseudovarieties of semigroupsdot-depth hierarchyfinite ordered semigroups
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 23 (SGA0201900001)
Main participants
Masarykova univerzita / Přírodovědecká fakulta
Contest type
VS - Public tender
Contract ID
19-12790S
Alternative language
Project name in Czech
Efektivní charakterizace tříd konečných pologrup a formálních jazyků
Annotation in Czech
Cílem projektu je získat výsledky směřující k vyřešení významných otázek v teorii regulárních jazyků a konečných pologrup, kterými jsou rozhodnutelnost zřetězovacích hierarchií regulárních jazyků, alternativní popisy důležitých pseudovariet pologrup a základní otázky teorie pseudovariet. 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í, konečných a prokonečných uspořádaných pologrup a kombinatorickou manipulací s termy. 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 další 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.
Scientific branches
Solution timeline
Realization period - beginning
Jan 1, 2019
Realization period - end
Dec 31, 2023
Project status
—
Latest support payment
Apr 30, 2021
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP22-GA0-GA-R
Data delivery date
Feb 22, 2022
Finance
Total approved costs
3,899 thou. CZK
Public financial support
3,560 thou. CZK
Other public sources
339 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
3 899 CZK thou.
Public support
3 560 CZK thou.
0%
Provider
Czech Science Foundation
OECD FORD
Pure mathematics
Solution period
01. 01. 2019 - 31. 12. 2023