{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T06:54:41Z","timestamp":1777100081687,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642180972","type":"print"},{"value":"9783642180989","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-18098-9_12","type":"book-chapter","created":{"date-parts":[[2011,2,4]],"date-time":"2011-02-04T13:56:14Z","timestamp":1296827774000},"page":"105-114","source":"Crossref","is-referenced-by-count":6,"title":["Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Volker","family":"Diekert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steffen","family":"Kopecki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Baker, B.S., Book, R.V.: Reversal-bounded multi-pushdown machines. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 207\u2013211 (1972)","DOI":"10.1109\/SWAT.1972.21"},{"key":"12_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-73235-5","volume-title":"Rational series and their languages","author":"J. Berstel","year":"1988","unstructured":"Berstel, J., Reutenauer, C.: Rational series and their languages. Springer, New York (1988)"},{"issue":"3","key":"12_CR3","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/j.aam.2005.01.002","volume":"35","author":"T. Ceccherini-Silberstein","year":"2005","unstructured":"Ceccherini-Silberstein, T.: On the growth of linear languages. Advances in Applied Mathematics\u00a035(3), 243\u2013253 (2005)","journal-title":"Advances in Applied Mathematics"},{"key":"12_CR4","unstructured":"Cheptea, D., Martin-Vide, C., Mitrana, V.: A new operation on words suggested by DNA biochemistry: Hairpin completion. Transgressive Computing, 216\u2013228 (2006)"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Deaton, R., Murphy, R., Garzon, M., Franceschetti, D., Stevens, S.: Good encodings for DNA-based solutions to combinatorial problems. In: Proc. of DNA-Based computers DIMACS Series, vol.\u00a044, pp. 247\u2013258 (1998)","DOI":"10.1090\/dimacs\/044\/20"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-642-03466-4_11","volume-title":"Theoretical Aspects of Computing - ICTAC 2009","author":"V. Diekert","year":"2009","unstructured":"Diekert, V., Kopecki, S., Mitrana, V.: On the hairpin completion of regular languages. In: Leucker, M., Morgan, C. (eds.) ICTAC 2009. LNCS, vol.\u00a05684, pp. 170\u2013184. Springer, Heidelberg (2009)"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Diekert, V., Kopecki, S.: Complexity Result and the Growths of Hairpin Completions of Regular Languages. Technical Report Computer Science 2010\/04, University of Stuttgart (June 2010)","DOI":"10.1007\/978-3-642-18098-9_12"},{"key":"12_CR8","unstructured":"Garzon, M., Deaton, R., Neathery, P., Murphy, R., Franceschetti, D., Stevens, E.: On the encoding problem for DNA computing. In: The Third DIMACS Workshop on DNA-Based Computing, pp. 230\u2013237 (1997)"},{"key":"12_CR9","unstructured":"Garzon, M., Deaton, R., Nino, L., Stevens Jr., S., Wittner, M.: Genome encoding for DNA computing. In: Proc. Third Genetic Programming Conference, pp. 684\u2013690 (1998)"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-540-85780-8_27","volume-title":"Developments in Language Theory","author":"P. Gawrychowski","year":"2008","unstructured":"Gawrychowski, P., Krieger, D., Rampersad, N., Shallit, J.: Finding the growth rate of a regular or context-free language in polynomial time. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol.\u00a05257, pp. 339\u2013358. Springer, Heidelberg (2008)"},{"issue":"1","key":"12_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01691341","volume":"2","author":"S.A. Greibach","year":"1968","unstructured":"Greibach, S.A.: A note on undecidable properties of formal languages. Mathematical Systems Theory\u00a02(1), 1\u20136 (1968)","journal-title":"Mathematical Systems Theory"},{"key":"12_CR12","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ulman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/11753681_12","volume-title":"DNA Computing","author":"L. Kari","year":"2006","unstructured":"Kari, L., Konstantinidis, S., Losseva, E., Sos\u00edk, P., Thierrin, G.: Hairpin structures in DNA words. In: Carbone, A., Pierce, N.A. (eds.) DNA 2005. LNCS, vol.\u00a03892, pp. 158\u2013170. Springer, Heidelberg (2006)"},{"issue":"3-4","key":"12_CR14","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00236-007-0041-4","volume":"44","author":"L. Kari","year":"2007","unstructured":"Kari, L., Mahalingam, K., Thierrin, G.: The syntactic monoid of hairpin-free languages. Acta Inf.\u00a044(3-4), 153\u2013166 (2007)","journal-title":"Acta Inf."},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0019-9958(70)90105-1","volume":"16","author":"W. Kuich","year":"1970","unstructured":"Kuich, W.: On the entropy of context-free languages. Information and Control\u00a016, 173\u2013200 (1970)","journal-title":"Information and Control"},{"issue":"4-5","key":"12_CR16","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.tcs.2008.09.049","volume":"410","author":"F. Manea","year":"2009","unstructured":"Manea, F., Mitrana, V., Yokomori, T.: Two complementary operations inspired by the DNA hairpin formation: Completion and reduction. Theor. Comput. Sci.\u00a0410(4-5), 417\u2013425 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR17","volume-title":"Computatational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computatational Complexity. Addison Wesley, Reading (1994)"},{"issue":"5469","key":"12_CR18","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1126\/science.288.5469.1223","volume":"288","author":"K. Sakamoto","year":"2000","unstructured":"Sakamoto, K., Gouzu, H., Komiya, K., Kiga, D., Yokoyama, S., Yokomori, T., Hagiya, M.: Molecular Computation by DNA Hairpin Formation. Science\u00a0288(5469), 1223\u20131226 (2000)","journal-title":"Science"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-18098-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,18]],"date-time":"2021-11-18T14:57:52Z","timestamp":1637247472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-18098-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642180972","9783642180989"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-18098-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}