Affiliations: [a] Dipartimento di Informatica Sistemistica e Comunicazione, Università degli Studi di Milano Bicocca, Milano, Italy. [email protected] | [b] Dipartimento di Informatica, Università degli Studi di Salerno, Fisciano (SA), Italy. [email protected], [email protected], [email protected]
Correspondence:
[*]
Address for correspondence: Dipartimento di Informatica, Università degli Studi di Salerno, Via Giovanni Paolo II 132, 84084 Fisciano (SA), Italy
Abstract: Circular splicing systems are a mathematical model, 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. A circular splicing language is a language generated by a circular splicing system. An open problem is to characterize regular circular splicing languages and the corresponding circular splicing systems. In this framework an important role is played by unavoidable sets. These sets have been considered in several contexts. In particular, Ehrenfeucht, Haussler and Rozenberg (1983) proved the following generalization of a famous Higman’s theorem: the quasi-order induced by insertions of words from a fixed finite set is a well-quasi-order if and only if the finite set is unavoidable. In this paper we survey the known relations between unavoidable sets and regular circular languages. Motivated by these connections we give an alternative and simpler proof of the Ehrenfeucht, Haussler and Rozenberg result. Our proof is strongly based on a known characterization of unavoidable sets in terms of graphs associated with them.
Keywords: Formal languages, Regular languages, Unavoidable sets, Circular splicing languages
