{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T13:12:04Z","timestamp":1773234724328,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540792277","type":"print"},{"value":"9783540792284","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79228-4_45","type":"book-chapter","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T05:07:56Z","timestamp":1209445676000},"page":"514-525","source":"Crossref","is-referenced-by-count":3,"title":["Model Theoretic Complexity of Automatic Structures (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Bakhadyr","family":"Khoussainov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mia","family":"Minnes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"45_CR1","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Libkin, L.: Tree extension algebras: Logics, automata, and query languages. In: Proceedings of LICS 2002, pp. 203\u2013212 (2002)","DOI":"10.1109\/LICS.2002.1029829"},{"key":"45_CR2","doi-asserted-by":"crossref","unstructured":"Bennett, C.H.: Logical Reversibility of Computation. IBM Journal of Research and Development, 525\u2013532 (1973)","DOI":"10.1147\/rd.176.0525"},{"key":"45_CR3","unstructured":"Blaas, A., Gurevich, Y.: Program Termination and Well Partial Orderings. ACM Transactions on Computational Logic, 1\u201325 (2006)"},{"key":"45_CR4","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Zeitschrift Math. Logik und Grundlagen det Mathematik, 66\u201392 (1960)","DOI":"10.1002\/malq.19600060105"},{"key":"45_CR5","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second-order arithmetic. In: Nagel, E., Suppes, P., Tarski, A. (eds.) Proc. International Congress on Logic, Methodology and Philosophy of Science, 1960, pp. 1\u201312. Stanford University Press (1962)"},{"key":"45_CR6","doi-asserted-by":"crossref","unstructured":"Calvert, W., Goncharov, S.S., Knight, J.F.: Computable structures of Scott rank ${\\omega}_1^{CK}$ in familiar classes. In: Advances in Logic (Proceedings of the North Texas Logic Conference). Contemporary Mathematics, vol.\u00a0425, pp. 49\u201366. American Mathematical Society (2007)","DOI":"10.1090\/conm\/425\/08117"},{"key":"45_CR7","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.crma.2004.03.035","volume":"339","author":"C. Delhomm\u00e9","year":"2004","unstructured":"Delhomm\u00e9, C.: Automaticit\u00e9 des ordinaux et des graphes homog\u00e8nes. C.R. Acad\u00e8mie des sciences Paris, Ser. I\u00a0339, 5\u201310 (2004)","journal-title":"C.R. Acad\u00e8mie des sciences Paris, Ser. I"},{"key":"45_CR8","volume-title":"Automata, Languages, and Machines (Vol. A)","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg, S.: Automata, Languages, and Machines (Vol. A). Academic Press, New York (1974)"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Epstein, D.B.A., et al.: Word Processing in Groups, A.K. Peters Ltd. (Natick, Massachusetts) (1992)","DOI":"10.1201\/9781439865699"},{"key":"45_CR10","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1023\/A:1021758312697","volume":"41","author":"S.S. Goncharov","year":"2002","unstructured":"Goncharov, S.S., Knight, J.F.: Computable structure and non-structure theorems. Algebra and Logic\u00a041, 351\u2013373 (2002)","journal-title":"Algebra and Logic"},{"key":"45_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0049-237X(98)80002-5","volume-title":"Handbook of Recursive Mathematics","author":"V.S. Harizanov","year":"1998","unstructured":"Harizanov, V.S.: Pure Computable Model Theory. In: Yu. Ershov, S., Goncharov, A., Nerode, J. (eds.) Handbook of Recursive Mathematics, pp. 3\u2013114. North-Holland, Amsterdam (1998)"},{"issue":"2","key":"45_CR12","doi-asserted-by":"publisher","first-page":"526","DOI":"10.2307\/1994961","volume":"131","author":"J. Harrison","year":"1968","unstructured":"Harrison, J.: Recursive Pseudo Well-Orderings. Transactions of the American Mathematical Society\u00a0131(2), 526\u2013543 (1968)","journal-title":"Transactions of the American Mathematical Society"},{"key":"45_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"},{"key":"45_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"key":"45_CR15","series-title":"LMSLNS","first-page":"193","volume-title":"Models and Computability, Invited Papers from LC 1997","author":"B. Khoussainov","year":"1999","unstructured":"Khoussainov, B., Shore, R.A.: Effective Model Theory: The Number of Models and Their Complexity. In: Cooper, S.B., Truss, J.K. (eds.) Models and Computability, Invited Papers from LC 1997. LMSLNS, vol.\u00a0259, pp. 193\u2013240. Cambridge University Press, Cambridge, England (1999)"},{"key":"45_CR16","doi-asserted-by":"crossref","unstructured":"Khoussainov, B., Rubin, S., Stephan, F.: On automatic partial orders. In: Proceedings of 18th LICS, pp. 168\u2013177 (2003)","DOI":"10.1109\/LICS.2003.1210056"},{"issue":"4","key":"45_CR17","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":"45_CR18","unstructured":"Knight, J.F., Millar, J.: Computable Structures of Rank $\\omega_1^{CK}$ . Journal of Mathematical Logic; posted on arXiv 25 (August 2005) (submitted)"},{"key":"45_CR19","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 (LNAI), vol.\u00a02850, pp. 344\u2013358. Springer, Heidelberg (2003)"},{"key":"45_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1995086","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"Rabin, M.O.: Decidability of Second-Order Theories and Automata on Infinite Trees. Transactions of the American Mathematical Society\u00a0141, 1\u201335 (1969)","journal-title":"Transactions of the American Mathematical Society"},{"key":"45_CR21","unstructured":"Rubin, S.: Automatic Structures, PhD Thesis, University of Auckland (2004)"},{"key":"45_CR22","first-page":"329","volume-title":"The Theory of Models","author":"D. Scott","year":"1965","unstructured":"Scott, D.: Logic with Denumerably Long Formulas and Finite Strings of Quantifiers. In: Addison, J., Henkin, L., Tarski, A. (eds.) The Theory of Models, pp. 329\u2013341. North-Holland, Amsterdam (1965)"},{"key":"45_CR23","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y., Wolper, P.: Automata-Theoretic Techniques for Modal Logics of Programs. In: Proceedings of 16th STOC, pp. 446\u2013456 (1984)","DOI":"10.1145\/800057.808711"},{"key":"45_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/3-540-60915-6_6","volume-title":"Logics for Concurrency","author":"M.Y. Vardi","year":"1996","unstructured":"Vardi, M.Y.: An Automata-Theoretic Approach to Linear Temporal Logic. In: Moller, F., Birtwistle, G. (eds.) Logics for Concurrency. LNCS, vol.\u00a01043, pp. 238\u2013266. Springer, Heidelberg (1996)"},{"key":"45_CR25","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: Model Checking for Database Theoreticians. In: Proceedings of ICDL, vol. 5 (2005)","DOI":"10.1007\/978-3-540-30570-5_1"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79228-4_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T23:02:40Z","timestamp":1738191760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79228-4_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540792277","9783540792284"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79228-4_45","relation":{},"subject":[]}}