6533b7d1fe1ef96bd125cde3

RESEARCH PRODUCT

Unavoidable sets and circular splicing languages

Clelia De FeliceRocco ZaccagninoRosalba Zizza

subject

Discrete mathematicsClass (set theory)General Computer ScienceRegular languages; Circular splicing systems; Unavoidable sets0102 computer and information sciences02 engineering and technologyRegular languagesCharacterization (mathematics)01 natural sciencesUnitary stateTheoretical Computer ScienceFocus (linguistics)Set (abstract data type)CombinatoricsRegular language010201 computation theory & mathematicsUnavoidable sets0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingFinite setGenerative grammarCircular splicing systemsMathematics

description

Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. In this paper, we focus on the still unknown relations between regular languages and circular splicing systems with a finite initial set and a finite set R of rules represented by a pair of letters ( ( 1 , 3 ) -CSSH systems). When R = A × A , it is known that the set of all words corresponding to the splicing language belongs to the class of pure unitary languages, introduced by Ehrenfeucht, Haussler, Rozenberg in 1983. They also provided a characterization of the regular pure unitary languages, based on the notions of unavoidable sets and well quasi-orders. We partially extend these notions and their results in the more general framework of the ( 1 , 3 ) -CSSH systems.

yearjournalcountryeditionlanguage
2017-01-01Theoretical Computer Science
https://doi.org/10.1016/j.tcs.2016.09.008