Publication detail

Left-Forbidding Cooperating Distributed Grammar Systems

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"
}