Prof. RNDr. Alexander Meduna, CSc.

KŘIVKA Zbyněk a MEDUNA Alexander. Jumping Grammars. International Journal of Foundations of Computer Science. 2015, roč. 26, č. 6, s. 709-731. ISSN 0129-0541.
Jazyk publikace:angličtina
Název publikace:Jumping Grammars
Název (cs):Skákající gramatiky
Strany:709-731
Místo vydání:SG
Rok:2015
Časopis:International Journal of Foundations of Computer Science, roč. 26, č. 6, SG
ISSN:0129-0541
DOI:10.1142/S0129054115500409
Klíčová slova
Modified grammars; discontinuous rewriting; generative power; jumping finite automata; semilinearity; finite index.
Anotace
Článek zavádí a studuje skákající gramatiky, které představují gramatický protějšek nedávno zavedených skákajících automatů. Způsob práce těchto gramatiky odpovídá klasickým gramatikám až na způsob aplikace pravidel, kdy mohou při přepsání větné formy přeskočit oběma směry. Skákající gramatika tedy přepisuje řetězc z podle pravidla x -> y tak, že vybere libovolný výskyt x v z, smaže jej a vloží y na libovolnou pozici v přepisované větné formě, takže vložení může být provedeno na jinou pozici než pozici přepsaného x.

Článek se soustředí na zkoumání generativní síly skákajících gramatik. Porovnává jejich sílu se skákajícími automaty a klasickými gramatikami.  Především se zaměřuje na různé bezkontextové varianty skákajících gramatik jako například regulární, pravě-lineární, lineární a bezkontextové s konečným indexem. Navíc studuje semilinearitu bezkontextovýh, kontextových a monotónních skákajících gramatik. Dokazuje také, že obecné skákajících gramatiky charakterizují třídu rekuzivně spočetných jazyků. V závěru článek formuluje několik otevřených problémů a navrhuje oblasti budoucího studia.
BibTeX:
@ARTICLE{
   author = {Zbyn{\v{e}}k K{\v{r}}ivka and Alexander Meduna},
   title = {Jumping Grammars},
   pages = {709--731},
   journal = {International Journal of Foundations of Computer Science},
   volume = 26,
 number = 6,
   year = 2015,
   ISSN = {0129-0541},
   doi = {10.1142/S0129054115500409},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=10735}
}

Vaše IPv4 adresa: 3.81.28.94
Přepnout na https