{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:55:57Z","timestamp":1725584157575},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642212536"},{"type":"electronic","value":"9783642212543"}],"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-21254-3_29","type":"book-chapter","created":{"date-parts":[[2011,5,27]],"date-time":"2011-05-27T05:38:04Z","timestamp":1306474684000},"page":"366-377","source":"Crossref","is-referenced-by-count":2,"title":["Planarity of Knots, Register Automata and LogSpace Computability"],"prefix":"10.1007","author":[{"given":"Alexei","family":"Lisitsa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafiq","family":"Saleh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Abramsky, S.: Temperley-Lieb Algebra: From Knot Theory to Logic and Computation via Quantum Mechanics. Mathematics of Quantum Computation and Quantum Technology (2007)","DOI":"10.1201\/9781584889007.ch15"},{"key":"29_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-540-74240-1_9","volume-title":"Fundamentals of Computation Theory","author":"H. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, H., Schwentick, T.: On Notions of Regularity for Data Languages. In: Csuhaj-Varj\u00fa, E., \u00c9sik, Z. (eds.) FCT 2007. LNCS, vol.\u00a04639, pp. 88\u201399. Springer, Heidelberg (2007)"},{"issue":"4","key":"29_CR3","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1142\/S0218216593000209","volume":"2","author":"G. Cairns","year":"1993","unstructured":"Cairns, G., Elton, D.: The planarity problem for signed Gauss words. Journal of Knot Theory and its Ramifications\u00a02(4), 359\u2013367 (1993)","journal-title":"Journal of Knot Theory and its Ramifications"},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1142\/S0218216596000102","volume":"5","author":"G. Cairns","year":"1996","unstructured":"Cairns, G., Elton, D.: The Planarity Problem II. Journal of Knot Theory and its Ramifications\u00a05, 137\u2013144 (1996)","journal-title":"Journal of Knot Theory and its Ramifications"},{"issue":"2","key":"29_CR5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/PL00009461","volume":"22","author":"H. Fraysseix De","year":"1999","unstructured":"De Fraysseix, H., Ossona de Mendez, P.: On a characterization of Gauss codes. Discrete and Computational Geometry\u00a022(2), 287\u2013295 (1999)","journal-title":"Discrete and Computational Geometry"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF02401740","volume":"67","author":"M. Dehn","year":"1936","unstructured":"Dehn, M.: Uber kombinatorische topologie. Acta Math.\u00a067, 123\u2013168 (1936)","journal-title":"Acta Math."},{"key":"29_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/11549345_2","volume-title":"Mathematical Foundations of Computer Science 2005","author":"R. Freivalds","year":"2005","unstructured":"Freivalds, R.: Knot Theory, Jones Polynomial and Quantum Computing. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 15\u201325. Springer, Heidelberg (2005)"},{"key":"29_CR8","unstructured":"Gauss, C.: Werke. Band 8. Teubner (1900)"},{"issue":"2","key":"29_CR9","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1145\/301970.301971","volume":"46","author":"J. Hass","year":"1999","unstructured":"Hass, J., Lagarias, J., Pippenger, N.: The computational complexity of knot and link problems. Journal of the ACM (JACM)\u00a046(2), 185\u2013211 (1999)","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"29_CR10","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"M. Kaminski","year":"1994","unstructured":"Kaminski, M., Francez, N.: Finite-memory automata. Theoretical Computer Science\u00a0134(2), 329\u2013363 (1994)","journal-title":"Theoretical Computer Science"},{"key":"29_CR11","unstructured":"Kari, J., Niemi, V.: Morphic Images of Gauss Codes. In: Developments in Language Theory, pp. 144\u2013156 (1993)"},{"key":"29_CR12","unstructured":"Kauffman, L.: Virtual knot theory. Arxiv Preprint Math. GT\/ 9811028 (1998)"},{"key":"29_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1017\/S0305004108001151","volume":"145","author":"V. Kurlin","year":"2008","unstructured":"Kurlin, V.: Gauss paragraphs of classical links and a characterization of virtual link groups. Mathematical Proceedings Cambridge Phil. Soc.\u00a0145, 129\u2013140 (2008)","journal-title":"Mathematical Proceedings Cambridge Phil. Soc."},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/3-540-10003-2_85","volume-title":"Automata, Languages and Programming","author":"H. Lewis","year":"1980","unstructured":"Lewis, H., Papadimitriou, C.: Symmertric space-bounded computation (extended abstract). In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol.\u00a085, pp. 374\u2013384. Springer, Heidelberg (1980)"},{"key":"29_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-642-00982-2_43","volume-title":"Language and Automata Theory and Applications","author":"A. Lisitsa","year":"2009","unstructured":"Lisitsa, A., Potapov, I., Saleh, R.: Automata on Gauss Words. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 505\u2013517. Springer, Heidelberg (2009)"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Lomonaco Jr., S., Kauffman, L.: Topological Quantum Computing and the Jones Polynomial. Arxiv Preprint Quant-ph\/ 0605004 (2006)","DOI":"10.1117\/12.665361"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Marx, M.: A forbidden substructure characterization of Gauss codes. Bull. Amer. Math. Soc. 82(1) (1976)","DOI":"10.1090\/S0002-9904-1976-13986-9"},{"issue":"5","key":"29_CR18","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1070\/IM2005v069n05ABEH002286","volume":"69","author":"V. Manturov","year":"2005","unstructured":"Manturov, V.: A proof of Vassiliev\u2019s conjecture on the planarity of singular links. Izvestiya: Mathematics\u00a069(5), 1025\u20131033 (2005)","journal-title":"Izvestiya: Mathematics"},{"key":"29_CR19","unstructured":"Minsky, M.: Computation: finite and infinite machines (1967)"},{"issue":"1","key":"29_CR20","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/BF01475475","volume":"26","author":"J. Nagy","year":"1927","unstructured":"Nagy, J.: \u00dcber ein topologisches Problem von Gauss. Mathematische Zeitschrift\u00a026(1), 579\u2013592 (1927)","journal-title":"Mathematische Zeitschrift"},{"issue":"3","key":"29_CR21","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1145\/1013560.1013562","volume":"5","author":"F. Neven","year":"2004","unstructured":"Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Transactions on Computational Logic\u00a05(3), 403\u2013435 (2004)","journal-title":"ACM Transactions on Computational Logic"},{"key":"29_CR22","first-page":"843","volume":"18","author":"R. Read","year":"1976","unstructured":"Read, R., Rosenstiehl, P.: On the Gauss crossing problem. Colloq. Math. Soc. Janos Bolyai.\u00a018, 843\u2013876 (1976)","journal-title":"Colloq. Math. Soc. Janos Bolyai."},{"issue":"4","key":"29_CR23","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O. Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. Journal of the ACM (JACM)\u00a055(4), 17 (2008)","journal-title":"Journal of the ACM (JACM)"},{"key":"29_CR24","unstructured":"Rosenstiehl, P.: Solution algebrique du probleme de Gauss sur la permutation des points d\u2019intersection d\u2019une ou plusieurs courbes fermees du plan. CR Acad. Sci. Paris Ser. AB 283 (1976)"},{"issue":"3","key":"29_CR25","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0196-6774(84)90018-X","volume":"5","author":"P. Rosenstiehl","year":"1984","unstructured":"Rosenstiehl, P., Tarjan, R.: Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations. Journal of Algorithms\u00a05(3), 375\u2013390 (1984)","journal-title":"Journal of Algorithms"},{"issue":"6","key":"29_CR26","doi-asserted-by":"publisher","first-page":"1769","DOI":"10.1016\/j.disc.2008.02.035","volume":"309","author":"B. Shtylla","year":"2009","unstructured":"Shtylla, B., Traldi, L., Zulli, L.: On the realization of double occurrence words. Discrete Mathematics\u00a0309(6), 1769\u20131773 (2009)","journal-title":"Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21254-3_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T03:11:50Z","timestamp":1560222710000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21254-3_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642212536","9783642212543"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21254-3_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}