In this paper, extended graph splicing systems are defined. It is shown that when strings are represented as linear graphs, any recursively enumerable set can be generated by an extended graph splicing system. It is also shown that the computational completeness of extended graph splicing systems can be proved under some constraints too. © 2006.

Kamala Krithivasan

Computational methods

Linear systems

Recursive functions

Computational completeness

CONSTRAINED SPLICING SYSTEMS

GRAPH SPLICING SYSTEMS

Graph theory

Fulltext

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Discrete Applied Mathematics

The string splicing system was introduced by Tom Head, which stands as an abstract model for the DNA recombination under the influence of restriction enzymes and ligase enzymes. However, it is observed that strings are not very capable of modelling the complex chemical process. Hence, in this article, matrix splicing system is introduced with a new splicing operation among the matrices. It is shown with an illustration that the DNA recombination process can be simulated by the matrix splicing system, which justifies the suitability of the matrices for modelling the complex processes of the molecules. The properties of the components of the system such as cutting rules and the splicing rules are discussed. Besides some properties of the system, it is shown that this system stands as a theoretical model for splicing strings in parallel. The abstraction of the ligase enzymes is explained which is missing in all the splicing models that have come out so far. The ability of the system in generating new patterns is also outlined.

International Journal of Computer Mathematics

Matrix splicing system

Theory of Computing Systems

DNA Computing Based on Splicing: The Existence of Universal Computers

On the computational power of DNA

On the undecidability of splicing systems

Bulletin of Mathematical Biology

Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors

Proceedings First International Symposium on Intelligence in Neural and Biological Systems. INBS'95

Splicing systems on graphs

Graph splicing systems

Journal	Discrete Applied Mathematics
ISSN	0166218X
Open Access	Yes