6533b7cffe1ef96bd12586df

RESEARCH PRODUCT

Marked systems and circular splicing

Rosalba ZizzaGabriele FiciClelia De Felice

subject

Discrete mathematicsProperty (programming)Structure (category theory)Molecular computingCircular wordDecidabilityRegular languageIf and only ifRNA splicingFormal languageSplicing systemFormal languageGenerative grammarAutomata theoryMathematics

description

Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. In this paper we introduce a special class of finite circular splicing 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 show that we can decide whether a regular circular language is generated by a marked system and we characterize the structure of these regular circular languages.

yearjournalcountryeditionlanguage
2007-01-01
http://www.scopus.com/inward/record.url?eid=2-s2.0-38149090879&partnerID=MN8TOARS