Applications of Algebra and Combinatorics in Formal Language Theory
Project goals
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.
Keywords
varieties of regular languagespseudovarieties of semigroupsdot-depth hierarchypiecewise testable languagesfinite ordered semigroupslanguage equationswell quasi-orders
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 19 (SGA0201500001)
Main participants
Masarykova univerzita / Přírodovědecká fakulta
Contest type
VS - Public tender
Contract ID
15-02862S
Alternative language
Project name in Czech
Aplikace algebry a kombinatoriky v teorii formálních jazyků
Annotation in Czech
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.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
IN - Informatics
CEP - another secondary branch
—
10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project focused on the development of algebraic and combinatorial methods in formal languages. The achieved results contribute significantly to the mathematical theory of regular languages (the decidability of the levels and the half levels stages of the Straubing-Thérien hierarchy) and to the theory of the finite semigroups.
Solution timeline
Realization period - beginning
Jan 1, 2015
Realization period - end
Dec 31, 2017
Project status
U - Finished project
Latest support payment
Apr 5, 2017
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
CEP18-GA0-GA-U/02:1
Data delivery date
May 4, 2018
Finance
Total approved costs
3,203 thou. CZK
Public financial support
3,203 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
3 203 CZK thou.
Public support
3 203 CZK thou.
100%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 2015 - 31. 12. 2017