{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T02:06:31Z","timestamp":1725501991525},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540781264"},{"type":"electronic","value":"9783540781271"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78127-1_35","type":"book-chapter","created":{"date-parts":[[2008,2,7]],"date-time":"2008-02-07T12:59:40Z","timestamp":1202389180000},"page":"635-655","source":"Crossref","is-referenced-by-count":21,"title":["Church\u2019s Problem and a Tour through Automata Theory"],"prefix":"10.1007","author":[{"given":"Wolfgang","family":"Thomas","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math.\u00a06, 66\u201392 (1960)","journal-title":"Z. Math. Logik Grundlagen Math."},{"key":"35_CR2","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Nagel, E., et al. (eds.) Proc. 1960 International Congress on Logic, Methodology and Philosophy of Science, pp. 1\u201311. Stanford University Press (1962)"},{"key":"35_CR3","unstructured":"B\u00fcchi, J.R., Elgot, C.C.: Decision problems of weak second-order arithmetics and finite automata, Abstract 553-112, Notices Amer. Math. Soc. 5, 834 (1958)"},{"key":"35_CR4","doi-asserted-by":"publisher","first-page":"367","DOI":"10.2307\/1994916","volume":"138","author":"J.R. B\u00fcchi","year":"1969","unstructured":"B\u00fcchi, J.R., Landweber, L.H.: Solving sequential conditions by finite-state strategies, Trans. Trans. Amer. Math. Soc\u00a0138, 367\u2013378 (1969)","journal-title":"Trans. Amer. Math. Soc"},{"key":"35_CR5","first-page":"3","volume-title":"Summaries of the Summer Institute of Symbolic Logic","author":"A. Church","year":"1957","unstructured":"Church, A.: Applications of recursive arithmetic to the problem of circuit synthesis. In: Summaries of the Summer Institute of Symbolic Logic, vol.\u00a0I, pp. 3\u201350. Cornell Univ, Ithaca, N.Y (1957)"},{"key":"35_CR6","unstructured":"Church, A.: Logic, arithmetic, and automata. In: Proc. Int. Congr. Math. 1962, Inst. Mittag-Leffler, Djursholm, Sweden, pp. 23\u201335 (1963)"},{"key":"35_CR7","first-page":"99","volume-title":"Proc. 12th IEEE Symp. on Logic in Computer Science","author":"S. Dziembowski","year":"1997","unstructured":"Dziembowski, S., Jurdzi\u0144ski, M., Walukiewicz, I.: How much memory is needed to win infinite games? In: Proc. 12th IEEE Symp. on Logic in Computer Science, pp. 99\u2013110. IEEE Computer Society Press, Los Alamitos (1997)"},{"key":"35_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.2307\/1993511","volume":"98","author":"C.C. Elgot","year":"1961","unstructured":"Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc.\u00a098, 21\u201352 (1961)","journal-title":"Trans. Amer. Math. Soc."},{"key":"35_CR9","first-page":"368","volume-title":"Proc. 32nd FoCS 1991","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus, and determinacy. In: Proc. 32nd FoCS 1991, pp. 368\u2013377. IEEE Comp. Soc. Press, Los Alamitos (1991)"},{"key":"35_CR10","first-page":"60","volume-title":"Proc. 14th ACM Symp. on the Theory of Computing","author":"Y. Gurevich","year":"1982","unstructured":"Gurevich, Y., Harrington, L.: Trees, automata, and games. In: Proc. 14th ACM Symp. on the Theory of Computing, pp. 60\u201365. ACM Press, New York (1982)"},{"key":"35_CR11","volume-title":"Formal Languages and Their Relation to Automata","author":"J.E. Hopcroft","year":"1969","unstructured":"Hopcroft, J.E., Ullman, J.D.: Formal Languages and Their Relation to Automata. Addison-Wesley, Boston (1969)"},{"key":"35_CR12","volume-title":"Finite-state infinite games, Project MAC Rep.","author":"R. McNaughton","year":"1965","unstructured":"McNaughton, R.: Finite-state infinite games, Project MAC Rep. MIT, Cambridge (1965)"},{"key":"35_CR13","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","volume":"9","author":"R. McNaughton","year":"1966","unstructured":"McNaughton, R.: Testing and generating infinite sequences by a finite automaton. Inf. Contr.\u00a09, 521\u2013530 (1966)","journal-title":"Inf. Contr."},{"key":"35_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0168-0072(93)90036-D","volume":"65","author":"R. McNaughton","year":"1993","unstructured":"McNaughton, R.: Infinite games played on finite graphs. Ann. Pure Appl. Logic\u00a065, 149\u2013184 (1993)","journal-title":"Ann. Pure Appl. Logic"},{"volume-title":"Sequential Machines \u2013 Selected Papers","year":"1963","key":"35_CR15","unstructured":"Moore, E.F. (ed.): Sequential Machines \u2013 Selected Papers. Addison-Wesley, Reading, Mass (1963)"},{"key":"35_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-16066-3_15","volume-title":"Computation Theory","author":"A.W. Mostowski","year":"1985","unstructured":"Mostowski, A.W.: Regular expressions for infinite trees and a standard form of automata. In: Skowron, A. (ed.) SCT 1984. LNCS, vol.\u00a0208, pp. 157\u2013168. Springer, Heidelberg (1985)"},{"key":"35_CR17","first-page":"3","volume-title":"Proc. 4th IEEE Ann. Symp. on Switching Circuit Theory and Logical Design","author":"D.E. Muller","year":"1963","unstructured":"Muller, D.E.: Infinite sequences and finite machines. In: Proc. 4th IEEE Ann. Symp. on Switching Circuit Theory and Logical Design, pp. 3\u201316. IEEE Press, Los Alamitos (1963)"},{"key":"35_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(94)00214-4","volume":"141","author":"D.E. Muller","year":"1995","unstructured":"Muller, D.E., Schupp, P.E.: Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the results of Rabin, McNaughton, and Safra. Theor. Comput. Sci.\u00a0141, 69\u2013107 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"35_CR19","unstructured":"Myhill, J.: Finite automata and the representation of events, WADC Tech. Rep. 57-624, pp. 112-137 (1957)"},{"key":"35_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. Trans. Amer. Math. Soc.\u00a0141, 1\u201335 (1969)","journal-title":"Trans. Amer. Math. Soc."},{"key":"35_CR21","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Automata on infinite objects and Church\u2019s Problem, Amer. Math. Soc., Providence RI (1972)","DOI":"10.1090\/cbms\/013"},{"key":"35_CR22","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Develop.\u00a03, 114\u2013125 (1959)","journal-title":"IBM J. Res. Develop."},{"key":"35_CR23","first-page":"319","volume-title":"Proc. 29th Ann. Symp.on Foundations of Computer Science","author":"S. Safra","year":"1988","unstructured":"Safra, S.: On the complexity of omega-automata. In: Proc. 29th Ann. Symp.on Foundations of Computer Science, White Plains, New York, pp. 319\u2013327. IEEE Computer Society Press, Los Alamitos (1988)"},{"key":"35_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-60275-5","volume-title":"STACS 95","author":"W. Thomas","year":"1995","unstructured":"Thomas, W.: On the synthesis of strategies in infinite games. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol.\u00a0900, pp. 1\u201313. Springer, Heidelberg (1995)"},{"key":"35_CR25","unstructured":"Thomas, W.: Solution of Church\u2019s Problem: A tutorial. In: Apt, K., van Rooij, R. (eds.) New Perspectives on Games and Interaction, vol.\u00a05, Amsterdam Univ. Press, Texts on Logic and Games (to appear)"},{"key":"35_CR26","first-page":"1005","volume":"112","author":"B.A. Trakhtenbrot","year":"1957","unstructured":"Trakhtenbrot, B.A.: On operators realizable in logical nets. Dokl. Akad. Naut. SSSR\u00a0112, 1005\u20131007 (1957) (in Russian)","journal-title":"Dokl. Akad. Naut. SSSR"},{"key":"35_CR27","first-page":"646","volume":"118","author":"B.A. Trakhtenbrot","year":"1958","unstructured":"Trakhtenbrot, B.A.: Synthesis of logical nets whose operators are described of monadic predicates. Dokl. Akad. Naut. SSSR\u00a0118, 646\u2013649 (1958) (in Russian)","journal-title":"Dokl. Akad. Naut. SSSR"},{"key":"35_CR28","volume-title":"Finite Automata. Behavior and Synthesis","author":"B.A. Trakhtenbrot","year":"1973","unstructured":"Trakhtenbrot, B.A., Barzdin, Ya.M.: Finite Automata. Behavior and Synthesis. North-Holland, Amsterdam (1973)"}],"container-title":["Lecture Notes in Computer Science","Pillars of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78127-1_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:58:42Z","timestamp":1619521122000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78127-1_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540781264","9783540781271"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78127-1_35","relation":{},"subject":[]}}