Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F14%3APU112061" target="_blank" >RIV/00216305:26230/14:PU112061 - isvavai.cz</a>
Result on the web
<a href="http://www.fit.vutbr.cz/research/pubs/all.php?id=10730" target="_blank" >http://www.fit.vutbr.cz/research/pubs/all.php?id=10730</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Computational Completeness Resulting from Scattered Context Grammars Working Under Various Derivation Modes
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: IT4Innovations Centre of Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of MEMICS'14
ISBN
978-80-214-5022-6
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
89-100
Publisher name
NOVPRESS s.r.o.
Place of publication
Brno
Event location
Telč
Event date
Oct 17, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—