Generalized marked systems

The circular splicing operation has been introduced by T. Head to model a specific recombinant behaviour of circular DNA, carrying on the investigation initiated with linear splicing. This operation allows us to define a computing (circular language generating) device, called a circular splicing system. A circular splicing system consists of a finite alphabet, an initial set of circular words and a set of rules. The circular language generated by it, named circular splicing language, is the smallest language containing the initial set which is closed under the circular splicing operation defined by the rules. The computational power of circular splicing systems has been thoroughly investigated but some interesting problems are still open. In this paper, we focus on the still unknown relations between regular circular languages and circular splicing systems with a finite initial set and a finite set of rules represented by a pair of letters ((1,3)-CSSH systems). In particular, we give results for special subclasses of them, named generalized marked systems and transitive generalized marked systems. As a main result, we prove that a transitive generalized marked system such that every pair of different letters is a rule generates a regular circular language if and only if it satisfies a special (decidable) property. As a consequence, we are able to characterize the structure of these regular circular languages.