{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:54:16Z","timestamp":1725515656180},"publisher-location":"Boston, MA","reference-count":29,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387096797"},{"type":"electronic","value":"9780387096803"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-0-387-09680-3_30","type":"book-chapter","created":{"date-parts":[[2008,7,21]],"date-time":"2008-07-21T11:37:14Z","timestamp":1216640234000},"page":"445-459","source":"Crossref","is-referenced-by-count":1,"title":["Hamiltonicity of automatic graphs"],"prefix":"10.1007","author":[{"given":"Dietrich","family":"Kuske","sequence":"first","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"30_CR1","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1017\/S0022481200051549","volume":"41","author":"D.R. Bean","year":"1976","unstructured":"D. R. Bean. Effective coloration. J. Symbolic Logic, 41(2):469\u2013480, 1976.","journal-title":"J. Symbolic Logic"},{"issue":"2","key":"30_CR2","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1090\/S0002-9939-1976-0416888-0","volume":"55","author":"D.R. Bean","year":"1976","unstructured":"D. R. Bean. Recursive Euler and Hamilton paths. Proc. Amer. Math. Soc., 55(2):385\u2013394, 1976.","journal-title":"Proc. Amer. Math. Soc."},{"key":"30_CR3","unstructured":"R. Beigel and W. I. Gasarch. unpublished results. 1986\u20131990."},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"R. Berger. The undecidability of the domino problem. Mem. Am. Math. Soc., 66. AMS, 1966.","DOI":"10.1090\/memo\/0066"},{"issue":"6","key":"30_CR5","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00224-004-1133-y","volume":"37","author":"A. Blumensath","year":"2004","unstructured":"A. Blumensath and E. Gr\u00e4del. Finite presentations of infinite structures: Automata and interpretations. Theory Comput. Syst., 37(6):641\u2013674, 2004.","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"30_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1002\/(SICI)1097-0118(199610)23:2<163::AID-JGT7>3.0.CO;2-R","volume":"23","author":"N. Dean","year":"1996","unstructured":"N. Dean, R. Thomas, and X. Yu. Spanning paths in infinite planar graphs. J. Graph Theory, 23(2):163\u2013174, 1996.","journal-title":"J. Graph Theory"},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"R. Diestel. Graph Theory, Third Edition. Springer, 2006.","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"M. F\u00fcrer. The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). In Logic and machines: decision problems and complexity, LNCS 171, pages 312\u2013319. Springer, 1984.","DOI":"10.1007\/3-540-13331-3_48"},{"issue":"4","key":"30_CR9","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. Garey","year":"1976","unstructured":"M. Garey, D. Johnson, and R. E. Tarjan. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput., 5(4):704\u2013714, 1976.","journal-title":"SIAM J. Comput."},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"D. Harel. A simple undecidable domino problem (or, a lemma on infinite trees, with applications). In Proc. Logic and Computation Conference, Victoria, Australia, 1984. Clayton.","DOI":"10.1145\/800057.808708"},{"key":"30_CR11","first-page":"51","volume":"24","author":"D. Harel","year":"1985","unstructured":"D. Harel. Recurring dominoes: making the highly undecidable highly understandable. Ann. Discrete Math., 24:51\u201372, 1985.","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"30_CR12","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1145\/4904.4993","volume":"33","author":"D. Harel","year":"1986","unstructured":"D. Harel. Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness. J. Assoc. Comput. Mach., 33(1):224\u2013248, 1986.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"30_CR13","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/BF02773868","volume":"76","author":"D. Harel","year":"1991","unstructured":"D. Harel. Hamiltonian paths in infinite graphs. Israel J. Math., 76(3):317\u2013336, 1991.","journal-title":"Israel J. Math."},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1006\/jcss.1996.0060","volume":"53","author":"T. Hirst","year":"1996","unstructured":"T. Hirst and D. Harel. Taking it to the limit: on infinite variants of NP-complete problems. J. Comput. System Sci., 53:180\u2013193, 1996.","journal-title":"J. Comput. System Sci."},{"key":"30_CR15","unstructured":"B. Khoussainov and M. Minnes. Model theoretic complexity of automatic structures. In Proceedings of TAMC 08. Springer, 2008. to appear."},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"B. Khoussainov and A. Nerode. Automatic presentations of structures. In LCC: International Workshop on Logic and Computational Complexity, LNCS 960, pages 367\u2013392, 1994.","DOI":"10.1007\/3-540-60178-3_93"},{"key":"30_CR17","unstructured":"B. Khoussainov, A. Nies, S. Rubin, and F. Stephan. Automatic structures: richness and limitations. Log. Methods Comput. Sci., 3(2):2:2, 18 pp. (electronic), 2007."},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"B. Khoussainov, S. Rubin, and F. Stephan. On automatic partial orders. In Proc. LICS 2003, pages 168\u2013177. IEEE Computer Society Press, 2003.","DOI":"10.1109\/LICS.2003.1210056"},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"B. Khoussainov, S. Rubin, and F. Stephan. Definability and regularity in automatic structures. In Proc. STACS 2004, LNCS 2996, pages 440\u2013451. Springer, 2004.","DOI":"10.1007\/978-3-540-24749-4_39"},{"issue":"4","key":"30_CR20","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1145\/1094622.1094625","volume":"6","author":"B. Khoussainov","year":"2005","unstructured":"B. Khoussainov, S. Rubin, and F. Stephan. Automatic linear orders and trees. ACM Trans. Comput. Log., 6(4):675\u2013700, 2005.","journal-title":"ACM Trans. Comput. Log."},{"key":"30_CR21","unstructured":"D. Kozen. Theory of Computation. Springer, 2006."},{"key":"30_CR22","doi-asserted-by":"publisher","first-page":"129","DOI":"10.2178\/jsl\/1208358745","volume":"73","author":"D. Kuske","year":"2008","unstructured":"D. Kuske and M. Lohrey. First-order and counting theories of omega-automatic structures. J. Symbolic Logic, 73:129\u2013150, 2008.","journal-title":"J. Symbolic Logic"},{"key":"30_CR23","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1112\/plms\/s3-25.4.615","volume":"25","author":"A.B. Manaster","year":"1972","unstructured":"A. B. Manaster and J. G. Rosenstein. Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall). Proc. London Math. Soc. (3), 25:615\u2013654, 1972.","journal-title":"Proc. London Math. Soc. (3)"},{"key":"30_CR24","unstructured":"S. Rubin. Automatic Structures. PhD thesis, University of Auckland, 2004."},{"key":"30_CR25","doi-asserted-by":"crossref","unstructured":"S. Rubin. Automata presenting structures: A survey of the finite string case. Bull. Symbolic Logic, 2008. To appear.","DOI":"10.2178\/bsl\/1208442827"},{"issue":"1","key":"30_CR26","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0022-0000(92)90043-I","volume":"45","author":"I.A. Stewart","year":"1992","unstructured":"I. A. Stewart. Using the Hamiltonian path operator to capture NP. J. Comput. System Sci., 45(1):127\u2013151, 1992.","journal-title":"J. Comput. System Sci."},{"key":"30_CR27","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1090\/S0002-9947-1956-0081471-8","volume":"82","author":"W.T. Tutte","year":"1956","unstructured":"W. T. Tutte. A theorem on planar graphs. Trans. Amer. Math. Soc., 82:99\u2013116, 1956.","journal-title":"Trans. Amer. Math. Soc."},{"key":"30_CR28","doi-asserted-by":"crossref","unstructured":"H. Veith. How to encode a logical structure by an OBDD. In Proc. 13th Annual Conf. Computational Complexity, pages 122\u2013131. IEEE Computer Society, 1998.","DOI":"10.1109\/CCC.1998.694598"},{"key":"30_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/j.1538-7305.1961.tb03975.x","volume":"40","author":"H. Wang","year":"1961","unstructured":"H. Wang. Proving theorems by pattern recognition. Bell Syst. Tech. J., 40:1\u201341, 1961.","journal-title":"Bell Syst. Tech. J."}],"container-title":["IFIP International Federation for Information Processing","Fifth Ifip International Conference On Theoretical Computer Science \u2013 Tcs 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-09680-3_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:44:37Z","timestamp":1619574277000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-0-387-09680-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9780387096797","9780387096803"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-09680-3_30","relation":{},"ISSN":["1571-5736"],"issn-type":[{"type":"print","value":"1571-5736"}],"subject":[]}}