Publication Details

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

MEDUNA, A.; SOUKUP, O. Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes. Proceedings of MEMICS'14. Brno: NOVPRESS s.r.o., 2014. p. 89-100. ISBN: 978-80-214-5022-6.
Czech title
Výpočetní úplnost gramatik s rozptýleným kontextem vyplývající z jejich práce v různých derivačních módech
Type
conference paper
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Soukup Ondřej, Ing., Ph.D.
Keywords

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

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.

Published
2014
Pages
89–100
Proceedings
Proceedings of MEMICS'14
Conference
MEMICS'14 -- 9th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Telč, CZ
ISBN
978-80-214-5022-6
Publisher
NOVPRESS s.r.o.
Place
Brno
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/"
}
Files
Back to top