Jumping Scattered Context Grammars
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F17%3APU122820" target="_blank" >RIV/00216305:26230/17:PU122820 - isvavai.cz</a>
Result on the web
<a href="http://www.fit.vutbr.cz/research/pubs/all.php?id=10750" target="_blank" >http://www.fit.vutbr.cz/research/pubs/all.php?id=10750</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.3233/FI-2017-1505" target="_blank" >10.3233/FI-2017-1505</a>
Alternative languages
Result language
angličtina
Original language name
Jumping Scattered Context Grammars
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Fundamenta Informaticae
ISSN
0169-2968
e-ISSN
1875-8681
Volume of the periodical
152
Issue of the periodical within the volume
1
Country of publishing house
PL - POLAND
Number of pages
36
Pages from-to
51-86
UT code for WoS article
000398597900004
EID of the result in the Scopus database
2-s2.0-85015808772