All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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