{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:56:21Z","timestamp":1743155781455,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031435867"},{"type":"electronic","value":"9783031435874"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-43587-4_4","type":"book-chapter","created":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T01:02:10Z","timestamp":1695258130000},"page":"46-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Domino Snake Problems on\u00a0Groups"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2701-570X","authenticated-orcid":false,"given":"Nathalie","family":"Aubrun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3460-9442","authenticated-orcid":false,"given":"Nicolas","family":"Bitar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,21]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L., Kari, J., Kari, L., Reishus, D.: On the decidability of self-assembly of infinite ribbons. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science 2002, pp. 530\u2013537. IEEE (2002)","DOI":"10.1109\/SFCS.2002.1181977"},{"issue":"11","key":"4_CR2","doi-asserted-by":"publisher","first-page":"7965","DOI":"10.1090\/tran\/6701","volume":"368","author":"Y Antolin","year":"2016","unstructured":"Antolin, Y., Ciobanu, L.: Finite generating sets of relatively hyperbolic groups and applications to geodesic languages. Trans. Am. Math. Soc. 368(11), 7965\u20138010 (2016)","journal-title":"Trans. Am. Math. Soc."},{"key":"4_CR3","series-title":"Trends in Mathematics","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-319-69152-7_9","volume-title":"Sequences, Groups, and Number Theory","author":"N Aubrun","year":"2018","unstructured":"Aubrun, N., Barbieri, S., Jeandel, E.: About the domino problem for subshifts on groups. In: Berth\u00e9, V., Rigo, M. (eds.) Sequences, Groups, and Number Theory. TM, pp. 331\u2013389. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-69152-7_9"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Aubrun, N., Bitar, N.: Domino snake problems on groups. arXiv preprint arXiv:2307.12655 (2023)","DOI":"10.1007\/978-3-031-43587-4_4"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"1423","DOI":"10.4171\/GGD\/689","volume":"16","author":"L Bartholdi","year":"2022","unstructured":"Bartholdi, L.: Monadic second-order logic and the domino problem on self-similar graphs. Groups Geom. Dyn. 16, 1423\u20131459 (2022)","journal-title":"Groups Geom. Dyn."},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Berger, R.: The Undecidability of the Domino Problem. No. 66. American Mathematical Soc. (1966)","DOI":"10.1090\/memo\/0066"},{"issue":"3","key":"4_CR7","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s00209-004-0666-8","volume":"248","author":"R Charney","year":"2004","unstructured":"Charney, R., Meier, J.: The language of geodesics for Garside groups. Math. Zeitschrift 248(3), 495\u2013509 (2004)","journal-title":"Math. Zeitschrift"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-319-66213-8_2","volume-title":"The Theory of Nilpotent Groups","author":"AE Clement","year":"2017","unstructured":"Clement, A.E., Majewicz, S., Zyman, M.: Introduction to nilpotent groups. In: The Theory of Nilpotent Groups, pp. 23\u201373. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-66213-8_2"},{"issue":"22\u201324","key":"4_CR9","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/malq.19820282204","volume":"28","author":"HD Ebbinghaus","year":"1982","unstructured":"Ebbinghaus, H.D.: Undecidability of some domino connectability problems. Math. Logic Q. 28(22\u201324), 331\u2013336 (1982)","journal-title":"Math. Logic Q."},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/3-540-18170-9_161","volume-title":"Computation Theory and Logic","author":"H-D Ebbinghaus","year":"1987","unstructured":"Ebbinghaus, H.-D.: Domino threads and complexity. In: B\u00f6rger, E. (ed.) Computation Theory and Logic. LNCS, vol. 270, pp. 131\u2013142. Springer, Heidelberg (1987). https:\/\/doi.org\/10.1007\/3-540-18170-9_161"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: The convenience of tilings. In: Complexity, Logic, and Recursion Theory, pp. 331\u2013363. CRC Press (2019)","DOI":"10.1201\/9780429187490-12"},{"key":"4_CR12","doi-asserted-by":"publisher","unstructured":"Epstein, D.B.: Word Processing in Groups. A K Peters\/CRC Press, Massachusetts (1992). https:\/\/doi.org\/10.1201\/9781439865699","DOI":"10.1201\/9781439865699"},{"key":"4_CR13","unstructured":"Etzion, Y.: On the Solvability of Domino Snake Problems. Master\u2019s thesis, Dept. of Applied Math. and Computer Science, Wiezmann Institute of Science, Rehovot, Israel (1991)"},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0304-3975(94)90174-0","volume":"131","author":"Y Etzion-Petruschka","year":"1994","unstructured":"Etzion-Petruschka, Y., Harel, D., Myers, D.: On the solvability of domino snake problems. Theor. Comput. Sci. 131(2), 243\u2013269 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"4_CR15","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1137\/0219055","volume":"19","author":"E Gr\u00e4del","year":"1990","unstructured":"Gr\u00e4del, E.: Domino games and complexity. SIAM J. Comput. 19(5), 787\u2013804 (1990)","journal-title":"SIAM J. Comput."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Harel, D.: Recurring dominoes: making the highly undecidable highly understandable. In: North-Holland Mathematics Studies, vol. 102, pp. 51\u201371. Elsevier (1985)","DOI":"10.1016\/S0304-0208(08)73075-5"},{"issue":"3","key":"4_CR17","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1112\/plms\/pdr035","volume":"104","author":"DF Holt","year":"2012","unstructured":"Holt, D.F., Rees, S.: Artin groups of large type are shortlex automatic with regular geodesics. Proc. London Math. Soc. 104(3), 486\u2013512 (2012)","journal-title":"Proc. London Math. Soc."},{"key":"4_CR18","unstructured":"Howlett, R.B.: Miscellaneous facts about Coxeter groups. University of Sydney, School of Mathematics and Statistics (1993)"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-45005-X_6","volume-title":"Developments in Language Theory","author":"J Kari","year":"2003","unstructured":"Kari, J.: Infinite snake tiling problems. In: Ito, M., Toyama, M. (eds.) DLT 2002. LNCS, vol. 2450, pp. 67\u201377. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45005-X_6"},{"issue":"1\u20133","key":"4_CR20","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/j.apal.2004.06.002","volume":"131","author":"D Kuske","year":"2005","unstructured":"Kuske, D., Lohrey, M.: Logical aspects of Cayley-graphs: the group case. Ann. Pure Appl. Logic 131(1\u20133), 263\u2013286 (2005)","journal-title":"Ann. Pure Appl. Logic"},{"key":"4_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/9781108899727","volume-title":"An Introduction to Symbolic Dynamics and Coding","author":"D Lind","year":"2021","unstructured":"Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (2021)"},{"issue":"3","key":"4_CR22","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(83)90003-X","volume":"26","author":"DE Muller","year":"1983","unstructured":"Muller, D.E., Schupp, P.E.: Groups, the theory of ends, and context-free languages. J. Comput. Syst. Sci. 26(3), 295\u2013310 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"DE Muller","year":"1985","unstructured":"Muller, D.E., Schupp, P.E.: The theory of ends, pushdown automata, and second-order logic. Theor. Comput. Sci. 37, 51\u201375 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR24","unstructured":"Myers, D.: Decidability of the tiling connectivity problem. Abstract 79T\u2013E42. Notices Am. Math. Soc. 195(26), 177\u2013209 (1979)"},{"issue":"1","key":"4_CR25","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01241129","volume":"120","author":"WD Neumann","year":"1995","unstructured":"Neumann, W.D., Shapiro, M.: Automatic structures, rational growth, and geometrically finite hyperbolic groups. Inventiones Math. 120(1), 259\u2013287 (1995)","journal-title":"Inventiones Math."},{"issue":"1","key":"4_CR26","doi-asserted-by":"publisher","first-page":"179","DOI":"10.2140\/gt.2014.18.179","volume":"18","author":"B Seward","year":"2014","unstructured":"Seward, B.: Burnside\u2019s problem, spanning trees and tilings. Geom. Topology 18(1), 179\u2013210 (2014). https:\/\/doi.org\/10.2140\/gt.2014.18.179","journal-title":"Geom. Topology"},{"issue":"1","key":"4_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/j.1538-7305.1961.tb03975.x","volume":"40","author":"H Wang","year":"1961","unstructured":"Wang, H.: Proving theorems by pattern recognition-II. Bell Syst. Tech. J. 40(1), 1\u201341 (1961)","journal-title":"Bell Syst. Tech. J."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43587-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T14:24:10Z","timestamp":1730125450000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43587-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031435867","9783031435874"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43587-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"21 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Trier","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.uni-trier.de\/index.php?id=71937&L=2","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"69","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}