Structuring grammar systems by priorities and hierarchies

Mitrana Victor; Păun Gheorghe; 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]
Előnézet
Cikk, tanulmány, mű
cybernetica_011_numb_003_189-204.pdf

Letöltés (920kB) | Előnézet

Absztrakt (kivonat)

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.

Mű típusa: Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe: Acta cybernetica
Dátum: 1994
Kötet: 11
Szám: 3
ISSN: 0324-721X
Oldalak: pp. 189-204
Nyelv: angol
Kiadás helye: Szeged
Befoglaló mű URL: http://acta.bibl.u-szeged.hu/38497/
Kulcsszavak: Számítástechnika, Kibernetika
Megjegyzések: Bibliogr.: 204. p. ; összefoglalás angol nyelven
Szakterület: 01. Természettudományok
01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma: 2016. okt. 15. 12:26
Utolsó módosítás: 2022. jún. 13. 11:48
URI: http://acta.bibl.u-szeged.hu/id/eprint/12528
Bővebben:
Tétel nézet Tétel nézet