1,720,995 research outputs found
A characterization of (regular) circular languages generated by monotone complete splicing systems
No full textCircular 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
Hybrid and generalized marked systems
No full textThe circular splicing operation is a language-theoretic operation introduced by Head to model biological phenomena on circular DNA and RNAs. It acts on pairs of circular words under conditions defined by a set of rules. A circular splicing system S is defined by giving an initial set of circular words and a set of rules. S represents a circular language from a generative point of view (splicing language). There are open questions related to the computational power of these systems. For instance, a characterization of circular splicing systems generating regular circular languages is still lacking as well as a characterization of the structure of the regular splicing languages. In this paper we give results about these questions for a special class of hybrid systems named generalized marked systems
Unavoidable sets and circular splicing languages
No full textCircular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. In this paper, we focus on the still unknown relations between regular languages and circular splicing systems with a finite initial set and a finite set R of rules represented by a pair of letters ((1,3)-CSSH systems). When R = A x A, it is known that the set of all words corresponding to the splicing language belongs to the class of pure unitary languages, introduced by Ehrenfeucht, Haussler, Rozenberg in 1983. They also provided a characterization of the regular pure unitary languages, based on the notions of unavoidable sets and well quasi-orders. We partially extend these notions and their results in the more general framework
of the (1,3)-CSSH systems
The structure of reflexive regular splicing languages via Schutzenberger constants
No full textThe 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 Schützenberger, once again intervenes
On the power of circular splicing
No full textSplicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. Via automata properties we show that it is decidable whether a regular language L on a one-letter alphabet is generated by a finite (Paun) circular splicing system: L has this property if and only if there is a unique final state q_n on the closed path in the transition diagram of the minimal finite state automaton A recognizing L and q_n is idempotent (i.e., \delta(q_n, a^n) = q_n). This result is obtained by an already known characterization of the unary languages L generated by a finite (Paun) circular splicing system and, in turn, allows us to simplify the description of the structure of L. This description is here extended to the larger class of the uniform languages, i.e., the circularizations of languages with the form A^J =\cup_{j∈J} A^j , J being a subset of the set N of the nonnegative integers. Finally, we exhibit a regular circular language, namely ∼((A2)* ∪ (A3)*), that cannot be generated by any finite circular splicing system
Linear splicing and syntactic monoid
No full textSplicing 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]_1L_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] ∪ {1}, 1 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
On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties
No full textThe Lyndon factorization of a word has been largely studied and recently variants of it have been introduced and investigated with different motivations. In particular, the canonical inverse Lyndon factorization ICFL(w) of a word w, previously introduced, maintains the main properties of the Lyndon factorization since it can be computed in linear time and it is uniquely determined. In this paper we investigate new properties of this factorization with the aim of exploring their use in some classical queries on w.
The main property we prove is related to a classical query on words. We prove that there are relations between the length of the longest common prefix (or longest common extension) lcp(x,y) of two different suffixes x,y of a word w and the maximum length M of two consecutive factors of ICFL(w). More precisely, M is an upper bound on the length of lcp(x,y). A main tool used in the proof of the above result is a property that we state for factors m_i with nonempty borders in ICFL(w): a nonempty border of m_i cannot be a prefix of the next factor m_{i+1}.
Another interesting result relates sorting of global suffixes, i.e., suffixes of a word w, and sorting of local suffixes, i.e., suffixes of products of factors in ICFL(w).
This is the counterpart for ICFL(w) of the compatibility property, proved for the Lyndon factorization by other authors. Roughly, the compatibility property allows us to extend the mutual order between suffixes of products of the (inverse) Lyndon factors to the suffixes of the whole word.
The last property we prove focuses on the Lyndon factorizations of a word and its factors. It suggests that the Lyndon factorizations of two words sharing a common overlap could be used to capture the common overlap of these two words
- …
