Publication Details

Weak Leftmost Derivations in Cooperative Distributed Grammar Systems

MEDUNA Alexander and GOLDEFUS Filip. Weak Leftmost Derivations in Cooperative Distributed Grammar Systems. In: MEMICS 09. Brno: Brno University of Technology, 2009, pp. 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 Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Goldefus Filip, Mgr. (DIFS FIT BUT)
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, CZ
BibTeX 
@INPROCEEDINGS{FITPUB9118,
   author = "Alexander Meduna and Filip Goldefus",
   title = "Weak Leftmost Derivations in Cooperative Distributed Grammar Systems",
   pages = "144--151",
   booktitle = "MEMICS 09",
   year = 2009,
   location = "Brno, CZ",
   publisher = "Brno University of Technology",
   ISBN = "978-80-87342-04-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9118"
}
Back to top