Structuring grammar systems by priorities and hierarchies

Mitrana Victor and Păun Gheorghe and Rozenberg Grzegorz: Structuring grammar systems by priorities and hierarchies. In: Acta cybernetica, (11) 3. pp. 189-204. (1994)

[thumbnail of cybernetica_011_numb_003_189-204.pdf]
Cikk, tanulmány, mű

Download (920kB) | Preview


A grammar system is a finite set of grammars that cooperate to generate a language. We consider two generalizations of grammar systems: (l) adding a priority relation between single grammar components, and (2) considering hierarchical components which by themselves are grammar systems. The generative power of these generalized grammar systems is investigated, and compared with the generative power of ordinary grammar systems and of some well-known types of grammars with regulated rewriting (such as matrix grammars). We prove that for many cooperating strategies the use of priority relation increases the generative capacity, however this is not the case for the maximal mode of derivation (an important case, because it gives a characterization of the ETOL languages). We also demonstrate that in many cases the use of hierarchical components does not increase the generative power.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1994
Volume: 11
Number: 3
ISSN: 0324-721X
Page Range: pp. 189-204
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: 204. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 11:48

Actions (login required)

View Item View Item