Publication detail

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

MEDUNA, A. SOUKUP, O.

Original Title

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

English Title

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

Type

conference paper

Language

en

Original Abstract

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.

English abstract

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.

Keywords

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

RIV year

2014

Released

17.10.2014

Publisher

NOVPRESS s.r.o.

Location

Brno

ISBN

978-80-214-5022-6

Book

Proceedings of MEMICS'14

Edition

NEUVEDEN

Edition number

NEUVEDEN

Pages from

89

Pages to

100

Pages count

12

URL

BibTex


@inproceedings{BUT111656,
  author="Alexandr {Meduna} and Ondřej {Soukup}",
  title="Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes",
  annote="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.",
  address="NOVPRESS s.r.o.",
  booktitle="Proceedings of MEMICS'14",
  chapter="111656",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NOVPRESS s.r.o.",
  year="2014",
  month="october",
  pages="89--100",
  publisher="NOVPRESS s.r.o.",
  type="conference paper"
}