SPLICING SYSTEMS WITH TARGETS ARE COMPUTATIONALLY UNIVERSAL

Authors
PAUN G
Citation
G. Paun, SPLICING SYSTEMS WITH TARGETS ARE COMPUTATIONALLY UNIVERSAL, Information processing letters, 59(3), 1996, pp. 129-133
Citations number
19
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
59
Issue
3
Year of publication
1996
Pages
129 - 133
Database
ISI
SICI code
0020-0190(1996)59:3<129:SSWTAC>2.0.ZU;2-U
Abstract
We prove that each recursively enumerable language can be generated by an extended splicing system with targets having finitely many rules o f radius at most two. (The target of a splicing rule is a regular lang uage: the rule can be applied to two strings only if the result of the splicing belongs to the target language.)