Jumping Scattered Context Grammars

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F17%3APU122820" target="_blank" >RIV/00216305:26230/17:PU122820 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.fit.vutbr.cz/research/pubs/all.php?id=10750" target="_blank" >http://www.fit.vutbr.cz/research/pubs/all.php?id=10750</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/FI-2017-1505" target="_blank" >10.3233/FI-2017-1505</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Jumping Scattered Context Grammars

Popis výsledku v původním jazyce

Conceptually, jumping scattered context grammars coincide with their standard counterparts, but they work differently. Indeed, a jumping version can apply a rule of the form (A1, A2, ..., An) -> (x1, x2, ..., xn) so it simultaneously erases A1, A2, ..., An in the current sentential form while inserting x1, x2, ..., xn possibly at different positions than the erased nonterminals. In fact, this paper introduces and studies scattered context grammars working under nine different jumping derivation modes, all of which give rise to the computational completeness. Indeed, the paper characterize the family of recursively enumerable languages by scattered context grammars working under any of these jumping modes. In its conclusion, the paper sketches application perspectives and formulates several open problems.

Název v anglickém jazyce

Jumping Scattered Context Grammars

Popis výsledku anglicky

Conceptually, jumping scattered context grammars coincide with their standard counterparts, but they work differently. Indeed, a jumping version can apply a rule of the form (A1, A2, ..., An) -> (x1, x2, ..., xn) so it simultaneously erases A1, A2, ..., An in the current sentential form while inserting x1, x2, ..., xn possibly at different positions than the erased nonterminals. In fact, this paper introduces and studies scattered context grammars working under nine different jumping derivation modes, all of which give rise to the computational completeness. Indeed, the paper characterize the family of recursively enumerable languages by scattered context grammars working under any of these jumping modes. In its conclusion, the paper sketches application perspectives and formulates several open problems.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

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 periodika

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

1875-8681

Svazek periodika

152

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

PL - Polská republika

Počet stran výsledku

36

Strana od-do

51-86

Kód UT WoS článku

000398597900004

EID výsledku v databázi Scopus

2-s2.0-85015808772