{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T18:42:22Z","timestamp":1743014542413,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540888680"},{"type":"electronic","value":"9783540888697"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-540-88869-7_17","type":"book-chapter","created":{"date-parts":[[2009,8,12]],"date-time":"2009-08-12T21:41:55Z","timestamp":1250113315000},"page":"313-329","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finite Splicing: Generative Capacity, New\u00a0Models and Complexity Aspects"],"prefix":"10.1007","author":[{"given":"Paola","family":"Bonizzoni","sequence":"first","affiliation":[]},{"given":"Remco","family":"Loos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,8,13]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0020-0190(92)90198-5","volume":"43","author":"J-C Birget","year":"1992","unstructured":"Birget J-C (1992) Intersection and union of regular languages and state complexity. Inf Process Lett 43:185\u2013190","journal-title":"Inf Process Lett"},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1051\/ita:2004010","volume":"38","author":"P Bonizzoni","year":"2004","unstructured":"Bonizzoni P, De Felice C, Mauri G, Zizza R (2004) Circular splicing and regularity. Theor Inform Appl 38:189\u2013228","journal-title":"Theor Inform Appl"},{"issue":"3","key":"17_CR3","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1016\/j.dam.2005.06.008","volume":"154","author":"P Bonizzoni","year":"2006","unstructured":"Bonizzoni P, De Felice C, Mauri G, Zizza R (2006) Linear splicing and syntactic monoid. Discrete Appl Math 154(3):452\u2013470","journal-title":"Discrete Appl Math"},{"issue":"1\u20133","key":"17_CR4","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.dam.2005.02.012","volume":"150","author":"P Bonizzoni","year":"2005","unstructured":"Bonizzoni P, De Felice C, Mauri G, Zizza R (2005) On the power of circular splicing. Discrete Appl Math 150(1\u20133):51\u201366","journal-title":"Discrete Appl Math"},{"key":"17_CR5","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/3-540-45005-X_7","volume-title":"Proceedings of the DLT 2002","author":"P Bonizzoni","year":"2003","unstructured":"Bonizzoni P, De Felice C, Mauri G, Zizza R (2003) Decision problems on linear and circular splicing. In: Ito M, Toyama M (eds) Proceedings of the DLT 2002. Lecture notes in computer science, vol\u00a02450. Springer, Berlin, pp 78\u201392"},{"key":"17_CR6","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/3-540-45007-6_10","volume-title":"Proceedings of the DLT 2003","author":"P Bonizzoni","year":"2003","unstructured":"Bonizzoni P, De Felice C, Mauri G, Zizza R (2003) Regular languages generated by reflexive finite linear splicing systems. In: Proceedings of the DLT 2003. Lecture notes in computer science, vol\u00a02710. Springer, Berlin, pp 134\u2013145"},{"issue":"1\u20133","key":"17_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.tcs.2004.12.033","volume":"334","author":"P Bonizzoni","year":"2005","unstructured":"Bonizzoni P, De Felice C, Zizza R (2005) The structure of reflexive regular splicing languages via Sch\u00fctzenberger constants. Theor Comput Sci 334(1\u20133):71\u201398","journal-title":"Theor Comput Sci"},{"issue":"4","key":"17_CR8","first-page":"295","volume":"1","author":"P Bonizzoni","year":"1998","unstructured":"Bonizzoni P, Ferretti C, Mauri G (1998) Splicing systems with marked rules. Rom J Inf Sci Technol 1(4):295\u2013306","journal-title":"Rom J Inf Sci Technol"},{"issue":"6","key":"17_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0020-0190(01)00139-9","volume":"79","author":"P Bonizzoni","year":"2001","unstructured":"Bonizzoni P, Ferretti C, Mauri G, Zizza R (2001) Separating some splicing models. Inf Process Lett 79(6):255\u2013259","journal-title":"Inf Process Lett"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Bonizzoni P, Mauri G (2006) A decision procedure for reflexive regular splicing languages. Dev Lang Theory 315\u2013326","DOI":"10.1007\/11779148_29"},{"key":"17_CR11","volume-title":"Computing with cells and atoms: an introduction to quantum, DNA and membrane computing","author":"CS Calude","year":"2001","unstructured":"Calude CS, P\u0103un Gh (2001) Computing with cells and atoms: an introduction to quantum, DNA and membrane computing. Taylor & Francis, London"},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0166-218X(91)90054-Z","volume":"31","author":"K Culik","year":"1991","unstructured":"Culik K, Harju T (1991) Splicing semigroups of dominoes and DNA. Discrete Appl Math 31:261\u2013277","journal-title":"Discrete Appl Math"},{"key":"17_CR13","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/S0019-9958(80)90180-1","volume":"44","author":"A De Luca","year":"1980","unstructured":"De Luca A, Restivo A (1980) A characterization of strictly locally testable languages and its application to semigroups of free semigroup. Inf Control 44:300\u2013319","journal-title":"Inf Control"},{"key":"17_CR14","unstructured":"Goode E (1999) Constants and splicing systems. PhD thesis, Binghamton University"},{"key":"17_CR15","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1016\/j.dam.2006.10.006","volume":"155","author":"E Goode","year":"2007","unstructured":"Goode E, Pixton D (2007) Recognizing splicing languages: syntactic monoids and simultaneous pumping. Discrete Appl Math 155:988\u20131006","journal-title":"Discrete Appl Math"},{"key":"17_CR16","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1016\/S0092-8240(87)90018-8","volume":"49","author":"T Head","year":"1987","unstructured":"Head T (1987) Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviours. Bull Math Biol 49:737\u2013759","journal-title":"Bull Math Biol"},{"key":"17_CR17","volume-title":"Computing with bio-molecules. Theory and experiments","author":"T Head","year":"1998","unstructured":"Head T (1998) Splicing languages generated with one sided context. In: P\u0103un Gh (ed) Computing with bio-molecules. Theory and experiments. Springer, Singapore"},{"key":"17_CR18","first-page":"295","volume-title":"Handbook of formal languages","author":"T Head","year":"1996","unstructured":"Head T, P\u0103un Gh, Pixton D (1996) Language theory and molecular genetics: generative mechanisms suggested by DNA recombination. In: Rozenberg G, Salomaa A (eds) Handbook of formal languages, vol\u00a02. Springer, Berlin, pp 295\u2013360"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1137\/S0097539794263890","volume":"26","author":"SM Kim","year":"1997","unstructured":"Kim SM (1997) Computational modeling for genetic splicing systems. SIAM J Comput 26:1284\u20131309","journal-title":"SIAM J Comput"},{"key":"17_CR20","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2006.03.002","volume":"358","author":"R Loos","year":"2006","unstructured":"Loos R (2006) An alternative definition of splicing. Theor Comput Sci 358:75\u201387","journal-title":"Theor Comput Sci"},{"issue":"4","key":"17_CR21","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1142\/S0129054108005978","volume":"19","author":"R Loos","year":"2008","unstructured":"Loos R, Malcher A, Wotschke D (2008) Descriptional complexity of splicing systems. Int J Found Comput Sci 19(4):813\u2013826","journal-title":"Int J Found Comput Sci"},{"key":"17_CR22","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1007\/11844297_78","volume-title":"PPSN IX","author":"R Loos","year":"2006","unstructured":"Loos R, Mart\u00edn-Vide C, Mitrana V (2006) Solving SAT and HPP with accepting splicing systems. In: PPSN IX. Lecture notes in computer science, vol\u00a04193. Springer, Berlin, pp 771\u2013777"},{"issue":"4","key":"17_CR23","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1080\/00207160701228101","volume":"84","author":"R Loos","year":"2007","unstructured":"Loos R, Mitrana V (2007) Non-preserving splicing with delay. Int J Comput Math 84(4):427\u2013436","journal-title":"Int J Comput Math"},{"key":"17_CR24","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.tcs.2007.06.010","volume":"386","author":"R Loos","year":"2007","unstructured":"Loos R, Ogihara M (2007) Complexity theory for splicing systems. Theor Comput Sci 386:132\u2013150","journal-title":"Theor Comput Sci"},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"Loos R, Ogihara M (2007) Time and space complexity for splicing systems. Theory Comput Syst (in press)","DOI":"10.1007\/s00224-008-9161-7"},{"issue":"2","key":"17_CR26","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/S0304-3975(96)00082-5","volume":"168","author":"Gh P\u0103un","year":"1996","unstructured":"P\u0103un Gh, Rozenberg G, Salomaa A (1996) Computing by splicing. Theor Comput Sci 168(2):321\u2013336","journal-title":"Theor Comput Sci"},{"key":"17_CR27","volume-title":"DNA computing, new computing paradigms","author":"G P\u0103un","year":"1998","unstructured":"P\u0103un G, Rozenberg G, Salomaa A (1998) DNA computing, new computing paradigms. Springer, Berlin"},{"key":"17_CR28","first-page":"1","volume-title":"Handbook of theoretical computer science","author":"D Perrin","year":"1990","unstructured":"Perrin D (1990) Finite automata. In: Van Leeuwen J (ed) Handbook of theoretical computer science, vol B. Elsevier, Amsterdam, pp 1\u201357"},{"key":"17_CR29","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0166-218X(95)00079-7","volume":"69","author":"D Pixton","year":"1996","unstructured":"Pixton D (1996) Regularity of splicing languages. Discrete Appl Math 69:101\u2013124","journal-title":"Discrete Appl Math"},{"key":"17_CR30","first-page":"245","volume":"15","author":"MP Sch\u00fctzenberger","year":"1975","unstructured":"Sch\u00fctzenberger MP (1975) Sur certaines op\u00e9rations de fermeture dans le langages rationnels. Symp Math 15:245\u2013253","journal-title":"Symp Math"},{"key":"17_CR31","doi-asserted-by":"crossref","unstructured":"Stockmeyer L, Meyer AR (1973) Word problems requiring exponential time: preliminary report. In: Fifth annual ACM symposium on theory of computing, pp\u00a01\u20139","DOI":"10.1145\/800125.804029"},{"key":"17_CR32","unstructured":"Verlan S, Zizza R (2003) 1-splicing vs. 2-splicing: separating results. In: Proceedings of Words03, Turku, Finland, pp\u00a0320\u2013331"},{"key":"17_CR33","unstructured":"Verlan S (2004) Head systems and applications to bio-informatics. PhD thesis, University of Metz"}],"container-title":["Natural Computing Series","Algorithmic Bioprocesses"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88869-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T18:55:41Z","timestamp":1676055341000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-88869-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783540888680","9783540888697"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88869-7_17","relation":{},"ISSN":["1619-7127"],"issn-type":[{"type":"print","value":"1619-7127"}],"subject":[],"published":{"date-parts":[[2009]]},"assertion":[{"value":"13 August 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}