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

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/ED1.1.00%2F02.0070" target="_blank" >ED1.1.00/02.0070: Centrum excelence IT4Innovations</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of MEMICS'14

ISBN

978-80-214-5022-6

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

89-100

Název nakladatele

NOVPRESS s.r.o.

Místo vydání

Brno

Místo konání akce

Telč

Datum konání akce

17. 10. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—