Detail publikačního výsledku

Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes

MEDUNA, A.; SOUKUP, O.

Originální název

Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes

Anglický název

Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

This paper introduces and studies a whole variety of derivation modes in scattered context grammars. These grammars are conceptualized just like classical scattered context grammars except that during the applications of their rules, after erasing n nonterminals, they can insert new substrings possibly at different positions than the original occurrence of the erased nonterminal.

The paper concentrates its attention on investigating the generative power of scattered context grammars  working under these derivation modes. It demonstrates that all of them are computationally complete--that is, they characterize the family of recursively enumerable languages.

Anglický abstrakt

This paper introduces and studies a whole variety of derivation modes in scattered context grammars. These grammars are conceptualized just like classical scattered context grammars except that during the applications of their rules, after erasing n nonterminals, they can insert new substrings possibly at different positions than the original occurrence of the erased nonterminal.

The paper concentrates its attention on investigating the generative power of scattered context grammars  working under these derivation modes. It demonstrates that all of them are computationally complete--that is, they characterize the family of recursively enumerable languages.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

MEDUNA, A.; SOUKUP, O.

Rok RIV

2015

Vydáno

17.10.2014

Nakladatel

NOVPRESS s.r.o.

Místo

Brno

ISBN

978-80-214-5022-6

Kniha

Proceedings of MEMICS'14

Strany od

89

Strany do

100

Strany počet

12

URL

https://www.fit.vut.cz/research/publication/10730/

BibTex

@inproceedings{BUT111656,
  author="Alexandr {Meduna} and Ondřej {Soukup}",
  title="Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes",
  booktitle="Proceedings of MEMICS'14",
  year="2014",
  pages="89--100",
  publisher="NOVPRESS s.r.o.",
  address="Brno",
  isbn="978-80-214-5022-6",
  url="https://www.fit.vut.cz/research/publication/10730/"
}

Dokumenty

paper