{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:49Z","timestamp":1725558949062},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240143"},{"type":"electronic","value":"9783540305507"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30550-7_26","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T15:06:05Z","timestamp":1278083165000},"page":"308-320","source":"Crossref","is-referenced-by-count":1,"title":["Decidability and Complexity in Automatic Monoids"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","first-page":"51","volume-title":"Proc.\u00a0LICS 2000","author":"A. Blumensath","year":"2000","unstructured":"Blumensath, A., Gr\u00e4del, E.: Automatic structures. In: Proc.\u00a0LICS 2000, pp. 51\u201362. IEEE Computer Society Press, Los Alamitos (2000)"},{"key":"26_CR2","unstructured":"Blumensath, A., Gr\u00e4del, E.: Finite presentations of infinite structures: Automata and interpretations. In: Proc.\u00a0CiAD 2002 (2002)"},{"key":"26_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-9771-7","volume-title":"String\u2013Rewriting Systems","author":"R.V. Book","year":"1993","unstructured":"Book, R.V., Otto, F.: String\u2013Rewriting Systems. Springer, Heidelberg (1993)"},{"key":"26_CR4","first-page":"106","volume-title":"Proc.\u00a0STOC 1992","author":"J.-Y. Cai","year":"1992","unstructured":"Cai, J.-Y.: Parallel computation over hyperbolic groups. In: Proc.\u00a0STOC 1992, pp. 106\u2013115. ACM Press, New York (1992)"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-540-49382-2_31","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"H. Calbrix","year":"1998","unstructured":"Calbrix, H., Knapik, T.: A string-rewriting characterization of Muller and Schupp\u2019s context-free graphs. In: Arvind, V., Sarukkai, S. (eds.) FST TCS 1998. LNCS, vol.\u00a01530, pp. 331\u2013342. Springer, Heidelberg (1998)"},{"issue":"1-2","key":"26_CR6","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0304-3975(99)00151-6","volume":"250","author":"C.M. Campbell","year":"2001","unstructured":"Campbell, C.M., Robertson, E.F., Ru\u0161kuc, N., Thomas, R.M.: Automatic semigroups. Theor.\u00a0Comput.\u00a0Sci.\u00a0250(1-2), 365\u2013391 (2001)","journal-title":"Theor.\u00a0Comput.\u00a0Sci."},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(90)90080-L","volume":"48","author":"K.J. Compton","year":"1990","unstructured":"Compton, K.J., Henson, C.W.: A uniform method for proving lower bounds on the computational complexity of logical theories. Ann.\u00a0Pure Appl.\u00a0Logic\u00a048, 1\u201379 (1990)","journal-title":"Ann.\u00a0Pure Appl.\u00a0Logic"},{"key":"26_CR8","volume-title":"Lecture Notes in Mathematics","author":"M. Coornaert","year":"1990","unstructured":"Coornaert, M., Delzant, T., Papadopoulos, A.: G\u00e9om\u00e9trie et th\u00e9orie des groupes. In: Lecture Notes in Mathematics. Springer, Heidelberg (1990)"},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/0022-0000(86)90062-0","volume":"33","author":"E. Dahlhaus","year":"1986","unstructured":"Dahlhaus, E., Warmuth, M.K.: Membership for growing context-sensitive grammars is polynomial. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a033, 456\u2013472 (1986)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1017\/S0305004103007497","volume":"136","author":"A. Duncan","year":"2004","unstructured":"Duncan, A., Gilman, R.H.: Word hyperbolic semigroups. Math.\u00a0Proc.\u00a0Cambridge Philos.\u00a0Soc.\u00a0136, 513\u2013524 (2004)","journal-title":"Math.\u00a0Proc.\u00a0Cambridge Philos.\u00a0Soc."},{"key":"26_CR11","doi-asserted-by":"crossref","DOI":"10.1201\/9781439865699","volume-title":"Word processing in groups","author":"D.B.A. Epstein","year":"1992","unstructured":"Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston, W.P.: Word processing in groups. Jones and Bartlett, Boston (1992)"},{"key":"26_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574","volume-title":"Model Theory","author":"W. Hodges","year":"1993","unstructured":"Hodges, W.: Model Theory. Cambridge University Press, Cambridge (1993)"},{"key":"26_CR13","unstructured":"Hoffmann, M.: Automatic semigroups. PhD thesis, University of Leicester, Department of Mathematics and Computer Science (2000)"},{"issue":"3","key":"26_CR14","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s002330010161","volume":"66","author":"M. Hoffmann","year":"2003","unstructured":"Hoffmann, M., Thomas, R.M.: Notions of automaticity in semigroups. Semigroup Forum\u00a066(3), 337\u2013367 (2003)","journal-title":"Semigroup Forum"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1142\/9789812776884_0016","volume-title":"Workshop on Semigroups, algorithms, automata and languages 2001","author":"M. Hoffmann","year":"2002","unstructured":"Hoffmann, M., Kuske, D., Otto, F., Thomas, R.M.: Some relatives of automatic and hyperbolic groups. In: Workshop on Semigroups, algorithms, automata and languages 2001, pp. 379\u2013406. World Scientific, Singapore (2002)"},{"key":"26_CR16","first-page":"145","volume-title":"Semigroups, Automata and Languages","author":"J.F.P. Hudson","year":"1998","unstructured":"Hudson, J.F.P.: Regular rewrite systems and automatic structures. In: Semigroups, Automata and Languages, pp. 145\u2013152. World Scientific, Singapore (1998)"},{"issue":"1","key":"26_CR17","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s002330010162","volume":"66","author":"A.V. Kelarev","year":"2003","unstructured":"Kelarev, A.V., Quinn, S.J.: A combinatorial property and Cayley graphs of semigroups. Semigroup Forum\u00a066(1), 89\u201396 (2003)","journal-title":"Semigroup Forum"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","first-page":"367","volume-title":"Logic and Computational Complexity","author":"B. Khoussainov","year":"1994","unstructured":"Khoussainov, B., Nerode, A.: Automatic presentations of structures. In: Leivant, D. (ed.) LCC 1994. LNCS, vol.\u00a0960, pp. 367\u2013392. Springer, Heidelberg (1994)"},{"key":"26_CR19","doi-asserted-by":"crossref","first-page":"305","DOI":"10.3233\/FI-1999-39305","volume":"39","author":"T. Knapik","year":"1999","unstructured":"Knapik, T., Calbrix, H.: Thue specifications and their monadic second-order properties. Fundam.\u00a0Inform.\u00a039, 305\u2013325 (1999)","journal-title":"Fundam.\u00a0Inform."},{"key":"26_CR20","unstructured":"Kuske, D., Lohrey, M.: Logical aspects of Cayley-graphs: the group case. In: Ann.\u00a0Pure Appl.\u00a0Logic (to appear)"},{"key":"26_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/3-540-36494-3_41","volume-title":"STACS 2003","author":"D. Kuske","year":"2003","unstructured":"Kuske, D., Lohrey, M.: Decidable theories of Cayley-graphs. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 463\u2013474. Springer, Heidelberg (2003)"},{"key":"26_CR22","series-title":"LNCS (LNAI)","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-540-39813-4_25","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"M. Lohrey","year":"2003","unstructured":"Lohrey, M.: Automatic structures of bounded degree. In: Y. Vardi, M., Voronkov, A. (eds.) LPAR 2003. LNCS (LNAI), vol.\u00a02850, pp. 344\u2013358. Springer, Heidelberg (2003)"},{"key":"26_CR23","volume-title":"Combinatorial Group Theory","author":"R.C. Lyndon","year":"1977","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Springer, Heidelberg (1977)"},{"key":"26_CR24","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(83)90003-X","volume":"26","author":"D.E. Muller","year":"1983","unstructured":"Muller, D.E., Schupp, P.E.: Groups, the theory of ends, and context-free languages. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a026, 295\u2013310 (1983)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"issue":"1","key":"26_CR25","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D.E. Muller","year":"1985","unstructured":"Muller, D.E., Schupp, P.E.: The theory of ends, pushdown automata, and second-order logic. Theor.\u00a0Comput.\u00a0Sci.\u00a037(1), 51\u201375 (1985)","journal-title":"Theor.\u00a0Comput.\u00a0Sci."},{"issue":"3","key":"26_CR26","first-page":"375","volume":"6","author":"F. Otto","year":"2001","unstructured":"Otto, F., Ru\u0161kuc, N.: Confluent monadic string-rewriting systems and automatic structures. J.\u00a0Autom.\u00a0Lang.\u00a0Comb.\u00a06(3), 375\u2013388 (2001)","journal-title":"J.\u00a0Autom.\u00a0Lang.\u00a0Comb."},{"key":"26_CR27","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W.L. Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree\u2013size bounded alternation. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a021, 218\u2013235 (1980)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"key":"26_CR28","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF03028235","volume":"1","author":"P.E. Schupp","year":"1979","unstructured":"Schupp, P.E.: Groups and graphs: Groups acting on trees, ends, and cancellation diagrams. Math.\u00a0Intell.\u00a01, 205\u2013222 (1979)","journal-title":"Math.\u00a0Intell."},{"key":"26_CR29","series-title":"Lecture Notes in Computer Science","first-page":"75","volume-title":"Term Rewriting, French Spring School of Theoretical Computer Science","author":"G. S\u00e9nizergues","year":"1993","unstructured":"S\u00e9nizergues, G.: Formal languages and word-rewriting. In: Comon, H., Jouannaud, J.-P. (eds.) TCS School 1993. LNCS, vol.\u00a0909, pp. 75\u201394. Springer, Heidelberg (1993)"},{"key":"26_CR30","unstructured":"Silva, P.V., Steinberg, B.: A geometric characterization of automatic monoids. Technical Report CMUP 2000-03, University of Porto (2001)"},{"key":"26_CR31","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1016\/S0304-3975(01)00390-5","volume":"289","author":"P.V. Silva","year":"2002","unstructured":"Silva, P.V., Steinberg, B.: Extensions and submonoids of automatic monoids. Theor.\u00a0Comput.\u00a0Sci.\u00a0289, 727\u2013754 (2002)","journal-title":"Theor.\u00a0Comput.\u00a0Sci."},{"issue":"3","key":"26_CR32","first-page":"405","volume":"25","author":"I.H. Sudborough","year":"1978","unstructured":"Sudborough, I.H.: On the tape complexity of deterministic context\u2013free languages. J.\u00a0Assoc.\u00a0Comput.\u00a0Mach.\u00a025(3), 405\u2013414 (1978)","journal-title":"J.\u00a0Assoc.\u00a0Comput.\u00a0Mach."},{"key":"26_CR33","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"43","author":"H. Venkateswaran","year":"1991","unstructured":"Venkateswaran, H.: Properties that characterize LOGCFL. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a043, 380\u2013404 (1991)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30550-7_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T09:08:50Z","timestamp":1591434530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30550-7_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240143","9783540305507"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30550-7_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}