Name
Abstract | ||
|---|---|---|
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 = L1[X]1L2, where L1, L2 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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.dam.2005.06.008 | Discrete Applied Mathematics |
Keywords | Field | DocType |
automata,marker language,molecular computing,paun linear splicing system,regular language,formal counterpart,dna recombination,syntactic congruence class,syntactic monoid,formal language theory,regular languages,linear splicing system,form l,splicing system,formal language,enzyme,satisfiability | Discrete mathematics,Combinatorics,Formal language,Linear system,Philosophy of language,Monoid,Syntactic monoid,Regular language,Congruence (geometry),Syntax,Mathematics | Journal |
Volume | Issue | ISSN |
154 | 3 | Discrete Applied Mathematics |
Citations | PageRank | References |
4 | 0.48 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paola Bonizzoni | 1 | 502 | 52.23 |
| C de Felice | 2 | 28 | 3.03 |
| G. Mauri | 3 | 19 | 2.54 |
| R. Zizza | 4 | 16 | 1.47 |