Publication result detail

Jumping Scattered Context Grammars

MEDUNA, A.; SOUKUP, O.

Original Title

Jumping Scattered Context Grammars

English Title

Jumping Scattered Context Grammars

Type

WoS Article

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.

English 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

Key words in English


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

Authors

MEDUNA, A.; SOUKUP, O.

RIV year

2018

Released

10.02.2017

ISBN

0169-2968

Periodical

FUNDAMENTA INFORMATICAE

Volume

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/"
}

Documents

Meduna_2017_1