{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T05:53:12Z","timestamp":1768283592689,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540542339","type":"print"},{"value":"9783540475163","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_154","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:38:34Z","timestamp":1330209514000},"page":"441-454","source":"Crossref","is-referenced-by-count":36,"title":["On logics, tilings, and automata"],"prefix":"10.1007","author":[{"given":"Wolfgang","family":"Thomas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"34_CR1","first-page":"61","volume-title":"Handbook of Theoretical Computer Science, Vol. B","author":"J. Berstel","year":"1990","unstructured":"J. Berstel, L. Boasson, Context-free languages, in: Handbook of Theoretical Computer Science, Vol. B (J. v. Leeuwen, ed.), Elsevier, Amsterdam 1990, pp. 61\u2013102."},{"key":"34_CR2","first-page":"63","volume":"372","author":"D. Beauquier","year":"1989","unstructured":"D. Beauquier, J.E. Pin, Factors of words, Proc. 16th ICALP (G. Ausiello et al., eds.), Springer LNCS 372 (1989), 63\u201379.","journal-title":"Springer LNCS"},{"key":"34_CR3","first-page":"190","volume":"324","author":"F. Bossut","year":"1988","unstructured":"F. Bossut, M. Dauchet, B. Warin, Automata and Rational expressions on planar graphs, in: Proc. MFCS 1988 (M.P. Chytil et al., eds.), Springer LNCS 324 (1988), 190\u2013200.","journal-title":"Springer LNCS"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"J.R. B\u00fcchi, Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlagen Math. 6, 66\u201392.","DOI":"10.1002\/malq.19600060105"},{"key":"34_CR5","unstructured":"J.R. B\u00fcchi, On a decision method in restricted second order arithmetic, in: Logic, Methodology and Philosophy of Science. Proc. 1960 Intern. Congr. (E. Nagel et al., eds.), Stanford Univ. Press, 1\u201311."},{"key":"34_CR6","first-page":"87","volume":"431","author":"D. Caucal","year":"1990","unstructured":"D. Caucal, On the regular structure of prefix rewriting, in: CAAP 90 (A. Arnold, ed.), Springer LNCS 431 (1990), 87\u2013102.","journal-title":"Springer LNCS"},{"key":"34_CR7","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(83)90059-2","volume":"25","author":"B. Courcelle","year":"1983","unstructured":"B. Courcelle, Fundamental properties of infinite trees, Theor. Comput. Sci. 25 (1983), 95\u2013169.","journal-title":"Theor. Comput. Sci."},{"key":"34_CR8","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, Vol. B","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle, Graph rewriting: An algebraic and logic approach, in: Handbook of Theoretical Computer Science, Vol. B (J. v. Leeuwen, ed.), Elsevier, Amsterdam 1990, pp. 193\u2013242."},{"key":"34_CR9","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"C.C. Elgot","year":"1961","unstructured":"C.C. Elgot, Decision problems of finite automata design and related arithmetics, Trans. Amer. Math. Soc. 98 (1961), 21\u201352.","journal-title":"Trans. Amer. Math. Soc."},{"key":"34_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.2307\/2269808","volume":"31","author":"C.C. Elgot","year":"1966","unstructured":"C.C. Elgot, M.O. Rabin, Decidability and undecidability of extensions of second (first) order theories of (generalized) successor, J. Symb. Logic 31 (1966), 169\u2013181.","journal-title":"J. Symb. Logic"},{"key":"34_CR11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0049-237X(08)71879-2","volume-title":"Proc. of the Herbrand Symposium, Logic Colloquium '81","author":"H. Gaifman","year":"1982","unstructured":"H. Gaifman, On local and non-local properties, in: Proc. of the Herbrand Symposium, Logic Colloquium '81 (J. Stern, ed.), North-Holland, Amsterdam 1982, pp. 105\u2013135."},{"key":"34_CR12","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/4904.4993","volume":"33","author":"D. Harel","year":"1986","unstructured":"D. Harel, Effective Transformations of infinite trees, with applications to high undecidability, dominoes, and fairness, J. Assoc. Comput. Mach. 33 (1986), 224\u2013248.","journal-title":"J. Assoc. Comput. Mach."},{"key":"34_CR13","first-page":"132","volume-title":"The Theory of Models","author":"W.P. Hanf","year":"1965","unstructured":"W.P. Hanf, Model-theoretic methods in the study of elementary logic, in: The Theory of Models (J.W. Addison, L. Henkin, A. Tarski, eds.), North-Holland, Amsterdam 1965, pp. 132\u2013145."},{"key":"34_CR14","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1002\/malq.19720182507","volume":"18","author":"K. Hauschild","year":"1972","unstructured":"K. Hauschild, W. Rautenberg, Interpretierbarkeit und Entscheidbarkeit in der Graphentheorie II, Zeitschr. Math. Logik Grundl. Math. 18 (1972), 457\u2013480.","journal-title":"Zeitschr. Math. Logik Grundl. Math."},{"key":"34_CR15","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/S0019-9958(81)90438-1","volume":"49","author":"T. Kamimura","year":"1981","unstructured":"T. Kamimura, G. Slutzki, Parallel and two-way automata on directed ordered acyclic graphs, Inform. Contr. 49 (1981), 10\u201351.","journal-title":"Inform. Contr."},{"key":"34_CR16","volume-title":"Elements of the Theory of Computation","author":"H.R. Lewis","year":"1981","unstructured":"H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, Englewood Cliffs, NJ, 1981."},{"key":"34_CR17","first-page":"285","volume":"354","author":"A. Mazurkiewicz","year":"1989","unstructured":"A. Mazurkiewicz, Basic notions of trace theory, in: Linear Time, Branching Time, and Partial Order in Logics and Models of Concurrency (J.W. de Bakker et al., eds.), Springer LNCS 354 (1989), 285\u2013363.","journal-title":"Springer LNCS"},{"key":"34_CR18","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D.E. Muller","year":"1985","unstructured":"D.E. Muller, P.E. Schupp, The theory of ends, pushdown automata, and second-order logic, Theor. Comput. Sci. 37 (1985), 51\u201375.","journal-title":"Theor. Comput. Sci."},{"key":"34_CR19","volume-title":"\u03c9-Bibliography of Mathematical Logic, Vol. III (Model Theory)","year":"1987","unstructured":"G.H. M\u00fcller (ed.), \u03c9-Bibliography of Mathematical Logic, Vol. III (Model Theory), Springer-Verlag, Berlin, Heidelberg, New York 1987."},{"key":"34_CR20","first-page":"1","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"M.O. Rabin, Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969), 1\u201335.","journal-title":"Trans. Amer. Math. Soc."},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"D. Seese, The structure of models of decidable monadic theories of graphs, Ann. of Pure Appl. Logic, to appear.","DOI":"10.1016\/0168-0072(91)90054-P"},{"key":"34_CR22","doi-asserted-by":"crossref","first-page":"379","DOI":"10.2307\/1971037","volume":"102","author":"S. Shelah","year":"1975","unstructured":"S. Shelah, The monadic theory of order, Ann. Math. 102 (1975), 379\u2013419.","journal-title":"Ann. Math."},{"key":"34_CR23","first-page":"441","volume-title":"Formale Sprachen und Automatentheorie","author":"D. Siefkes","year":"1969","unstructured":"D. Siefkes, Decidable extensions of monadic second-order successor arithmetic, in: \u201cFormale Sprachen und Automatentheorie\u201d (K. D\u00f6rr, G. Hotz, eds.), Bibliographisches Institut, Mannheim, 1969, pp. 441\u2013472."},{"key":"34_CR24","unstructured":"J. Stupp, The lattice-model is recursive in the original model, manuscript, The Hebrew University, 1975."},{"key":"34_CR25","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01351676","volume":"237","author":"W. Thomas","year":"1978","unstructured":"W. Thomas, The theory of successor with an extra predicate, Math. Ann. 237 (1978), 121\u2013132.","journal-title":"Math. Ann."},{"key":"34_CR26","first-page":"135","volume-title":"Handbook of Theoretical Computer Science, Vol. B","author":"W. Thomas","year":"1990","unstructured":"W. Thomas, Automata on infinite objects, in: Handbook of Theoretical Computer Science, Vol. B (J. v. Leeuwen, ed.), Elsevier, Amsterdam 1990, pp. 135\u2013191."},{"key":"34_CR27","unstructured":"W. Thomas, On logical definability of trace languages, in: Proc. ASMICS Workshop \u201cFree Partially Commutative Monoids\u201d (V. Diekert, ed.), Rep. TUM-I9002, TU M\u00fcnchen 1990."},{"key":"34_CR28","doi-asserted-by":"crossref","unstructured":"Th. Wilke, An Eilenberg Theorem for \u221e-languages, in: Proc. ASMICS Workshop \u201cLogics and Recognizable Sets\u201d, Tech. Rep. 9104, Inst. f. Informatik u. Prakt. Math., Universit\u00e4t Kiel, 1991 (Extended Abstract in these Proceedings).","DOI":"10.1007\/3-540-54233-7_166"},{"key":"34_CR29","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1051\/ita\/1987210200991","volume":"21","author":"W. Zielonka","year":"1987","unstructured":"W. Zielonka, Notes on finite asynchronous automata, RAIRO Inform. Theor. 21 (1987), 99\u2013135.","journal-title":"RAIRO Inform. Theor."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_154.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:53:17Z","timestamp":1605646397000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_154","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}