Result 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.

Type

conference paper

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Soukup Ondřej, Ing., Ph.D., FIT (FIT), DIFS (FIT)

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

Published

2014

Pages

89–100

Proceedings

Proceedings of MEMICS'14

Conference

MEMICS'14 -- 9th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science

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

pdf paper.pdf 219 kB

Projects

Centrum excelence IT4Innovations, MŠMT, Operační program Výzkum a vývoj pro inovace, ED1.1.00/02.0070, start: 2011-01-01, end: 2015-12-31, completed
Výzkum pokročilých metod ICT a jejich aplikace, BUT, Vnitřní projekty VUT, FIT-S-14-2299, start: 2014-01-01, end: 2016-12-31, completed

Research groups

Formal Model Research Group (RG FM)

Departments

Department of Information Systems (DIFS)