Detail publikace

Jumping Grammars

KŘIVKA Zbyněk a MEDUNA Alexander. Jumping Grammars. International Journal of Foundations of Computer Science, roč. 26, č. 6, 2015, s. 709-731. ISSN 0129-0541.
Název česky
Skákající gramatiky
Typ
článek v časopise
Jazyk
angličtina
Autoři
Abstrakt

Č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 xz, 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.

Rok
2015
Strany
709-731
Časopis
International Journal of Foundations of Computer Science, roč. 26, č. 6, ISSN 0129-0541
DOI
UT WoS
000364655800004
EID Scopus
BibTeX
@ARTICLE{FITPUB10735,
   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 = "https://www.fit.vut.cz/research/publication/10735"
}
Nahoru