Detail výsledku

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.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Soukup Ondřej, Ing., Ph.D., FIT (FIT), UIFS (FIT)
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

Rok
2014
Strany
89–100
Sborník
Proceedings of MEMICS'14
Konference
MEMICS'14 -- 9th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
ISBN
978-80-214-5022-6
Vydavatel
NOVPRESS s.r.o.
Místo
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/"
}
Soubory
Projekty
Centrum excelence IT4Innovations, MŠMT, Operační program Výzkum a vývoj pro inovace, ED1.1.00/02.0070, zahájení: 2011-01-01, ukončení: 2015-12-31, ukončen
Výzkum pokročilých metod ICT a jejich aplikace, VUT, Vnitřní projekty VUT, FIT-S-14-2299, zahájení: 2014-01-01, ukončení: 2016-12-31, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru