Detail publikace
Jumping Scattered Context Grammars
MEDUNA, A. SOUKUP, O.
Originální název
Jumping Scattered Context Grammars
Anglický název
Jumping Scattered Context Grammars
Jazyk
en
Originální abstrakt
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.
Anglický abstrakt
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.
Dokumenty
BibTex
@article{BUT133485,
author="Alexandr {Meduna} and Ondřej {Soukup}",
title="Jumping Scattered Context Grammars",
annote="
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.",
address="NEUVEDEN",
chapter="133485",
doi="10.3233/FI-2017-1512",
edition="NEUVEDEN",
howpublished="online",
institution="NEUVEDEN",
number="1",
volume="152",
year="2017",
month="february",
pages="51--86",
publisher="NEUVEDEN",
type="journal article in Web of Science"
}