Plánovaný výzkum se zaměří na studium bezkontextových jazyků a zásobníkových automatů a jejich aplikací. Pro hlubší pochopení struktur formálních jazyků je nápomocné studovat jejich kombinatorické vlastnosti. Jedním z předmětů výzkumu je problém primitivních slov. Slovo nazýváme primitivní, pokud není mocninou jiného slova. P. Dömösi, M. Ito a S. Horváth prezentovali domněnku, že jazyk všech primitivních slov nad abecedou s několika symboly, Q, není bezkontextový. Nedávno publikované články se stále zabývají tímto proslulým dohadem, který je stále otevřeným problémem. Plánujeme dále rozvíjet toto zkoumání se zaměřením na malé bezkontextové gramatiky generující primitivní slova. Na druhou stranu, vezmeme-li v úvahu, že homomorfický obraz neprimitivního slova je také neprimitivní, budeme také studovat, zda je Q skutečnou homomorfickou charakterizací Chomsky-Schützenberger-Stanleyho typu. Doufáme, že toto zkoumání povede na důkaz platnosti či neplatnosti předchozí domněnky a otevřeného problému. Dále bychom rádi charakterizovali bezkontextové jazyky z neprimitivních slov. Během tohoto výzkumu můžeme odhalit nové důležité vlastnosti bezkontextových jazyků. Studium kombinatorických vlastností slov a jazyků nám může poskytnout řadu informací o struktuře jazyků s vazbou na Chomského hierarchii a odpovídající automaty. Jedním z nejdůležitějších výsledků v této oblasti je Bar-Hillelovo lemma, které poskytuje efektivní metodu pro testování, zda je jazyk bezkontextový či nikoli. K dispozici jsou také silnější verze tohoto lemmatu. Nasnadě je tedy studium třídy nelineárních bezkontextových jazyků. G. Horváth objevil silně iterující vlastnosti nelineárních bezkontextových jazyků, které bychom rádi také v tomto projektů dále zkoumali. Podle dobře známého teorému Chomsky-Schützenberger-Stanleyho, jež říká, že každý bezkontextový jazyk je homomorficky charakterizovaný pomocí, h, D a R, kde h je homomorfismus, D je Dyckův jazyk a R je regulární jazyk. Existuje několik rozšíření tohoto výsledku. V tomto projektu plánujeme pokračovat také v tomto výzkumu, kdy se pokusíme vytvořit skutečnou homomorfickou charakterizaci bezkontextových jazyků s danou kombinatorickou vlastností (skromnost (angl. slenderness), poloskromnost, palindromicita, atd.). Matematická hodnota očekávaných výsledků bude podpořena jejich publikací v mezinárodních vědeckých časopisech a na konferencích.

Popis anglicky
The planned research will focus on the study of context-free languages and pushdown automata and their applications. To understand the structure of formal languages is a helpful tool to study their combinatorial properties. One of the subjects of this research is the problem of primitive words. A word is called primitive if it is not a power of another word. A widely known conjecture of P. Dömösi, M. Ito, and S. Horváth states that the language Q of all primitive words over an alphabet with several letters is not context-free. A number of recent papers investigated this well-known conjecture which is still open. We intend to continue our investigations on small context-free grammars generating primitive words. On the other hand, using the fact that a homomorphic map of a nonprimitive word is also nonprimitive, we also plan to study whether or not Q has a real Chomsky-Schützenberger-Stanley type homomorphic characterization. By our hope, these investigations may lead to prove or disprove our conjecture. In addition, we would like to characterize context-free languages consisting of non-primitive words. By this research we can also find new important properties of context-free languages. Studying the combinatorial properties of words and languages we can get a lot of information on the structure of languages in connection with the Chomsky hierarchy and corresponding automata. Regarding this subject, one of the most important results is the Bar-Hillel Lemma having an effective method for testing a language whether or not it is context-free. There are some well-known stronger versions of this result. One direction is to study the family of context-free non-linear languages. G. Horváth discovered a strong iteration property of context-free non-linear languages. In this project we would like to continue this line of research. By the well-known Chomsky-Schützenberger-Stanley theorem, every context-free language is homomorphically characterized by h and D, R, where h is a homomorphism, D is a Dyck language and R is a regular language. Several extensions of this result are known. In this project we plan to continue this research giving real homomorphic characterizations of context-free languages having certain combinatorial properties (slenderness, poly-slenderness, palindromicity, etc). The mathematical value of the expected results will be proved by their publications in international scientific journals and conferences.

Klíčová slova
teorie formální jazyků, primitivní slova, gramatiky, automaty

Klíčová slova anglicky
formal language theory, primitive words, grammars, automata