{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:38Z","timestamp":1725551138067},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540006237"},{"type":"electronic","value":"9783540364948"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_41","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T17:12:04Z","timestamp":1269882724000},"page":"463-474","source":"Crossref","is-referenced-by-count":3,"title":["Decidable Theories of Cayley-Graphs"],"prefix":"10.1007","author":[{"given":"Dietrich","family":"Kuske","sequence":"first","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"key":"41_CR1","first-page":"18","volume":"4","author":"A. V. Anisimov","year":"1971","unstructured":"A. V. Anisimov. Group languages. Kibernetika, 4:18\u201324, 1971. In Russian; English translation in: Cybernetics 4, 594\u2013601, 1973.","journal-title":"Kibernetika"},{"key":"41_CR2","unstructured":"A. Blumensath. Prefix-recognizable graphs and monadic second-order logic. Technical Report 2001-06, RWTH Aachen, Department of Computer Science, 2001."},{"issue":"4","key":"41_CR3","first-page":"141","volume":"3","author":"H. L. Bodlaender","year":"1999","unstructured":"H. L. Bodlaender. A note on domino treewidth. Discrete Mathematics & Theoretical Computer Science, 3(4):141\u2013150, 1999.","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"issue":"1\u20132","key":"41_CR4","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0304-3975(99)00151-6","volume":"250","author":"C. M. Campbell","year":"2001","unstructured":"C. M. Campbell, E. F. Robertson, N. Ru\u015dkuc, and R. M. Thomas. Automatic semigroups. Theoretical Computer Science, 250(1\u20132):365\u2013391, 2001.","journal-title":"Theoretical Computer Science"},{"key":"41_CR5","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF02088013","volume":"21","author":"B. Courcelle","year":"1989","unstructured":"B. Courcelle. The monadic second-order logic of graphs, II: Infinite graphs of bounded width. Mathematical Systems Theory, 21:187\u2013221, 1989.","journal-title":"Mathematical Systems Theory"},{"key":"41_CR6","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0166-218X(94)90019-1","volume":"54","author":"B. Courcelle","year":"1994","unstructured":"B. Courcelle. The monadic second-order logic of graphs VI: On several representations of graphs by relational structures. Discrete Applied Mathematics, 54:117\u2013149, 1994.","journal-title":"Discrete Applied Mathematics"},{"key":"41_CR7","unstructured":"V. Diekert. Makanin\u015b algorithm. In M. Lothaire, editor, Algebraic Combinatorics on Words, pages 342\u2013390. Cambridge University Press, 2001."},{"key":"41_CR8","doi-asserted-by":"crossref","unstructured":"V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scientific, 1995.","DOI":"10.1142\/2563"},{"key":"41_CR9","unstructured":"R. Diestel. Graph Theory, Second Edition. Springer, 2000."},{"issue":"1","key":"41_CR10","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF02579278","volume":"2","author":"M. J. Dunwoody","year":"1981","unstructured":"M. J. Dunwoody. Cutting up graphs. Combinatorica, 2(1):15\u201323, 1981.","journal-title":"Combinatorica"},{"issue":"2","key":"41_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.2307\/2269808","volume":"31","author":"C. C. Elgot","year":"1966","unstructured":"C. C. Elgot and M. O. Rabin. Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. Journal of Symbolic Logic, 31(2):169\u2013181, 1966.","journal-title":"Journal of Symbolic Logic"},{"key":"41_CR12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.4064\/fm-47-1-57-103","volume":"47","author":"S. Feferman","year":"1959","unstructured":"S. Feferman and R. L. Vaught. The first order properties of products of algebraic systems. Fundamenta Mathematicae, 47:57\u2013103, 1959.","journal-title":"Fundamenta Mathematicae"},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"J. Ferrante and C. Racko.. The Computational Complexity of Logical Theories, number 718 of Lecture Notes in Mathematics. Springer, 1979.","DOI":"10.1007\/BFb0062837"},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"H. Gaifman. On local and nonlocal properties. In J. Stern, editor, Logic Colloquium\u2019 81, pages 105\u2013135. North Holland, 1982.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"41_CR15","unstructured":"E. R. Green. Graph Products of Groups. PhD thesis, The University of Leeds, 1990."},{"key":"41_CR16","series-title":"Lect Notes Comput Sci","first-page":"367","volume-title":"Automatic presentations of structures","author":"B. Khoussainov","year":"1994","unstructured":"B. Khoussainov and A. Nerode. Automatic presentations of structures. In LCC: International Workshop on Logic and Computational Complexity, number 960 in Lecture Notes in Computer Science, pages 367\u2013392, 1994."},{"key":"41_CR17","doi-asserted-by":"crossref","unstructured":"D. Kuske and M. Lohrey. Decidable theories of graphs, factorized unfoldings and cayley-graphs. Technical Report2002\/37, University of Leicester, MCS, 2002.","DOI":"10.1007\/3-540-36494-3_41"},{"key":"41_CR18","first-page":"147","volume":"103","author":"G. S. Makanin","year":"1977","unstructured":"G. S. Makanin. The problem of solvability of equations in a free semigroup. Math. Sbornik, 103:147\u2013236, 1977. In Russian; English translation in: Math. USSR Sbornik 32, 1977.","journal-title":"Math. USSR Sbornik 32, 1977"},{"key":"41_CR19","first-page":"1199","volume":"46","author":"G. S. Makanin","year":"1983","unstructured":"G. S. Makanin. Equations in a free group. Izv. Akad. Nauk SSR, Ser. Math. 46:1199\u20131273, 1983. In Russian; English translation in Math. USSR Izvestija 21, 1983.","journal-title":"Izv. Akad. Nauk SSR"},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(83)90003-X","volume":"26","author":"D. E. Muller","year":"1983","unstructured":"D. E. Muller and P. E. Schupp. Groups, the theory of ends, and context-free languages. Journal of Computer and System Sciences, 26:295\u2013310, 1983.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"41_CR21","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D. E. Muller","year":"1985","unstructured":"D. E. Muller and P. E. Schupp. The theory of ends, pushdown automata, and second-order logic. Theoretical Computer Science, 37(1):51\u201375, 1985.","journal-title":"Theoretical Computer Science"},{"key":"41_CR22","series-title":"Lect Notes Comput Sci","volume-title":"Some results on equational unification","author":"P. Narendran","year":"1990","unstructured":"P. Narendran and F. Otto. Some results on equational unification. In M. E. Stickel, editor, Proceedings of the 10th International Conference on Automated Deduction (CADE 90), Kaiserslautern (Germany), number 449 in Lecture Notes in Computer Science, pages 276\u2013291. Springer, 1990."},{"key":"41_CR23","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1007\/BFb0028825","volume-title":"Tree-partite graphs and the complexity of algorithms","author":"D. Seese","year":"1985","unstructured":"D. Seese. Tree-partite graphs and the complexity of algorithms. In L. Budach, editor, Proceedings of Fundamentals of Computation Theory (FCT\u201985), Cottbus (GDR), number 199 in Lecture Notes in Computer Science, pages 412\u2013421"},{"key":"41_CR24","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0168-0072(91)90054-P","volume":"53","author":"D. Seese","year":"1991","unstructured":"D. Seese. The structure of models of decidable monadic theories of graphs. Annals of Pure and Applied Logic, 53:169\u2013195, 1991.","journal-title":"Annals of Pure and Applied Logic"},{"key":"41_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/3-540-61440-0_129","volume-title":"Semi-groups acting on context-free graphs","author":"G. S\u00e9nizergues","year":"1996","unstructured":"G. S\u00e9nizergues. Semi-groups acting on context-free graphs. In F. M. auf der Heide and B. Monien, editors, Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 96), Paderborn (Germany), number 1099 in Lecture Notes in Computer Science, pages 206\u2013218. Springer, 1996."},{"key":"41_CR26","doi-asserted-by":"crossref","first-page":"379","DOI":"10.2307\/1971037","volume":"102","author":"S. Shelah","year":"1975","unstructured":"S. Shelah. The monadic theory of order. Annals of Mathematics, II. Series, 102:379\u2013419, 1975.","journal-title":"Annals of Mathematics, II. Series"},{"key":"41_CR27","unstructured":"J. Stupp. The lattice-model is recursive in the original model. The Hebrew University, Jerusalem, 1975."},{"key":"41_CR28","series-title":"Lect Notes Comput Sci","first-page":"130","volume-title":"A short introduction to infinite automata","author":"W. Thomas","year":"2001","unstructured":"W. Thomas. A short introduction to infinite automata. In W. Kuich, G. Rozenberg, and A. Salomaa, editors, Proceedings of the 5th International Conference on Developments in Language Theory (DLT 2001), Vienna (Austria), number 2295in Lecture Notes in Computer Science, pages 130\u2013144. Springer, 2001."},{"key":"41_CR29","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1006\/jctb.1993.1042","volume":"58","author":"C. Thomassen","year":"1993","unstructured":"C. Thomassen and W. Woess. Vertex-transitive graphs and accessibility. Journal of Combinatorial Theory, Series B, 58:248\u2013268, 1993.","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"41_CR30","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s002330010075","volume":"63","author":"A. Costa Veloso da","year":"2001","unstructured":"A. Veloso da Costa. Graph products of monoids. Semigroup Forum, 63(2):247\u2013277, 2001.","journal-title":"Semigroup Forum"},{"issue":"1\u20132","key":"41_CR31","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0304-3975(01)00185-2","volume":"275","author":"I. Walukiewicz","year":"2002","unstructured":"I. Walukiewicz. Monadic second-order logic on tree-like structures. Theoretical Computer Science, 275(1\u20132):311\u2013346, 2002.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T06:00:14Z","timestamp":1685512814000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}