Search

Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. Some unanswered questions are related to the computational power of such systems, and finding a characterization of the class of circular languages generated by circular splicing systems is still an open problem. In this paper we solve this problem for monotone complete systems, which are finite circular splicing systems with rules of a simpler form. We show that a circular language L is generated by a monotone complete system if and only if the set Lin(L) of all words corresponding to L is a pure unitary language generated by a set closed under the conjugacy relation. The class of pure unitary languages was introduced by A. Ehrenfeucht, D. Haussler, G. Rozenberg in 1983, as a subclass of the class of context-free languages, together with a characterization of regular pure unitary languages by means of a decidable property. As a direct consequence, we characterize (regular) circular languages generated by monotone complete systems. We can also decide whether the language generated by a monotone complete system is regular. Finally, we point out that monotone complete systems have the same computational power as finite simple systems, an easy type of circular splicing system defined in the literature from the very beginning, when only one rule of a specific type is allowed. From our results on monotone complete systems, it follows that finite simple systems generate a class of languages containing non-regular languages, showing the incorrectness of a longstanding result on simple systems.

Circular splicing has been introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we focus on the relationship between regular circular languages and languages generated by finite circular splicing systems. We survey the known results towards a characterization of the intersection between these two classes and provide new contributions on the open problem of finding this characterization. First, we exhibit a non-regular circular language generated by a circular simple system thus disproving a known result in this area. Then we give new results related to a restrictive class of circular splicing systems, the marked systems. Precisely, we review in a graph theoretical setting the recently obtained characterization of marked systems generating regular circular languages. In particular, we define a slight variant of marked systems, that is the g-marked systems, and we introduce the graph associated with a g-marked system. We show that a g-marked system generates a regular circular language if and only if its associated graph is a cograph. Furthermore, we prove that the class of g-marked systems generating regular circular languages is closed under a complement operation applied to systems. We also prove that marked systems with self-splicing generate only regular circular languages. © 2009 Springer Science+Business Media B.V.

Splicing systems were introduced by Head in 1987 as a formal counterpart of a biological mechanism of DNA recombination under the action of restriction and ligase enzymes. Despite the intensive studies on linear splicing systems, some elementary questions about their computational power are still open. In particular, in this paper we face the problem of characterizing the proper subclass of regular languages which are generated by finite (Paun) linear splicing systems. We introduce here the class of marker languages L, i.e., regular languages with the form L = L-1 [x](1) L-2, where L-1, L-2 are regular languages, [x] is a syntactic congruence class satisfying special conditions and [x](1) is either equal to [x] or equal to [x] boolean OR {1}, I being the empty word. Using classical properties of formal language theory, we give an algorithm which allows us to decide whether a regular language is a marker language. Furthermore, for each marker language L we exhibit a finite Paun linear splicing system and we prove that this system generates L. (c) 2005 Elsevier B.V. All rights reserved.

A splicing operation, as a model of gene splicing, is introduced as an operator on strings. A splicing system is defined by giving an initial language I and a set of special words or rules R. The set I is then transformed by repeated applications of the splicing operation. Depending on the definition of the splicing operation we refer to, we have different definitions of linear splicing systems and of circular splicing systems. Here, we focus on finite splicing systems that are closest to the biological process. Indeed, they are defined by a finite set of rules and a finite set of initial strings. We discuss results concerning both circular and linear finite splicing systems

The splicing operation was introduced in 1987 by Head as a mathematical model of the recombination of DNA molecules under the influence of restriction and ligases enzymes. This operation allows us to define a computing (language generating) device, called a splicing system. Other variants of this original definition were also proposed by Paun and Pixton respectively. The computational power of splicing systems has been thoroughly investigated. Nevertheless, an interesting problem is still open, namely the characterization of the class of regular languages generated by finite splicing systems. In this paper, we will solve the problem for a special class of finite splicing systems, termed reflexive splicing systems, according to each of the definitions of splicing given by Paun and Pixton. This special class of systems contains, in perticular, finite Head splicing systems. The notion of a constant, given by Schutzenberger, once again intervenes. © 2005 Elsevier B.V. All rights reserved.

Circular splicing has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we restrict our study to the relationship between regular circular languages and languages generated by finite circular splicing systems and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages X*, called here star languages, which are closed under conjugacy relation and with X being a regular language. Using automata theory and combinatorial techniques on words, we show that for a subclass of star languages the corresponding circular languages are (Paun) circular splicing languages. For example, star languages belong to this subclass when X* is a free monoid or X is a finite set. We also prove that each (Paun) circular splicing language L over a one-letter alphabet has the form L=X+ boolean ORY, with X, Y finite sets satisfying particular hypotheses. Cyclic and weak cyclic languages, which will be introduced in this paper, show that this result does not hold when we increase the size of alphabets, even if we restrict ourselves to regular languages.

We report 2 elderly patients with facial lentigo maligna who experienced complete regression, both clinically and histopathologically, after once-daily topical treatment with tazarotene 0.1% gel for 6 to 8 months. After a follow-up period of 18 and 30 months, no recurrence was observed. We believe that tazarotene might be considered as an alternative medical approach in selected patients with lentigo maligna.

Splicing systems are a generative device inspired by a cut and paste phenomenon on DNA molecules, introduced by Head in 1987 and subsequently defined with slight variations also by Paun and Pixton respectively.We will face the problem of characterizing the class of regular languages generated by finite splicing systems. We will solve this problem for the special class of the reflexive finite splicing systems. As a byproduct, we give a characterization of the regular languages generated by finite Head splicing systems. As in already known results, the notion of constant, given by Schuetzenberger, intervenes.

We will consider here the splicing systems, generative devicesinspired by cut and paste phenomena on DNA molecules under the actionof restriction and ligase enzymes. A DNA strand can be viewed as a stringover a four letter alphabet (the four deoxyribonucleotides), therefore wecan model DNA computation within the framework of formal languagetheory. In spite of a vast literature on splicing systems, briefly surveyedhere, a few problems related to their computational power are still open.We intend to evidence how classical techniques and concepts in automatatheory are a legitimate tool for investigating some of these problems.

Circular splicing has been very recently introduced to model a speci fic recombinant behaviour of circular DNA, carrying on the investigation initiated with linear splicing. In this paper we restrict ourselves to the relationship between circular regular languages and circular splicing languages. We provide partial results towards a characterization of the class of circular regular languages generated by finite circular splicing systems. Using automata theory and combinatorial techniques on words, we show that for a subclass of star languages the corresponding circular languages are circular (Paun) splicing languages.