Přístupnostní navigace
E-application
Search Search Close
Publication detail
MEDUNA, A. SOUKUP, O.
Original Title
Jumping Scattered Context Grammars
Type
journal article in Web of Science
Language
English
Original 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.
Keywords
scattered context grammars, alternative derivation modes, generative power, computational completeness
Authors
MEDUNA, A.; SOUKUP, O.
Released
10. 2. 2017
ISBN
0169-2968
Periodical
Fundamenta Informaticae
Year of study
152
Number
1
State
Republic of Poland
Pages from
51
Pages to
86
Pages count
36
URL
https://www.fit.vut.cz/research/publication/10750/
BibTex
@article{BUT133485, author="Alexandr {Meduna} and Ondřej {Soukup}", title="Jumping Scattered Context Grammars", journal="Fundamenta Informaticae", year="2017", volume="152", number="1", pages="51--86", doi="10.3233/FI-2017-1512", issn="0169-2968", url="https://www.fit.vut.cz/research/publication/10750/" }