Publication Details
Left-Forbidding Cooperating Distributed Grammar Systems
Goldefus Filip, Mgr.
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Cooperating distributed grammar system, cooperating derivation
mode, left-forbidding grammar, generative power, descriptional complexity.
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.
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.
@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"
}