Conference paper

MEDUNA Alexander and SOUKUP Ondřej. Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes. In: Proceedings of MEMICS'14. Brno: NOVPRESS s.r.o., 2014, pp. 89-100. ISBN 978-80-214-5022-6.
Publication language:english
Original title:Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes
Title (cs):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
Pages:89-100
Proceedings:Proceedings of MEMICS'14
Conference:MEMICS'14 -- 9th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Place:Brno, CZ
Year:2014
ISBN:978-80-214-5022-6
Publisher:NOVPRESS s.r.o.
Files: 
+Type Name Title Size Last modified
iconpaper.pdf219 KB2014-10-02 15:52:49
^ Select all
With selected:
Keywords
scattered context grammars, alternative derivation modes, generative power, computational completeness
Annotation
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.
BibTeX:
@INPROCEEDINGS{
   author = {Alexander Meduna and Ond{\v{r}}ej Soukup},
   title = {Computational Completeness Resulting from Scattered Context
	Grammars Working Under Various Derivation Modes},
   pages = {89--100},
   booktitle = {Proceedings of MEMICS'14},
   year = {2014},
   location = {Brno, CZ},
   publisher = {NOVPRESS s.r.o.},
   ISBN = {978-80-214-5022-6},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.en.iso-8859-2?id=10730}
}

Your IPv4 address: 54.166.245.10
Switch to IPv6 connection

DNSSEC [dnssec]