Romanian Journal of Information Science and Technology (ROMJIST)

An open – access publication

  |  HOME  |   GENERAL INFORMATION  |   ROMJIST ON-LINE  |  KEY INFORMATION FOR AUTHORS  |   COMMITTEES  |  

ROMJIST is a publication of Romanian Academy,
Section for Information Science and Technology

Editor – in – Chief:

Academician Dan Dascalu

Secretariate (office):
Adriana Apostol
Adress for correspondence: romjist@nano-link.net (after 1st of January, 2019)

Editing of the printed version: Mihaela Marian (Publishing House of the Romanian Academy, Bucharest)

Technical editor
of the on-line version:
Lucian Milea (University POLITEHNICA of Bucharest)

Sponsors:
• National Institute for R & D
in Microtechnologies
(IMT Bucharest), www.imt.ro
• Association for Generic
and Industrial Technologies (ASTEGI), www.astegi.ro

ROMJIST Volume 19, No. 4, 2016, pp. 369-384, Paper no. 544/2016
 

Mahalingam KALPANA, Paul PRITHWINEEL
Locally Evolving Splicing Systems

ABSTRACT: An extended H system with locally evolving rules is a model of splicing computation with a special feature that the splicing rules evolve at each step. It was originally proved by Paun et al. that all RE languages can be generated by such systems with a finite set of rules of radius at most 4 and with contexts of length at most 7 for the insertion-deletion rules by which the splicing rules evolve. We improve this result by reducing the length of the contexts to at most 2 and we also show that such systems with radius at most 2 and contexts of length at most 3 can generate all RE languages. In both cases, the insertion-deletion rules will insert or delete only one symbol. We also show that if the inserted strings are of length at most 2 and the deleted strings are of length 1, then the system can generate all RE languages with splicing rules of radius 3 and insertion-deletion rules with contexts of length at most 2. Finally, we show that the length of contexts and of the strings inserted/deleted can be reduced to 1 if the rules are applied in a matrix controlled manner.

KEYWORDS: Extended H system, splicing, evolving rules, recursively enumer-able

Read full text (pdf)






  |  HOME  |   GENERAL INFORMATION  |   ROMJIST ON-LINE  |  KEY INFORMATION FOR AUTHORS  |   COMMITTEES  |