{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T09:59:34Z","timestamp":1773223174725,"version":"3.50.1"},"reference-count":33,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,8]]},"abstract":"<jats:p>Several complexity and decidability results for automatic monoids are shown: (i) there exists an automatic monoid with a P-complete word problem, (ii) there exists an automatic monoid such that the first-order theory of the corresponding Cayley-graph is not elementary decidable, and (iii) there exists an automatic monoid such that reachability in the corresponding Cayley-graph is undecidable. Moreover, it is shown that for every hyperbolic group the word problem belongs to LOGCFL, which improves a result of Cai [8].<\/jats:p>","DOI":"10.1142\/s0129054105003248","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T14:52:13Z","timestamp":1120575133000},"page":"707-722","source":"Crossref","is-referenced-by-count":19,"title":["DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS"],"prefix":"10.1142","volume":"16","author":[{"given":"MARKUS","family":"LOHREY","sequence":"first","affiliation":[{"name":"FMI, University of Stuttgart, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00271645"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00070-1"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1133-y"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322301"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00151-6"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90080-L"},{"key":"rf12","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0084913","volume-title":"G\u00e9om\u00e9trie et th\u00e9orie des groupes","volume":"1441","author":"Coornaert M.","year":"1990"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90062-0"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004103007497"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1201\/9781439865699"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9586-7_3"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/s002330010161"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196700000078"},{"key":"rf22","unstructured":"J. F. P.\u00a0Hudson, Semigroups, Automata and Languages (World Scientific, 1998)\u00a0pp. 145\u2013152."},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/s002330010162"},{"key":"rf25","doi-asserted-by":"crossref","first-page":"305","DOI":"10.3233\/FI-1999-39305","volume":"39","author":"Knapik T.","journal-title":"Fundamenta Informaticae"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.06.002"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61896-3"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90003-X"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90087-8"},{"key":"rf36","first-page":"375","volume":"6","author":"Otto F.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.2307\/2267170"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1007\/BF01241140"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90036-7"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1007\/BF03028235"},{"key":"rf41","unstructured":"G.\u00a0S\u00e9nizergues, Term Rewriting, French Spring School of Theoretical Computer Science, Font Romeux (France), Lecture Notes in Computer Science\u00a0909, eds. H.\u00a0Comon and J.P.\u00a0Jouannaud (Springer, 1993)\u00a0pp. 75\u201394."},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00390-5"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/hah006"},{"key":"rf44","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322083"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90020-6"},{"key":"rf46","first-page":"407","volume":"27","author":"Zelinka B.","journal-title":"Casopis. Pest. Mat."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T04:33:05Z","timestamp":1586320385000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":33,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,8]]}},"alternative-id":["10.1142\/S0129054105003248"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003248","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8]]}}}