{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T18:12:24Z","timestamp":1781892744718,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540323013","type":"print"},{"value":"9783540322887","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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":[[2006]]},"DOI":"10.1007\/11672142_24","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T08:27:54Z","timestamp":1141115274000},"page":"301-312","source":"Crossref","is-referenced-by-count":5,"title":["On the Accepting Power of 2-Tape B\u00fcchi Automata"],"prefix":"10.1007","author":[{"given":"Olivier","family":"Finkel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"24_CR1","volume-title":"Finite Automata, Behaviour and Synthesis, Nauka, Moscow, 1970 (English translation)","author":"Y.M. Barzdinand","year":"1973","unstructured":"Barzdinand, Y.M., Trakhtenbrot, B.A.: Finite Automata, Behaviour and Synthesis, Nauka, Moscow, 1970 (English translation). North Holland, Amsterdam (1973)"},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-45022-X_47","volume-title":"Automata, Languages and Programming","author":"M.-P. Bal","year":"2000","unstructured":"Bal, M.-P., Carton, O.: Determinization of Transducers over Infinite Words. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 561\u2013570. Springer, Heidelberg (2000)"},{"issue":"1","key":"24_CR3","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0304-3975(01)00214-6","volume":"292","author":"M.-P. B\u00e9al","year":"2003","unstructured":"B\u00e9al, M.-P., Carton, O., Prieur, C., Sakarovitch, J.: Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality. Theoretical Computer Science\u00a0292(1), 45\u201363 (2003)","journal-title":"Theoretical Computer Science"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Berstel, J.: Transductions and Context Free Languages. Teubner Verlag (1979)","DOI":"10.1007\/978-3-663-09367-1"},{"key":"24_CR5","unstructured":"B\u00fcchi, J.R.: On a Decision Method in Restricted Second Order Arithmetic, Logic Methodology and Philosophy of Science. In: Proc. 1960 Int. Congr., pp. 1\u201311. Stanford University Press (1962)"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/3-540-45793-3_22","volume-title":"Computer Science Logic","author":"T. Cachat","year":"2002","unstructured":"Cachat, T., Duparc, J., Thomas, W.: Solving Pushdown Games with a \u03a33 Winning Condition. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol.\u00a02471, pp. 322\u2013336. Springer, Heidelberg (2002)"},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(77)90049-4","volume":"5","author":"C. Choffrut","year":"1977","unstructured":"Choffrut, C.: Une Caract\u00e9risation des Fonctions S\u00e9quentielles et des Fonctions Sous-S\u00e9quentielles en tant que Relations Rationnelles. Theoretical Computer Science\u00a05, 325\u2013338 (1977)","journal-title":"Theoretical Computer Science"},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-60207-8_6","volume-title":"Jewels are Forever 1999","author":"C. Choffrut","year":"1999","unstructured":"Choffrut, C., Grigorieff, S.: Uniformization of Rational Relations. In: Karhumki, J., Maurer, H., Paun, G., Rozenberg, G. (eds.) Jewels are Forever 1999, pp. 59\u201371. Springer, Heidelberg (1999)"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Hoogeboom, H.J.: X-automata on \u03c9-Words. Theoretical Computer Science\u00a0110, 1\u201351 (1993)","DOI":"10.1016\/0304-3975(93)90349-X"},{"issue":"2","key":"24_CR10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1051\/ita:2003016","volume":"37","author":"O. Finkel","year":"2003","unstructured":"Finkel, O.: On the Topological Complexity of Infinitary Rational Relations. RAIRO-Theoretical Informatics and Applications\u00a037(2), 105\u2013113 (2003)","journal-title":"RAIRO-Theoretical Informatics and Applications"},{"issue":"2","key":"24_CR11","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1051\/ita:2003013","volume":"37","author":"O. Finkel","year":"2003","unstructured":"Finkel, O.: Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations. RAIRO-Theoretical Informatics and Applications\u00a037(2), 115\u2013126 (2003)","journal-title":"RAIRO-Theoretical Informatics and Applications"},{"key":"24_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-45066-1_12","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"O. Finkel","year":"2003","unstructured":"Finkel, O.: On Infinitary Rational Relations and Borel Sets. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) DMTCS 2003. LNCS, vol.\u00a02731, pp. 155\u2013167. Springer, Heidelberg (2003)"},{"key":"24_CR13","unstructured":"Finkel, O.: On Infinitary Rational Relations and the Borel Hierarchy, submitted to Logical Methods in Computer Science, 27 pages"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Finkel, O.: Borel Ranks and Wadge Degrees of Context Free \u03c9-Languages. In: Cooper, S.B., L\u00f6we, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol.\u00a03526, pp. 129\u2013138. Springer, Heidelberg (2005)","DOI":"10.1007\/11494645_17"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Finkel, O.: Borel Ranks and Wadge Degrees of Context Free \u03c9-Languages. In: Cooper, S.B., L\u00f6we, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol.\u00a03526, pp. 129\u2013138. Springer, Heidelberg (2005)","DOI":"10.1007\/11494645_17"},{"key":"24_CR16","unstructured":"Gire, F.: Relations Rationnelles Infinitaires, Th\u00e8se de troisi\u00e8me cycle, Universit\u00e9 Paris 7 (Septembre 1981)"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"Gire, F.: Une Extension aux Mots Infinis de la Notion de Transduction Rationnelle. In: 6th GI Conf. Lect. Notes in Comp. Sci, vol.\u00a0145, pp. 123\u2013139 (1983)","DOI":"10.1007\/BFb0009639"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Gire, F., Nivat, M.: Relations Rationnelles Infinitaires, Calcolo, vol.\u00a0XXI, pp. 91\u2013125 (1984)","DOI":"10.1007\/BF02575909"},{"key":"24_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4190-4","volume-title":"Classical Descriptive Set Theory","author":"A.S. Kechris","year":"1995","unstructured":"Kechris, A.S.: Classical Descriptive Set Theory. Springer, Heidelberg (1995)"},{"issue":"3","key":"24_CR20","doi-asserted-by":"publisher","first-page":"915","DOI":"10.2307\/2274751","volume":"54","author":"A.S. Kechris","year":"1989","unstructured":"Kechris, A.S., Marker, D., Sami, R.L.: $\\Pi_1^1$ Borel Sets. The Journal of Symbolic Logic\u00a054(3), 915\u2013920 (1989)","journal-title":"The Journal of Symbolic Logic"},{"key":"24_CR21","volume-title":"Topology","author":"K. Kuratowski","year":"1966","unstructured":"Kuratowski, K.: Topology. Academic Press, New York (1966)"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Landweber, L.H.: Decision Problems for \u03c9-Automata. Math. Syst. Theory\u00a03(4), 376\u2013384 (1969)","DOI":"10.1007\/BF01691063"},{"key":"24_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/3-540-58043-3_29","volume-title":"A Decade of Concurrency","author":"H. Lescow","year":"1994","unstructured":"Lescow, H., Thomas, W.: Logical Specifications of Infinite Computations. In: de Bakker, J.W., de Roever, W.-P., Rozenberg, G. (eds.) REX 1993. LNCS, vol.\u00a0803, pp. 583\u2013621. Springer, Heidelberg (1994)"},{"key":"24_CR24","doi-asserted-by":"crossref","DOI":"10.1515\/9783112546369","volume-title":"Algebraische Codierungstheorie - Theorie der Sequentiellen Codierungen","author":"R. Lindner","year":"1977","unstructured":"Lindner, R., Staiger, L.: Algebraische Codierungstheorie - Theorie der Sequentiellen Codierungen. Akademie-Verlag, Berlin (1977)"},{"key":"24_CR25","volume-title":"Descriptive Set Theory","author":"Y.N. Moschovakis","year":"1980","unstructured":"Moschovakis, Y.N.: Descriptive Set Theory. North-Holland, Amsterdam (1980)"},{"key":"24_CR26","series-title":"Pure and Applied Mathematics","volume-title":"Infinite Words, Automata, Semigroups, Logic and Games","author":"D. Perrin","year":"2004","unstructured":"Perrin, D., Pin, J.-E.: Infinite Words, Automata, Semigroups, Logic and Games. Pure and Applied Mathematics, vol.\u00a0141. Elsevier, Amsterdam (2004)"},{"key":"24_CR27","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02127803","volume":"16","author":"J.-E. Pin","year":"1996","unstructured":"Pin, J.-E.: Logic, Semigroups and Automata on Words. Annals of Mathematics and Artificial Intelligence\u00a016, 343\u2013384 (1996)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"24_CR28","unstructured":"Prieur, C.: Fonctions Rationnelles de Mots Infinis et Continuit\u00e9, Th\u00e8se de Doctorat, Universit\u00e9 Paris 7, Octobre (2000)"},{"key":"24_CR29","unstructured":"Simonnet, P.: Automates et Th\u00e9orie Descriptive, Th\u00e8se de Doctorat, Universit\u00e9 Paris 7 (March 1992)"},{"key":"24_CR30","unstructured":"Staiger, L.: Hierarchies of Recursive \u03c9-Languages. Jour. Inform. Process. Cybernetics EIK\u00a022(5\/6), 219\u2013241 (1986)"},{"key":"24_CR31","unstructured":"Staiger, L.: \u03c9-Languages. In: Rozenberg, G., Salomaa, A. (eds.) Chapter of the Handbook of Formal languages, vol.\u00a03, Springer, Berlin"},{"key":"24_CR32","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1002\/malq.19780243107","volume":"24","author":"L. Staiger","year":"1978","unstructured":"Staiger, L., Wagner, K.: Rekursive Folgenmengen I. Z. Math Logik Grundlag. Math.\u00a024, 523\u2013538 (1978)","journal-title":"Z. Math Logik Grundlag. Math."},{"key":"24_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/BFb0013115","volume-title":"Formal Properties of Finite Automata and Applications","author":"W. Thomas","year":"1989","unstructured":"Thomas, W.: Automata and Quantifier Hierarchies. In: Pin, J.E. (ed.) LITP 1988. LNCS, vol.\u00a0386, pp. 104\u2013119. Springer, Heidelberg (1989)"},{"key":"24_CR34","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Automata on Infinite Objects. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol.\u00a0B, pp. 133\u2013191. Elsevier, Amsterdam (1990)","DOI":"10.1016\/B978-0-444-88074-1.50009-3"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T16:31:28Z","timestamp":1683390688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/11672142_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}