Weak Leftmost Derivations in Cooperative Distributed Grammar Systems

Czech title

Slabé levé derivace pro kooperativně distributivní gramatické systémy

Type

conference paper

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Goldefus Filip, Mgr.

Keywords

leftmost derivation, cooperative distributed grammar systems, generative power, Chomsky Hierarchy

Abstract

This paper introduces and discusses a weak leftmost restriction placed upon derivations in cooperative distributed grammar systems. During every derivation step restricted in this way, a system rewrites the leftmost nonterminal coinciding with the left-hand side of a production that belong to a prescribed set of productions in a grammatical component of the system. The present paper proves that cooperative distributed grammar systems restricted in this way characterize the family of recursively enumerable languages.

Annotation

This paper introduces and discusses a weak leftmost restriction placed upon derivations in cooperative distributed grammar systems. During every derivation step restricted in this way, a system rewrites the leftmost nonterminal coinciding with the left-hand side of a production that belong to a prescribed set of productions in a grammatical component of the system. The present paper proves that cooperative distributed grammar systems restricted in this way characterize the family of recursively enumerable languages.

Published

2009

Pages

144–151

Proceedings

MEMICS 09

ISBN

978-80-87342-04-6

Publisher

Brno University of Technology

Place

Brno

BibTeX

@inproceedings{BUT91231,
  author="Alexandr {Meduna} and Filip {Goldefus}",
  title="Weak Leftmost Derivations in Cooperative Distributed Grammar Systems",
  booktitle="MEMICS 09",
  year="2009",
  pages="144--151",
  publisher="Brno University of Technology",
  address="Brno",
  isbn="978-80-87342-04-6"
}