Martín-Vide Carlos; Păun Gheorghe: Duplication grammars. In: Acta cybernetica, (14) 1. pp. 151-164. (1999)
Előnézet |
Cikk, tanulmány, mű
cybernetica_014_numb_001_151-164.pdf Letöltés (862kB) | Előnézet |
Absztrakt (kivonat)
Motivated by the abundance of duplication operations appearing in natural languages and in the genetic area, we introduce a generative mechanism based on duplication operations: one starts from a given finite set of strings and one produces new strings by copying certain substrings, according to a set of given rules (which specify contexts where duplicated substrings can be inserted). We mainly investigate the power of such devices, comparing the obtained families of languages to each other and with families in the Chomsky hierarchy. In this context, we also solve a problem left open in a paper by Dassow and Mitrana, [1], even giving a stronger results: the iterated duplication with rules of only one type (see formal definitions in the sequel) can generate non-context-free languages (even non-matrix languages).
Mű típusa: | Cikk, tanulmány, mű |
---|---|
Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
Dátum: | 1999 |
Kötet: | 14 |
Szám: | 1 |
ISSN: | 0324-721X |
Oldalak: | pp. 151-164 |
Nyelv: | angol |
Kiadás helye: | Szeged |
Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/38507/ |
Kulcsszavak: | Számítástechnika, Kibernetika |
Megjegyzések: | Bibliogr.: p. 163-164. ; ö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. 14. 09:54 |
URI: | http://acta.bibl.u-szeged.hu/id/eprint/12616 |
![]() |
Tétel nézet |