Aplikace algebry a kombinatoriky v teorii formálních jazyků
Cíle projektu
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.
Klíčová slova
varieties of regular languagespseudovarieties of semigroupsdot-depth hierarchypiecewise testable languagesfinite ordered semigroupslanguage equationswell quasi-orders
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 19 (SGA0201500001)
Hlavní účastníci
Masarykova univerzita / Přírodovědecká fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
15-02862S
Alternativní jazyk
Název projektu anglicky
Applications of Algebra and Combinatorics in Formal Language Theory
Anotace anglicky
The goal of the project is to obtain results aiming at potential solutions of three important open problems in formal language theory, namely, decidability of concatenation hierarchies, indecomposability of pseudovarieties of semigroups and solvability of language equations. We plan to reach this goal using various algebraic and combinatorial techniques, in particular, finite universal algebra, equational theories, rewriting, theory of finite and profinite semigroups, combinatorics on words and well quasi-orders. Based on our previous results, we will further develop these mathematical techniques, with the view of potential applications to new 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 acknowledged mathematical journals.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
IN - Informatika
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Projekt byl zaměřen na rozvoj algebraických a kombinatorických metod v oblasti formálních jazyků. Dosažené výsledky významně přispívají k matematické teorii regulárních jazyků (rozhodnutelnost pater a mezipater Straubingovy-Thérienovy hierarchie) a k teorii konečných pologrup.
Termíny řešení
Zahájení řešení
1. 1. 2015
Ukončení řešení
31. 12. 2017
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
5. 4. 2017
Dodání dat do CEP
Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP18-GA0-GA-U/02:1
Datum dodání záznamu
4. 5. 2018
Finance
Celkové uznané náklady
3 203 tis. Kč
Výše podpory ze státního rozpočtu
3 203 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
3 203 tis. Kč
Statní podpora
3 203 tis. Kč
100%
Poskytovatel
Grantová agentura České republiky
CEP
BA - Obecná matematika
Doba řešení
01. 01. 2015 - 31. 12. 2017