Bezkontextové gramatiky a zásobníkové automaty

Poskytovatel

Ministerstvo školství, mládeže a tělovýchovy

Program

KONTAKT

Veřejná soutěž

—

Hlavní účastníci

—

Druh soutěže

M2 - Mezinárodní spolupráce

Číslo smlouvy

5364/2010-32

Název projektu anglicky

Context-free languages and pushdown automata

Anotace 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 conjectur

Kategorie VaV

ZV - Základní výzkum

CEP - hlavní obor

IN - Informatika

CEP - vedlejší obor

JC - Počítačový hardware a software

CEP - další vedlejší obor

—

OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)<br>20206 - Computer hardware and architecture

Hodnocení poskytovatelem

U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

Zhodnocení výsledků projektu

Cílem projektu bylo studovat modely založené na bezkontextových gramatikách a automatech. Jejich nově popsané vlastnosti byly prezentovány na 4 veřejných odborných seminářích a publikovány ve 4 mezinárodních časopisech a na několika konferencích.

Zahájení řešení

1. 1. 2010

Ukončení řešení

31. 12. 2011

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

7. 3. 2011

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

CEP12-MSM-ME-U/01:1

Datum dodání záznamu

12. 7. 2012

Celkové uznané náklady

124 tis. Kč

Výše podpory ze státního rozpočtu

124 tis. Kč

Ostatní veřejné zdroje financování

0 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč