Detail publikačního výsledku

Left-Forbidding Cooperating Distributed Grammar Systems

MASOPUST, T.; GOLDEFUS, F.; MEDUNA, A.

Originální název

Left-Forbidding Cooperating Distributed Grammar Systems

Anglický název

Left-Forbidding Cooperating Distributed Grammar Systems

Druh

Článek Scopus

Originální abstrakt

A left-forbidding grammar 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 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 with two left-forbidding components (including erasing productions) to characterize the family of all recursively enumerable languages.

Anglický abstrakt

A left-forbidding grammar 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 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 with two left-forbidding components (including erasing productions) to characterize the family of all recursively enumerable languages.

Klíčová slova

Cooperating distributed grammar system, cooperating derivation
mode, left-forbidding grammar, generative power, descriptional complexity.

Klíčová slova v angličtině

Cooperating distributed grammar system, cooperating derivation
mode, left-forbidding grammar, generative power, descriptional complexity.

Autoři

MASOPUST, T.; GOLDEFUS, F.; MEDUNA, A.

Rok RIV

2011

Vydáno

30.04.2010

Nakladatel

Elsevier Science

Místo

Paris

Kniha

Theoretical Computer Science

ISSN

0304-3975

Periodikum

Theoretical Computer Science

Svazek

411

Číslo

40

Stát

Nizozemsko

Strany od

3661

Strany do

3667

Strany počet

7

BibTex

@article{BUT50510,
  author="Tomáš {Masopust} and Filip {Goldefus} and Alexandr {Meduna}",
  title="Left-Forbidding Cooperating Distributed Grammar Systems",
  journal="Theoretical Computer Science",
  year="2010",
  volume="411",
  number="40",
  pages="3661--3667",
  doi="10.1016/j.tcs.2010.06.010",
  issn="0304-3975"
}