Ústav informačních systémů

Bezkontextové gramatiky a zásobníkové automaty

Název v angličtině:Context-free languages and pushdown automata
Hlavní řešitel:Meduna Alexander
Další řešitelé:Čermák Martin, Koutný Jiří, Křivka Zbyněk
Agentura:Ministerstvo školství, mládeže a tělovýchovy České republiky - KONTAKT
Kód:MEB041003
Zahájení:2010-01-01
Ukončení:2011-12-31
Klíčová slova:teorie formální jazyků, primitivní slova, gramatiky, automaty
Anotace:
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.
Výsledky projektu:
Kromě publikací, které považujeme za hlavní výsledky projektu, byly uspořádány na FIT, VUT v Brně 4 veřejné odborné semináře se 6 výzkumnými přednáškami v angličtině:
  • 29. 3. 2011: J. Falucskai (College of Nyíregyháza, Hungary): Some Algorithms Concerning Uniquely Decipherable Codes; G. Horváth (University of Debrecen, Hungary): Pumping lemmas for linear and nonlinear context-free languages
  • 7. 7. 2011: P. Dömösi (College of Nyíregyháza, Hungary): Context-free languages and primitive words
  • 21. 7. 2011: János Falucskai (College of Nyíregyháza, Hungary): A New Interpretation of the Decipherability
  • 2. 11. 2011: P. Dömösi (College of Nyíregyháza, Hungary): Something About Cryptography; G. Horváth (University of Debrecen, Hungary): The Language of Primitive Words

Publikace

2012KOUTNÝ Jiří a MEDUNA Alexander. Tree-Controlled Grammars with Restrictions Placed upon Cuts and Paths. Kybernetika. 2012, roč. 48, č. 1, s. 165-175. ISSN 0023-5954.
 MEDUNA Alexander a ZEMEK Petr. One-Sided Forbidding Grammars and Selective Substitution Grammars. International Journal of Computer Mathematics. 2012, roč. 89, č. 5, s. 586-596. ISSN 0020-7160.
 ČERMÁK Martin, HORÁČEK Petr a MEDUNA Alexander. Rule-restricted automaton-grammar transducers: Power and linguistic applications. Mathematics for Applications. Brno: Ústav matematiky FEKT VUT v Brně, 2012, roč. 1, č. 1, s. 13-35. ISSN 1805-3610.
 ČERMÁK Martin, KOUTNÝ Jiří a MEDUNA Alexander. Parsing Based on n-Path Tree-Controlled Grammars. Theoretical and Applied Informatics. Varšava: 2012, roč. 2011, č. 23, s. 213-228. ISSN 1896-5334.
2011KOUTNÝ 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.
 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.
 KŘIVKA Zbyněk a MASOPUST Tomáš. Cooperating Distributed Grammar Systems with Random Context Grammars as Components. Acta Cybernetica. 2011, roč. 20, č. 2, s. 269-283. ISSN 0324-721X.
 Č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.
 Č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.
2010LUKÁŠ Roman a MEDUNA Alexander. Multigenerative Grammar Systems and Matrix Grammars. Kybernetika. 2010, roč. 46, č. 1, s. 68-82. ISSN 0023-5954.

Vaše IPv4 adresa: 54.159.51.118
Přepnout na IPv6 spojení

DNSSEC [dnssec]