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)
Č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