Přístupnostní navigace
E-application
Search Search Close
Publication detail
MASOPUST, T. GOLDEFUS, F. MEDUNA, A.
Original Title
Left-Forbidding Cooperating Distributed Grammar Systems
Type
journal article in Scopus
Language
English
Original Abstract
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.
Keywords
Cooperating distributed grammar system, cooperating derivation mode, left-forbidding grammar, generative power, descriptional complexity.
Authors
MASOPUST, T.; GOLDEFUS, F.; MEDUNA, A.
RIV year
2010
Released
30. 4. 2010
Publisher
Elsevier Science
Location
Paris
ISBN
0304-3975
Periodical
Theoretical Computer Science
Year of study
411
Number
40
State
Kingdom of the Netherlands
Pages from
3661
Pages to
3667
Pages count
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" }