Unavoidable sets and circular splicing languages

详细信息    查看全文

• 作者：Clelia De Felice ; ^{defelice@dia.unisa.it} ; Rocco Zaccagnino ; Rosalba Zizza
• 关键词：Regular languages ; Circular splicing systems ; Unavoidable sets
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：7 January 2017
• 年：2017
• 卷：658
• 期：part_PA
• 页码：148-158
• 全文大小：431 K
• 卷排序：658

文摘

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)(1,3)-CSSH systems). When R=A×AR=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)(1,3)-CSSH systems.