Left-Forbidding Cooperating Distributed Grammar Systems

Czech title

Levě zakazující kooperující distribuované gramatické systémy

Type

journal article

Language

english

Authors

Goldefus Filip, Mgr. (DIFS FIT BUT)
Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)

Keywords

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

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.

Annotation

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.

Published

2010

Pages

3661-3667

Journal

Theoretical Computer Science, vol. 411, no. 40, ISSN 0304-3975

Book

Theoretical Computer Science

Publisher

Elsevier Science

Place

Paris, FR

DOI

10.1016/j.tcs.2010.06.010

EID Scopus

2-s2.0-77956095170

BibTeX

@ARTICLE{FITPUB9215,
   author = "Filip Goldefus and Tom\'{a}\v{s} Masopust and Alexander Meduna",
   title = "Left-Forbidding Cooperating Distributed Grammar Systems",
   pages = "3661--3667",
   booktitle = "Theoretical Computer Science",
   journal = "Theoretical Computer Science",
   volume = 411,
   number = 40,
   year = 2010,
   location = "Paris, FR",
   publisher = "Elsevier Science",
   ISSN = "0304-3975",
   doi = "10.1016/j.tcs.2010.06.010",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9215"
}