Unavoidable Sets, Prefix Graphs and Regularity of Circular Splicing Languages

• Autorzy: Bonizzoni Paola , De Felice Clelia , Zaccagnino Rocco , Zizza Rosalba

Identyfikatory

DOI

10.3233/FI-2020-1873

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

circular splicing languages; formal languages; regular languages; unavoidable sets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 81--95
• Opis fizyczny: Bibliogr. 27 poz., rys., tab.

Twórcy

autor

Bonizzoni Paola

• Dipartimento di Informatica Sistemistica e Comunicazione, Università degli Studi di Milano Bicocca, Milano, Italy

autor

De Felice Clelia

• Dipartimento di Informatica, Università degli Studi di Salerno, Fisciano (SA), Italy

autor

Zaccagnino Rocco

• Dipartimento di Informatica, Università degli Studi di Salerno, Fisciano (SA), Italy

autor

Zizza Rosalba

• Dipartimento di Informatica, Università degli Studi di Salerno, Fisciano (SA), Italy

Bibliografia

• [1] Head T. Splicing schemes and DNA. In: Rozenberg G, Salomaa A (eds.), Lindenmayer systems : impacts on theoretical computer science, computer graphics, and developmental biology, pp. 371-383. Springer, 1992. doi:10.1007/978-3-642-58117-5_23.
• [2] Head T, Păun G, Pixton D. Language theory and molecular genetics: generative mechanisms suggested by DNA recombination. In: Rozenberg G, Salomaa A (eds.), Handbook of Formal Languages, pp. 295-360. Springer, 1997. doi:10.1007/978-3-662-07675-0_7.
• [3] Boasson L, Bonizzoni P, De Felice C, Fagnot I, Fici G, Zaccagnino R, Zizza R. Splicing Systems from Past to Future: Old and New Challenges. In: Discrete Mathematics and Computer Science. In Memoriam Alexandru Mateescu (1952-2005). 2014 pp. 51-76.
• [4] Bonizzoni P, De Felice C, Zizza R. A characterization of (regular) circular languages generated by monotone complete splicing systems. Theor. Comput. Sci., 2010. 411(48):4149-4161. doi:10.1016/j.tcs.2010.05.013.
• [5] De Felice C, Fici G, Zizza R. A characterization of regular circular languages generated by marked splicing systems. Theor. Comput. Sci., 2009. 410(47-49):4937-4960. doi:10.1016/j.tcs.2009.07.005.
• [6] Schützenberger MP. On the synchronizing properties of certain prefix codes. Information and Control, 1964. 7(1):23-36. URL https://doi.org/10.1016/S0019-9958(64)90232-3.
• [7] Choffrut C, Karhumáki J. Combinatorics on Words, in: Handbook of Formal Languages, Vol. 1. Springer Verlag, 1996. doi:10.1007/978-3-642-59136-5.
• [8] Higman G. Ordering by divisibility in abstract algebras. Proc. London Math. Soc., 1952. 2:326-336. URL https://doi.org/10.1112/plms/s3-2.1.326.
• [9] Ehrenfeucht A, Haussler D, Rozenberg G. On Regularity of Context-Free Languages. Theor. Comput. Sci., 1983. 27:311-332. doi:10.1016/0304-3975(82)90124-4.
• [10] Lothaire M. Algebraic Combinatorics on Words. Cambridge University Press, 2002. URL https://doi.org/10.1017/CBO9781107326019.
• [11] Perrin D, Restivo A. Words, in: Handbook of Enumerative Combinatorics. Discrete Mathematics and Its Applications Series, Chapman and Hall/CRC, 2015. ISBN-9781482220858, 1482220857.
• [12] Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley series in computer science. Addison-Wesley-Longman, second edition, 2001.
• [13] de Luca A, Varricchio S. Regularity and finiteness conditions, in: Handbook of Formal Languages, Vol. 1. Springer Verlag, 1996. doi:10.1007/978-3-642-59136-5_11.
• [14] Sakarovitch J. Elements of Automata Theory. Cambridge University Press, 2009. ISBN-10:0521844258, 13:978-0521844253.
• [15] Haussler D. Insertion languages. Inf. Sci., 1983. 31(1):77-89. doi:10.1016/0020-0255(83)90023-3.
• [16] Kari L. On insertion and deletion in formal languages, PhD Thesis, 1991.
• [17] Bonizzoni P, De Felice C, Fici G, Zizza R. On the regularity of circular splicing languages: a survey and new developments. Natural Computing, 2010. 9(2):397-420. doi:10.1007/s11047-009-9155-7.
• [18] Kudlek M. Languages of Cyclic Words. In: Jonoska N, Păun G, Rozenberg G (eds.), Aspects of Molecular Computing, Essays Dedicated to Tom Head on the Occasion of His 70th Birthday, volume 2950 of Lecture Notes in Computer Science. Springer, 2004 pp. 278-288. doi:10.1007/978-3-540-24635-0_20.
• [19] Berstel J, Boasson L, Fagnot I. Splicing systems and the Chomsky hierarchy. Theor. Comput. Sci., 2012. 436:2-22. doi:10.1016/j.tcs.2012.03.008.
• [20] Ceterchi R. An Algebraic Characterization of Semi-Simple Splicing. Fundam. Inform., 2006. 73(1-2):19-25.
• [21] Ceterchi R, Martín-Vide C, Subramanian KG. On Some Classes of Splicing Languages. In: Aspects of Molecular Computing, Essays Dedicated to Tom Head on the Occasion of His 70th Birthday. 2004 pp. 84-105. doi:10.1007/978-3-540-24635-0_6.
• [22] Siromoney R, Subramanian KG, Dare VR. Circular DNA and Splicing Systems. In: Parallel Image Analysis, Second International Conference, ICPIA ’92, Ube, Japan, December 21-23, 1992, Proceedings. 1992 pp. 260-273. doi:10.1007/3-540-56346-6_44.
• [23] Bonizzoni P, De Felice C, Mauri G, Zizza R. On the power of circular splicing. Discrete Applied Mathematics, 2005. 150(1-3):51-66. doi:10.1016/j.dam.2005.02.012.
• [24] De Felice C, Fici G, Zizza R. Marked Systems and Circular Splicing. In: Fundamentals of Computation Theory, 16th International Symposium, FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings. 2007 pp. 238-249. doi:10.1007/978-3-540-74240-1_21.
• [25] De Felice C, Zaccagnino R, Zizza R. Unavoidable Sets and Regularity of Languages Generated by (1, 3)-Circular Splicing Systems. In: Theory and Practice of Natural Computing - Third International Conference, TPNC 2014, Granada, Spain, December 9-11, 2014. Proceedings. 2014 pp. 169-180. doi:10.1007/978-3-319-13749-0_15.
• [26] De Felice C, Zaccagnino R, Zizza R. Unavoidable sets and circular splicing languages. Theor. Comput. Sci., 2017. 658:148-158. doi:10.1016/j.tcs.2016.09.008.
• [27] D’Alessandro F, Varricchio S. Avoidable Sets and Well Quasi-Orders. In: Developments in Language Theory, 8th International Conference, DLT 2004, Auckland, New Zealand, December 13-17, 2004, Proceedings. 2004 pp. 139-150. doi:10.1007/978-3-540-30550-7_12.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).