Left-forbidding cooperating distributed grammar systems

Filip GoldefusFilip Goldefus, Tomáš MasopustTomáš Masopust, Alexander MedunaAlexander Meduna

ISSN: 0304-3975
Download
DOI Link

Filip Goldefus, Tomáš Masopust, Alexander Meduna
Left-forbidding cooperating distributed grammar systems
Theoretical Computer Science, 411(40-42):3661-3667, 2010

Details
Bibtex

KurzfassungAbstract
A left-forbidding grammar, introduced in this paper, 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 grammars as 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 working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@article{GMM2010,
  author  = {Filip Goldefus and Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
  title   = {Left-forbidding cooperating distributed grammar systems},
  journal = {Theoretical Computer Science},
  volume  = {411},
  number  = {40-42},
  year    = {2010},
  pages   = {3661-3667},
  doi     = {10.1016/j.tcs.2010.06.010}
}