Detail projektu

Bezkontextové gramatiky a zásobníkové automaty

Období řešení: 1. 1. 2010 - 31. 12. 2011

Typ projektu: grant

Kód: MEB041003

Agentura: Ministerstvo školství, mládeže a tělovýchovy České republiky

Program: KONTAKT

Název anglicky
Context-free languages and pushdown automata
Typ
grant
Klíčová slova

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

Abstrakt
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.
Řešitelé
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT) , hlavní řešitel
Čermák Martin, Ing. (UIFS FIT VUT)
Koutný Jiří, Ing. (UIFS FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Publikace

2012

  • MEDUNA Alexander a ZEMEK Petr. One-Sided Forbidding Grammars and Selective Substitution Grammars. International Journal of Computer Mathematics, roč. 89, č. 5, 2012, s. 586-596. ISSN 0020-7160. Detail
  • ČERMÁK Martin, HORÁČEK Petr a MEDUNA Alexander. Rule-restricted automaton-grammar transducers: Power and linguistic applications. Mathematics for Applications, roč. 1, č. 1, 2012, s. 13-35. ISSN 1805-3610. Detail
  • KOUTNÝ Jiří a MEDUNA Alexander. Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths. Kybernetika, roč. 48, č. 1, 2012, s. 165-175. ISSN 0023-5954. Detail

2011

  • ČERMÁK Martin. Basic Properties of n-Languages. In: Proceedings of the 17th Conference and Competition STUDENT EEICT 2011 Volume 3. Brno: Fakulta informačních technologií VUT v Brně, 2011, s. 460-464. ISBN 978-80-214-4273-3. Detail
  • KŘIVKA Zbyněk a MASOPUST Tomáš. Cooperating Distributed Grammar Systems with Random Context Grammars as Components. Acta Cybernetica, roč. 20, č. 2, 2011, s. 269-283. ISSN 0324-721X. Detail
  • ČERMÁK Martin a MEDUNA Alexander. n-Accepting Restricted Pushdown Automata Systems. In: 13th International Conference on Automata and Formal Languages. Nyíregyháza: Computer and Automation Research Institute, Hungarian Academy of Sciences, 2011, s. 168-183. ISBN 978-615-5097-19-5. Detail
  • ČERMÁK Martin, KOUTNÝ Jiří a MEDUNA Alexander. Parsing Based on n-Path Tree-Controlled Grammars. Theoretical and Applied Informatics, roč. 23, č. 3, 2011, s. 213-228. ISSN 1896-5334. Detail
  • KOUTNÝ Jiří, KŘIVKA Zbyněk a MEDUNA Alexander. Pumping Properties of Path-Restricted Tree-Controlled Languages. In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Vysoké učení technické v Brně, 2011, s. 61-69. ISBN 978-80-214-4305-1. Detail
  • KOUTNÝ Jiří. Syntax Analysis of Tree-Controlled Languages. In: Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3. Brno: Vysoké učení technické v Brně, 2011, s. 5. ISBN 978-80-214-4273-3. Detail

2010

  • LUKÁŠ Roman a MEDUNA Alexander. Multigenerative Grammar Systems and Matrix Grammars. Kybernetika, roč. 46, č. 1, 2010, s. 68-82. ISSN 0023-5954. Detail
Nahoru