Left-forbidding cooperating distributed grammar systems

J 2010

Left-forbidding cooperating distributed grammar systems

GOLDEFUS, Filip; Tomáš MASOPUST a Alexander MEDUNA

Základní údaje

Originální název

Left-forbidding cooperating distributed grammar systems

Autoři

GOLDEFUS, Filip; Tomáš MASOPUST a Alexander MEDUNA

Vydání

Theoretical Computer Science, Amsterdam, North Holland, Elsevier Science Publishers, 2010, 0304-3975

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.838

Označené pro přenos do RIV

Organizační jednotka

Fakulta informatiky

UT WoS

000281942400012

Klíčová slova anglicky

Cooperating distributed grammar system; Cooperating derivation mode; Left-forbidding grammar; Generative power; Descriptional complexity

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 25. 10. 2010 14:21, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Anotace

V originále

A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.

Citovat

GOLDEFUS, Filip; Tomáš MASOPUST a Alexander MEDUNA. Left-forbidding cooperating distributed grammar systems. Theoretical Computer Science. Amsterdam, North Holland: Elsevier Science Publishers, 2010, roč. 411, 40-42, s. 3661-3667. ISSN 0304-3975.

@article{891315,
   author = {Goldefus, Filip and Masopust, Tomáš and Meduna, Alexander},
   article_location = {Amsterdam, North Holland},
   article_number = {40-42},
   keywords = {Cooperating distributed grammar system; Cooperating derivation mode; Left-forbidding grammar; Generative power; Descriptional complexity},
   language = {eng},
   issn = {0304-3975},
   journal = {Theoretical Computer Science},
   title = {Left-forbidding cooperating distributed grammar systems},
   url = {http://dx.doi.org/10.1016/j.tcs.2010.06.010},
   volume = {411},
   year = {2010}
}

TY  - JOUR
ID  - 891315
AU  - Goldefus, Filip - Masopust, Tomáš - Meduna, Alexander
PY  - 2010
TI  - Left-forbidding cooperating distributed grammar systems
JF  - Theoretical Computer Science
VL  - 411
IS  - 40-42
SP  - 3661-3667
EP  - 3661-3667
PB  - Elsevier Science Publishers
SN  - 03043975
KW  - Cooperating distributed grammar system
KW  - Cooperating derivation mode
KW  - Left-forbidding grammar
KW  - Generative power
KW  - Descriptional complexity
UR  - http://dx.doi.org/10.1016/j.tcs.2010.06.010
N2  - A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.
ER  -

GOLDEFUS, Filip; Tomáš MASOPUST a Alexander MEDUNA. Left-forbidding cooperating distributed grammar systems. \textit{Theoretical Computer Science}. Amsterdam, North Holland: Elsevier Science Publishers, 2010, roč.~411, 40-42, s.~3661-3667. ISSN~0304-3975.

Přehled o publikaci