{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T09:03:24Z","timestamp":1750323804387},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642035630"},{"type":"electronic","value":"9783642035647"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03564-7_5","type":"book-chapter","created":{"date-parts":[[2009,8,20]],"date-time":"2009-08-20T03:05:35Z","timestamp":1250737535000},"page":"81-98","source":"Crossref","is-referenced-by-count":3,"title":["Theories of Automatic Structures and Their Complexity"],"prefix":"10.1007","author":[{"given":"Dietrich","family":"Kuske","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/11672142_23","volume-title":"STACS 2006","author":"V. B\u00e1r\u00e1ny","year":"2006","unstructured":"B\u00e1r\u00e1ny, V.: Invariants of automatic presentations and semi-synchronous transductions. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 289\u2013300. Springer, Heidelberg (2006)"},{"unstructured":"B\u00e1r\u00e1ny, V., Kaiser, \u0141., Rubin, S.: Cardinality and counting quantifiers on omega-automatic structures. In: STACS 2008, pp. 385\u2013396. IFIB Schloss Dagstuhl (2008)","key":"5_CR2"},{"unstructured":"Blumensath, A.: Automatic structures. Technical report, RWTH Aachen (1999)","key":"5_CR3"},{"key":"5_CR4","first-page":"51","volume-title":"LICS 2000","author":"A. Blumensath","year":"2000","unstructured":"Blumensath, A., Gr\u00e4del, E.: Automatic Structures. In: LICS 2000, pp. 51\u201362. IEEE Computer Society Press, Los Alamitos (2000)"},{"key":"5_CR5","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. Theoretical Computer Science\u00a0250, 365\u2013391 (2001)","journal-title":"Theoretical Computer Science"},{"key":"5_CR6","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. Annals of Pure and Applied Logic\u00a048, 1\u201379 (1990)","journal-title":"Annals of Pure and Applied Logic"},{"unstructured":"Corran, R., Hoffmann, M., Kuske, D., Thomas, R.M.: Singular Artin monoids of finite type are automatic (submitted)","key":"5_CR7"},{"unstructured":"Delhomm\u00e9, Ch., Goranko, V., Knapik, T.: Automatic linear orderings (Manuscript 2003)","key":"5_CR8"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"C.C. Elgot","year":"1961","unstructured":"Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc.\u00a098, 21\u201351 (1961)","journal-title":"Trans. Am. Math. Soc."},{"doi-asserted-by":"crossref","unstructured":"Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston, W.P.: Word Processin. Groups. Jones and Bartlett Publishers, Boston (1992)","key":"5_CR10","DOI":"10.1201\/9781439865699"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00233-006-0602-9","volume":"72","author":"E. Fohry","year":"2006","unstructured":"Fohry, E., Kuske, D.: On graph products of automatic and biautomatic monoids. Semigroup forum\u00a072, 337\u2013352 (2006)","journal-title":"Semigroup forum"},{"key":"5_CR12","first-page":"105","volume-title":"Logic Colloquium 1981","author":"H. Gaifman","year":"1982","unstructured":"Gaifman, H.: On local and nonlocal properties. In: Stern, J. (ed.) Logic Colloquium 1981, pp. 105\u2013135. North-Holland, Amsterdam (1982)"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/0304-3975(82)90042-1","volume":"19","author":"B.R. Hodgson","year":"1982","unstructured":"Hodgson, B.R.: On direct products of automaton decidable theories. Theoretical Computer Science\u00a019, 331\u2013335 (1982)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"5_CR14","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1002\/malq.200410013","volume":"51","author":"H.J. Keisler","year":"2005","unstructured":"Keisler, H.J., Lotfallah, W.B.: A local normal form theorem for infinitary logic with unary quantifiers. Mathematical Logic Quarterly\u00a051(2), 137\u2013144 (2005)","journal-title":"Mathematical Logic Quarterly"},{"key":"5_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/3-540-60178-3_93","volume-title":"Logic and Computational Complexity","author":"B. Khoussainov","year":"1995","unstructured":"Khoussainov, B., Nerode, A.: Automatic presentations of structures. In: Leivant, D. (ed.) LCC 1994. LNCS, vol.\u00a0960, pp. 367\u2013392. Springer, Heidelberg (1995)"},{"doi-asserted-by":"crossref","unstructured":"Khoussainov, B., Nies, A., Rubin, S., Stephan, F.: Automatic structures: richness and limitations. Log. Methods in Comput. Sci.\u00a03(2) (2007)","key":"5_CR16","DOI":"10.2168\/LMCS-3(2:2)2007"},{"key":"5_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/978-3-540-24749-4_39","volume-title":"STACS 2004","author":"B. Khoussainov","year":"2004","unstructured":"Khoussainov, B., Rubin, S., Stephan, F.: Definability and regularity in automatic structures. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 440\u2013451. Springer, Heidelberg (2004)"},{"issue":"4","key":"5_CR18","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1145\/1094622.1094625","volume":"6","author":"B. Khoussainov","year":"2005","unstructured":"Khoussainov, B., Rubin, S., Stephan, F.: Automatic linear orders and trees. ACM Transactions on Computational Logic\u00a06(4), 675\u2013700 (2005)","journal-title":"ACM Transactions on Computational Logic"},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/978-3-540-39813-4_24","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D. Kuske","year":"2003","unstructured":"Kuske, D.: Is Cantor\u2019s theorem automatic? In: Y. Vardi, M., Voronkov, A. (eds.) LPAR 2003. LNCS, vol.\u00a02850, pp. 332\u2013345. Springer, Heidelberg (2003)"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"129","DOI":"10.2178\/jsl\/1208358745","volume":"73","author":"D. Kuske","year":"2008","unstructured":"Kuske, D., Lohrey, M.: First-order and counting theories of \u03c9-automatic structures. Journal of Symbolic Logic\u00a073, 129\u2013150 (2008)","journal-title":"Journal of Symbolic Logic"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","volume-title":"CSL 1999","author":"D. Kuske","year":"2009","unstructured":"Kuske, D., Lohrey, M.: Automatic structures of bounded degree revisited. In: CSL 1999. LNCS. Springer, Heidelberg (to appear, 2009)"},{"doi-asserted-by":"crossref","unstructured":"Kuske, D., Lohrey, M.: Some natural problems in automatic graphs. Journal of Symbolic Logic (accepted, 2009)","key":"5_CR22","DOI":"10.2178\/jsl\/1268917499"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","first-page":"344","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, vol.\u00a02850, pp. 344\u2013358. Springer, Heidelberg (2003)"},{"key":"5_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/978-3-540-31856-9_57","volume-title":"STACS 2005","author":"G.P. Oliver","year":"2005","unstructured":"Oliver, G.P., Thomas, R.M.: Automatic presentations for finitely generated groups. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 693\u2013704. Springer, Heidelberg (2005)"},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"169","DOI":"10.2178\/bsl\/1208442827","volume":"14","author":"S. Rubin","year":"2008","unstructured":"Rubin, S.: Automata presenting structures: A survey of the finite string case. Bulletin of Symbolic Logic\u00a014, 169\u2013209 (2008)","journal-title":"Bulletin of Symbolic Logic"},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0890-5401(87)90020-4","volume":"74","author":"J. Sakarovitch","year":"1987","unstructured":"Sakarovitch, J.: Easy multiplications. I. The realm of Kleene\u2019s Theorem. Information and Computation\u00a074, 173\u2013197 (1987)","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Algebraic Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03564-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T07:36:52Z","timestamp":1685086612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03564-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642035630","9783642035647"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03564-7_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}