Publication Details

Jumping Scattered Context Grammars

MEDUNA Alexander and SOUKUP Ondřej. Jumping Scattered Context Grammars. Fundamenta Informaticae, vol. 152, no. 1, 2017, pp. 51-86. ISSN 0169-2968.
Czech title
Skákájící Gramatiky s Rozptýleným Kontextem
Type
journal article
Language
english
Authors
Keywords


scattered context grammars, alternative derivation modes, generative power, computational completeness

Abstract


Conceptually, jumping scattered context grammars coincide with their standard counterparts, but they work differently. Indeed, a jumping version can apply a rule of the form (A1, A2, ..., An) -> (x1, x2, ..., xn) so it simultaneously erases A1, A2, ..., An in the current sentential form while inserting x1, x2, ..., xn possibly at different positions than the erased nonterminals. In fact, this paper introduces and studies scattered context grammars working under nine different jumping derivation modes, all of which give rise to the computational completeness. Indeed, the paper characterize the family of recursively enumerable languages by scattered context grammars working under any of these jumping modes. In its conclusion, the paper sketches application perspectives and formulates several open problems.

Published
2017
Pages
51-86
Journal
Fundamenta Informaticae, vol. 152, no. 1, ISSN 0169-2968
Publisher
IOS Press
DOI
UT WoS
000398597900004
EID Scopus
BibTeX
@ARTICLE{FITPUB10750,
   author = "Alexander Meduna and Ond\v{r}ej Soukup",
   title = "Jumping Scattered Context Grammars",
   pages = "51--86",
   journal = "Fundamenta Informaticae",
   volume = 152,
   number = 1,
   year = 2017,
   ISSN = "0169-2968",
   doi = "10.3233/FI-2017-1512",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10750"
}
Back to top