{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T08:22:40Z","timestamp":1775463760087,"version":"3.50.1"},"reference-count":40,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2006,4]]},"abstract":"<jats:p>Cayley-graphs of monoids are investigated under a logical point of view. It is shown that the class of monoids, for which the Cayley-graph has a decidable monadic second-order theory, is closed under free products. This result is derived from a result of Walukiewicz, stating that the decidability of monadic second-order theories is preserved under tree-like unfoldings. Concerning first-order logic, it is shown that the class of monoids, for which the Cayley-graph has a decidable first-order theory, is closed under arbitrary graph products, which generalize both, free and direct products. For the proof of this result, tree-like unfoldings are generalized to so-called factorized unfoldings. It is shown that the decidability of the first-order theory of a structure is preserved by factorized unfoldings. Several additional results concerning factorized unfoldings are shown.<\/jats:p>","DOI":"10.1142\/s0218196706003001","type":"journal-article","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T12:53:13Z","timestamp":1146142393000},"page":"307-340","source":"Crossref","is-referenced-by-count":14,"title":["LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE"],"prefix":"10.1142","volume":"16","author":[{"given":"DIETRICH","family":"KUSKE","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, D-04109 Leipzig, Germany"}]},{"given":"MARKUS","family":"LOHREY","sequence":"additional","affiliation":[{"name":"FMI, Universit\u00e4t Stuttgart, D-70569 Stuttgart, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","unstructured":"L.\u00a0Babai, Handbook of Combinatorics\u00a02, eds. R. L.\u00a0Graham, M.\u00a0Gr\u00f6tschel and L.\u00a0Lov\u00e1sz (Elsevier Science Publishers, 1995)\u00a0pp. 1447\u20131540."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90037-7"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322301"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00151-6"},{"key":"rf9","series-title":"Lecture Notes in Mathematics, No. 85","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0079468","volume-title":"Probl\u00e8mes Combinatoires de Commutation et R\u00e9arrangements","author":"Cartier P.","year":"1969"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90080-L"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1142\/2563"},{"key":"rf14","doi-asserted-by":"crossref","first-page":"57","DOI":"10.4064\/fm-47-1-57-103","volume":"47","author":"Feferman S.","journal-title":"Fund. Math."},{"key":"rf16","series-title":"Lecture Notes in Mathematics, No. 718","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0062837","volume-title":"The Computational Complexity of Logical Theories","author":"Ferrante J.","year":"1979"},{"key":"rf18","doi-asserted-by":"crossref","unstructured":"H.\u00a0Gaifman, Logic Colloquium '81, ed. J.\u00a0Stern (North Holland, 1982)\u00a0pp. 105\u2013135.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"rf19","unstructured":"D.\u00a0Giammarresi and A.\u00a0Restivo, Handbook of Formal Languages\u00a03, eds. G.\u00a0Rozenberg and A.\u00a0Salomaa (Springer, 1997)\u00a0pp. 216\u2013267."},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.1995.1010"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"rf23","first-page":"73","volume":"25","author":"Kelarev A. V.","journal-title":"Australas. J. Combin."},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(02)00120-8"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/s002330010162"},{"key":"rf27","doi-asserted-by":"crossref","first-page":"305","DOI":"10.3233\/FI-1999-39305","volume":"39","author":"Knapik T.","journal-title":"Fund. Inform."},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.06.002"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003248"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1142\/S021819670200122X"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61896-3"},{"key":"rf34","volume-title":"Combinatorial Group Theory","author":"Magnus W.","year":"1966"},{"key":"rf35","first-page":"147","volume":"103","author":"Makanin G. S.","journal-title":"Mat. Sb."},{"key":"rf36","first-page":"1199","volume":"46","author":"Makanin G. S.","journal-title":"Izv. Akad. Nauk SSR"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90003-X"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90087-8"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90049-X"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.2307\/1968867"},{"key":"rf44","first-page":"56","volume":"27","author":"Ochma\u0144ski E.","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS)"},{"key":"rf45","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994"},{"key":"rf46","doi-asserted-by":"publisher","DOI":"10.1007\/BF03028235"},{"key":"rf48","doi-asserted-by":"publisher","DOI":"10.2307\/1971037"},{"key":"rf49","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/hah006"},{"key":"rf50","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00390-5"},{"key":"rf52","first-page":"1","volume":"23","author":"Trakhtenbrot B. A.","journal-title":"Amer. Math. Soc. Transl. Ser. II"},{"key":"rf53","doi-asserted-by":"publisher","DOI":"10.1007\/s002330010075"},{"key":"rf54","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2001103"},{"key":"rf55","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00185-2"},{"key":"rf56","first-page":"407","volume":"27","author":"Zelinka B.","journal-title":"Casopis. Pest. Mat."}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196706003001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T06:08:05Z","timestamp":1586844485000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196706003001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":40,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,4]]}},"alternative-id":["10.1142\/S0218196706003001"],"URL":"https:\/\/doi.org\/10.1142\/s0218196706003001","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,4]]}}}