On derivation languages of a class of splicing systems

Mahalingam Kalpana; Paul Prithwineel; Mäkinen Erkki: On derivation languages of a class of splicing systems. In: Acta cybernetica, (23) 4. pp. 981-993. (2018)

Előnézet

Cikk, tanulmány, mű cybernetica_023_numb_003_0981-0993.pdf Letöltés (325kB) | Előnézet

Absztrakt (kivonat)

Derivation languages are language theoretical tools that describe halting derivation processes of a generating device. We consider two types of derivation languages, namely Szilard and control languages for splicing systems where iterated splicing is done in non-uniform way defined by Mitrana, Petre and Rogojin in 2010. The families of Szilard (rules and labels are mapped in a one to one manner) and control (more than one rule can share the same label) languages generated by splicing systems of this type are then compared with the family of languages in the Chomsky hierarchy. We show that context-free languages can be generated as Szilard and control languages and any non-empty context-free language is a morphic image of the Szilard language of this type of system with finite set of rules and axioms. Moreover, we show that these systems with finite set of axioms and regular set of rules are capable of generating any recursively enumerable language as a control language.

Mű típusa:	Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe:	Acta cybernetica
Dátum:	2018
Kötet:	23
Szám:	4
ISSN:	0324-721X
Oldalak:	pp. 981-993
Nyelv:	angol
Kiadó:	University of Szeged, Institute of Informatics
Kiadás helye:	Szeged
Befoglaló mű URL:	http://acta.bibl.u-szeged.hu/58250/
DOI:	10.14232/actacyb.23.4.2018.1
Kulcsszavak:	Számítástechnika, Programozás
Megjegyzések:	Bibliogr.: p. 992-993. ; ö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:	2019. júl. 17. 13:56
Utolsó módosítás:	2022. jún. 21. 08:29
URI:	http://acta.bibl.u-szeged.hu/id/eprint/58183

Bővebben:

Tétel nézet