28066504
Multiple splicing systems and the universal computability
We propose a new extension of splicing systems, called multiple splicing systems, based on a kind of logic grammars. First, we introduce a class of Elementary formal systems, called simple H-form EFS, and show that its generative power is equivalent to the class of basic splicing systems (the original Head's splicing system) and is more adequate as representation device for formal languages. Next, we gradually extend the simple class of EFSs and get a very natural extension of splicing systems, multiple splicing systems. We show that multiple splicing systems have universal computability.
32287187
Sticker systems with complex structures
Abstract In this paper, we propose a variant of sticker systems which uses molecules with complex structures. Since the original sticker systems (Paun et al. (1998) [2, 8]) working on double strands of DNA have been studied as a formal model for self-assembly in DNA computing, we extend the sticker systems to working on more complex (higher-order) structures of DNA molecules. The advantage of sticker systems with complex structures is that augmented with weak codings we can obtain the characterization of recursively enumerable languages by using only sticking (hybridization) operations for complex molecules, while the usual sticker systems require more complicated operations such as the simultaneous use of couples of dominoes or coherent computations besides morphisms.
5965546
An Algorithm for Testing Structure Freeness of Biomolecular Sequences
We are concerned with a problem of checking the structure freeness of S + for a given set S of DNA sequences. It is still open whether or not there exists an efficient algorithm for this problem. In this paper, we will give an efficient algorithm to check the structure freeness of S + under the constraint that every sequence may form only linear secondary structures, which partially solves the open problem.
8742017
Two Extensions of PX system
Abstract Two extensions of PX system will be discussed. The extensions are ctPX (catch/throw PX) and mvPX (multiple values PX). ctPX is a PX system extended with Nakano's catch/throw logic. ctPX enables to extract LISP programs with catch/throw mechanism form natural proofs. mvPX is a PX system which uses multiple values rather than lists to keep a finite sequences of data. Programs extracted by ctPX are more efficient than the ones by the original PX.