View Related Documents

Abstract

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.
Partially supported by MIUR Project “Automi e Linguaggi Formali: aspetti matematici e applicativi” (2005), by 60 % Project “Linguaggi formali e codici: problemi classici e modelli innovativi” (University of Salerno, 2005) and by 60 % Project “Linguaggi formali e codici a lunghezza variabile: proprietà strutturali e nuovi modelli di rappresentazione” (University of Salerno, 2006).

Fulltext Preview

Image of the first page of the fulltext document