Publication Details

Weak Leftmost Derivations in Cooperative Distributed Grammar Systems

MEDUNA, A.; GOLDEFUS, F. Weak Leftmost Derivations in Cooperative Distributed Grammar Systems. MEMICS 09. Brno: Brno University of Technology, 2009. p. 144-151. ISBN: 978-80-87342-04-6.

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

Conference

MEMICS'09 -- 5th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Znojmo, CZ

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