6533b82ffe1ef96bd1295d74
RESEARCH PRODUCT
A characterization of regular circular languages generated by marked splicing systems
Gabriele FiciRosalba ZizzaClelia De Felicesubject
Pure mathematicsGeneral Computer ScienceMolecular computing Splicing systems Circular words Formal languages Automata theoryMolecular computingQuantitative Biology::GenomicsDecidabilityTheoretical Computer ScienceSet (abstract data type)Formal languagesRegular languageFormal languageRNA splicingAutomata theorySplicing systemsCircular wordsFinite setAlgorithmWord (computer architecture)Automata theoryMathematicsComputer Science(all)description
AbstractSplicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. A splicing system is defined by giving an initial set I and a set R of rules. Some unanswered questions are related to the computational power of circular splicing systems. In particular, a still open question is to find a characterization of circular languages generated by finite circular splicing systems (i.e., circular splicing systems with both I and R finite sets). In this paper we introduce a special class of the latter systems named marked systems. We prove that a marked system S generates a regular circular language if and only if S satisfies a special (decidable) property. As a consequence, we are able to characterize the structure of these regular circular languages.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2009-11-01 |