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)
Preview |
Cikk, tanulmány, mű
cybernetica_011_numb_003_189-204.pdf Download (920kB) | Preview |
Abstract
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: | http://acta.bibl.u-szeged.hu/38497/ |
| 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 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/12528 |
Actions (login required)
 |
View Item |
