Coding properties of DNA languages

The computation language of a DNA-based system consists of all the words (DNA strands) that can appear in any computation step of the system. In this work we define properties of languages which ensure that the words of such languages will not form undesirable bonds when used in DNA computations. We give several characterizations of the desired properties and provide methods for obtaining languages with such properties. The decidability of these properties is addressed as well. As an application we consider splicing systems whose computation language is free of certain undesirable bonds and is generated by nearly optimal comma-free codes.     

DNA splicing: computing by observing

Motivated by several techniques for observing molecular processes in real-time we introduce a computing device that stresses the role of the observer in biological computations and that is based on the observed behavior of a splicing system. The basic idea is to introduce a marked DNA strand into a test tube with other DNA strands and restriction enzymes. Under the action of these enzymes the DNA starts to splice. An external observer monitors and registers the evolution of the marked DNA strand. The input marked DNA strand is then accepted if its observed evolution follows a certain expected pattern. We prove that using simple observers (finite automata), applied on finite splicing systems (finite set of rules and finite set of axioms), the class of recursively enumerable languages can be recognized.     

Bond-free DNA language classes

The absence of the ability to form a specified set of bonds in a collection of DNA strands is crucial in the design of experiments encoding algorithmic problems as single- or double-stranded DNA. Recently, the specification of the bonding types to be avoided has been formalized by defining bond-free properties. Bond-free properties generalize several bonding properties which have been studied in the context of DNA computing. In this paper, we consider a bond-free property as defining a class of languages. We study the properties of these classes of languages. We develop new unary operators on languages for characterizing bond-free properties exactly, using familiar code-theoretic equations. These new operators provide a new characterization of maximal bond-free properties as well. We also focus on relationships to classes of languages from the theory of codes. Research supported in part by a grant from NSERC.     

A computer scientist's guide to molecular biology

 In this paper, we explain the basic structure and properties of both single- and double-stranded DNA in vivo (in living organisms). We also review the first in vitro (test tube) experiment that solved a mathematical problem, The Directed Hamiltonian Path Problem, by manipulating DNA strands. Lastly, we give a list of bio-operations that have so far been used in DNA computation.     

用于DNA编码的部分字

寻找合理的DNA编码是DNA计算中一个基本的问题.因此要给出一种方法使得DNA序列不会产生不想要的结构,尤其是假阳性是解决此问题的关键.传统方法是要求码字间的Hamming距离足够大.因此考虑用部分字的方法来解决DNA编码问题,利用部分字的洞的定义及其性质得到了关于部分字的洞、Hamming距离和Watson-CrickHamming距离的3个命题,通过部分字对DNA编码进行了优化,解决了DNA编码中的部分疑难问题.     

Euclidean Group Invariant Computation of Stochastic Completion Fields Using Shiftable-Twistable Functions

We describe a method for computing the likelihood that a completion joining two contour fragments passes through any given position and orientation in the image plane. Like computations in primary visual cortex (and unlike all previous models of contour completion), the output of our computation is invariant under rotations and translations of the input pattern. This is achieved by representing the input, output, and intermediate states of the computation in a basis of shiftable-twistable functions.     

Computation with multiple CTCs of fixed length and width

We examine some variants of computation with closed timelike curves (CTCs), where various restrictions are imposed on the memory of the computer, and the information carrying capacity and range of the CTC. We give full characterizations of the classes of languages decided by polynomial time probabilistic and quantum computers that can send a single classical bit to their own past. We show that, given a time machine with constant negative delay, one can implement CTC-based computations without the need to know about the runtime beforehand. Chaining multiple instances of such fixed-length CTCs, the power of postselection can be endowed to deterministic computers, all languages in $\mathsf{NP} \cup \mathsf{coNP}$ can be decided with no error in worst-case polynomial time, and all Turing-decidable languages can be decided in constant expected time. We provide proofs of the following facts for weaker models: Augmenting probabilistic computers with a single CTC leads to an improvement in language recognition power. Quantum computers under these restrictions are more powerful than their classical counterparts. Some deterministic models assisted with multiple CTCs are more powerful than those with a single CTC.     

可满足性(SAT)问题的几种DNA计算模型

DNA计算是一种新的计算方式，其高度并行性和巨大的信息存储容量为NP-完全问题的解决提供了一种全新的方法。主要介绍了几种可满足性(SAT)问题的DNA计算模型，并在编码问题、实现方式、及算法设计等三个方面对其进行了比较。     

On non-determinism in machines and languages

Non-deterministic computation is not really computation, but the difference with real computation is blurred. We study in detail various levels of non-determinism in computations on non-deterministic Turing machines with polynomial bounds on the resources. Meanwhile, we consider numerous query languages, implicit logic, choice logic, order invariant logic, and restrictions of second-order logic, and establish correspondences between all these formalisms for both deterministic and non-deterministic queries. To the degrees of non-determinism in the computations, correspond levels of non-determinism in the logical definitions. Our main contribution is to characterize various complexity classes between PTIME and PSPACE, by several logical means, thus translating open questions in complexity theory to open questions in logic related to the use of the non-determinism.     

Zero Orders and Dimensions of Some Invariant Subspaces in Linear Structured Systems

In this paper we consider linear structured systems which represent a large class of parameter-dependent linear systems and we study invariants for such systems under a large group of transformations including state feedback. In this context we consider the dimension of the maximal output-nulling invariant subspace of a linear structured system, the number and structure of its invariant zeros and its structure at infinity. We give generic characterizations of the invariants in terms of properties of the directed graph that can be naturally associated with a linear structured system. Date received: March 1, 2002. Date revised: April 1, 2003. The first authors stay at the Laboratoire dAutomatique de Grenoble was supported by grants of the Netherlands Organization for Scientific Research (NWO), the Institut National Polytechnique de Grenoble (INPG) and the French Ministry of Research.     

An alternative definition of splicing

In this paper, we propose a new definition of the language generated by a splicing system, motivated by both biochemical and mathematical considerations. The main feature of the new definition is that by applying a splicing rule, we not only create new strings, but also allow for the removal of the strings entering the rule. This behaviour seems to correspond better to biochemical reality and is in fact used as a tool in several experimental DNA computations. We show that using this new definition, finite extended H$H$ systems can generate all recursively enumerable languages. Even a weaker version of these H$H$ systems, defined using the new notion of delay, is shown to be strictly more powerful than H$H$ systems defined in the traditional way.     

Real Hypercomputation and Continuity

By the sometimes so-called Main Theorem of Recursive Analysis, every computable real function is necessarily continuous. We wonder whether and which kinds of hypercomputation allow for the effective evaluation of also discontinuous . More precisely the present work considers the following three super-Turing notions of real function computability: - relativized computation; specifically given oracle access to the Halting Problem or its jump ; - encoding input and/or output y = f(x) in weaker ways also related to the Arithmetic Hierarchy; - nondeterministic computation. It turns out that any computable in the first or second sense is still necessarily continuous whereas the third type of hypercomputation provides the required power to evaluate for instance the discontinuous Heaviside function.     

On the finite degree of ambiguity of finite tree automata

Summary The degree of ambiguity of a finite tree automaton A, da(A), is the maximal number of different accepting computations of A for any possible input tree. We show: it can be decided in polynomial time whether or not da(A)<. We give two criteria characterizing an infinite degree of ambiguity and derive the following fundamental properties of an finite tree automaton A with n states and rank L>1 having a finite degree of ambiguity: for every input tree t there is a input tree t ₁ of depth less than 2²ⁿ·n! having the same number of accepting computations; the degree of ambiguity of A is bounded by 2^{2 2·log(L+1)·n}.     

Computations on one-dimensional cellular automata

Cellular automata may be viewed as a modelization of synchronous parallel computation. Even in the one-dimensional case, they are known as capable of universal computations. The usual proof uses a simulation of a universal Turing machine. In this paper, we present how a one-dimensional cellular automata can simulate any recursive function in such a way that composition of computations occurs as soon as possible. In addition, this allows us to show that one-dimensional cellular automata may simulate asynchronous computations.This work was supported by the Programme de Recherches Coordonnées Mathématiques et Informatique and the Esprit Basic Research Action Algebraic and Syntactical Methods in Computer Science.     

Reversible pushdown automata

Reversible pushdown automata are deterministic pushdown automata that are also backward deterministic. Therefore, they have the property that any configuration occurring in any computation has exactly one predecessor. In this paper, the computational capacity of reversible computations in pushdown automata is investigated and turns out to lie properly in between the regular and deterministic context-free languages. Furthermore, it is shown that a deterministic context-free language cannot be accepted reversibly if more than realtime is necessary for acceptance. Closure properties as well as decidability questions for reversible pushdown automata are studied. Finally, we show that the problem to decide whether a given nondeterministic or deterministic pushdown automaton is reversible is P-complete, whereas it is undecidable whether the language accepted by a given nondeterministic pushdown automaton is reversible.     

Sticker systems with complex structures

 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.     

基于h-距离的DNA编码序列设计

针对DNA编码序列设计问题,将其转换为带约束的多目标优化问题,在单链DNA集合中引入h-距离,构造了DNA序列间的共享函数,应用小种群遗传算法,对DNA编码序列设计问题进行求解。与已有结果比较,算法可以得到更好的DNA序列且计算效率较高。算法可用于DNA计算中编码序列的具体设计。     

On pseudoknot-bordered words and their properties

We study a generalization of the classical notions of bordered and unbordered words, motivated by biomolecular computing. DNA strands can be viewed as finite strings over the alphabet {A, G, C, T}, and are used in biomolecular computing to encode information. Due to the fact that A is Watson–Crick complementary to T and G to C, DNA single strands that are Watson–Crick complementary can bind to each other or to themselves forming so-called secondary structures. Most of these secondary structures are undesirable for biomolecular computational purposes since the strands they involve cannot further interact with other strands. This paper studies pseudoknot-bordered words, a mathematical formalization of pseudoknot-like inter- and intra-molecular structures. In this context, pseudoknot-unbordered words model DNA or RNA strands that will be free of such secondary structures. We obtain several properties of pseudoknot-bordered and -unbordered words. We also address following problem: Given a pseudoknot-unbordered word u, does ${\{u\}}^{+}$ consist of pseudoknot-unbordered words only? We show that this is not generally true. We find that a sufficient condition for ${\{u\}}^{+}$ to consist of pseudoknot-unbordered words only is that u be not primitive. All of our results hold for arbitrary antimorphic involutions, of which the DNA Watson–Crick complementarity function is a particular case.     

On regular realizability problems for context-free languages

We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.