Detail publikace

Jumping Scattered Context Grammars

MEDUNA, A. SOUKUP, O.

Originální název

Jumping Scattered Context Grammars

Typ

článek v časopise ve Web of Science, Jimp

Jazyk

angličtina

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.

Klíčová slova

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

Autoři

MEDUNA, A.; SOUKUP, O.

Vydáno

10. 2. 2017

ISSN

0169-2968

Periodikum

Fundamenta Informaticae

Ročník

152

Číslo

1

Stát

Polská republika

Strany od

51

Strany do

86

Strany počet

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