{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T15:15:52Z","timestamp":1696346152478},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2008,7,29]],"date-time":"2008-07-29T00:00:00Z","timestamp":1217289600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2008,9]]},"DOI":"10.1007\/s00153-008-0101-7","type":"journal-article","created":{"date-parts":[[2008,7,28]],"date-time":"2008-07-28T03:42:45Z","timestamp":1217216565000},"page":"625-651","source":"Crossref","is-referenced-by-count":1,"title":["Topological complexity of locally finite \u03c9-languages"],"prefix":"10.1007","volume":"47","author":[{"given":"Olivier","family":"Finkel","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,7,29]]},"reference":[{"key":"101_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59207-2","volume-title":"The Classical Decision Problem","author":"E. B\u00f6rger","year":"1997","unstructured":"B\u00f6rger E., Gr\u00e4del E., Gurevich Y.: The Classical Decision Problem. Springer, Heidelberg (1997)"},{"key":"101_CR2","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1090\/S0002-9947-1969-0280205-0","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. Am. Math. Soc. 138, 295\u2013311 (1969)","journal-title":"Trans. Am. Math. Soc."},{"key":"101_CR3","doi-asserted-by":"crossref","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. Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik 6, 66\u201392 (1960)","journal-title":"Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik"},{"key":"101_CR4","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic, logic methodology and philosophy of science. In: Proceedings of the 1960 International Congress. Stanford University Press, pp. 1\u201311 (1962)"},{"key":"101_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BFb0082721","volume":"328","author":"J.R. B\u00fcchi","year":"1973","unstructured":"B\u00fcchi J.R., Siefkes D.: The monadic second order theory of all countable ordinals, decidable theories 2. Lect. Notes Math. 328, 1\u2013217 (1973)","journal-title":"Lect. Notes Math."},{"key":"101_CR6","unstructured":"Chang, C.C., Keisler, H.J.: Model Theory, American Elsevier Publishing Company, Inc., New York (1973) (3rd edn., North Holland, Amsterdam, 1990)"},{"key":"101_CR7","unstructured":"Duparc, J.: La Forme Normale des Bor\u00e9liens de Rang Fini. Ph.D. Thesis, Universit\u00e9 Paris 7 (1995)"},{"key":"101_CR8","unstructured":"Duparc, J.: The Normal Form of Borel Sets, Part 1: Borel Sets of Finite Rank. Comptes Rendus de l\u2019Acad\u00e9mie des Sciences, Paris, t.320, S\u00e9rie 1, pp. 651\u2013656 (1995)"},{"issue":"1","key":"101_CR9","doi-asserted-by":"crossref","first-page":"56","DOI":"10.2307\/2694911","volume":"66","author":"J. Duparc","year":"2001","unstructured":"Duparc J.: Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank. J. Symb. Log. 66(1), 56\u201386 (2001)","journal-title":"J. Symb. Log."},{"issue":"1\u20132","key":"101_CR10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/S0304-3975(00)00111-0","volume":"257","author":"J. Duparc","year":"2001","unstructured":"Duparc J., Finkel O., Ressayre J-P.: Computer science and the fine structure of Borel sets. Theor. Comput. Sci. 257(1\u20132), 85\u2013105 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"101_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(93)90349-X","volume":"110","author":"J. Engelfriet","year":"1993","unstructured":"Engelfriet J., Hoogeboom H.J.: X-automata on \u03c9-words. Theor. Comput. Sci. 110(1), 1\u201351 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"101_CR12","unstructured":"Finkel, O.: Langages de B\u00fcchi et \u03c9-Langages Locaux. Comptes Rendus de l\u2019Acad\u00e9mie des Sciences, Paris, t.309, S\u00e9rie 1, pp. 991\u2013994 (1989)"},{"key":"101_CR13","unstructured":"Finkel, O.: Th\u00e9orie des Mod\u00e8les des Formules Locales et Etude des Langages Formels qu\u2019elles D\u00e9finissent. Ph.D. Thesis, Universit\u00e9 Paris 7 (1993)"},{"issue":"2","key":"101_CR14","doi-asserted-by":"crossref","first-page":"563","DOI":"10.2307\/2275676","volume":"61","author":"O. Finkel","year":"1996","unstructured":"Finkel O., Ressayre J-P.: Stretchings. J. Symb. Log. 61(2), 563\u2013585 (1996)","journal-title":"J. Symb. Log."},{"issue":"1\u20132","key":"101_CR15","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0304-3975(99)00286-8","volume":"255","author":"O. Finkel","year":"2001","unstructured":"Finkel O.: Locally finite languages. Theor. Comput. Sci. 255(1\u20132), 223\u2013261 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"101_CR16","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1016\/S0304-3975(00)00405-9","volume":"262","author":"O. Finkel","year":"2001","unstructured":"Finkel O.: Topological properties of omega context free languages. Theor. Comput. Sci. 262(1\u20132), 669\u2013697 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"101_CR17","unstructured":"Finkel, O.: Locally Finite \u03c9-Languages and Borel Sets of Infinite Rank (preprint)"},{"issue":"1","key":"101_CR18","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.tcs.2004.03.025","volume":"322","author":"O. Finkel","year":"2004","unstructured":"Finkel O.: Closure properties of locally finite omega languages. Theor. Comput. Sci. 322(1), 69\u201384 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"101_CR19","doi-asserted-by":"crossref","unstructured":"Finkel, O.: On decidability properties of local sentences. In: Proceedings of the 11th Workshop on Logic, Language, Information and Computation WoLLIC 2004. Electronic Notes in Theoretical Computer Science, vol. 123, pp. 75\u201392. Elsevier, Amsterdam (2005)","DOI":"10.1016\/j.entcs.2004.05.013"},{"issue":"2","key":"101_CR20","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.tcs.2006.08.004","volume":"364","author":"O. Finkel","year":"2006","unstructured":"Finkel O.: On decidability properties of local sentences. Theor. Comput. Sci. 364(2), 196\u2013211 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"101_CR21","unstructured":"Hopcroft, J.E., Ullman, J.D.: Formal Languages and their Relation to Automata. Addison-Wesley Publishing Company, Reading (1969)"},{"key":"101_CR22","doi-asserted-by":"crossref","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)"},{"key":"101_CR23","volume-title":"Topology","author":"K. Kuratowski","year":"1966","unstructured":"Kuratowski K.: Topology. Academic Press, New York (1966)"},{"issue":"3","key":"101_CR24","doi-asserted-by":"crossref","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. J. Symb. Log. 54(3), 915\u2013920 (1989)","journal-title":"J. Symb. Log."},{"issue":"4","key":"101_CR25","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/BF01691063","volume":"3","author":"L.H. Landweber","year":"1969","unstructured":"Landweber L.H.: Decision problems for \u03c9-automata. Math. Syst. Theory 3(4), 376\u2013384 (1969)","journal-title":"Math. Syst. Theory"},{"key":"101_CR26","doi-asserted-by":"crossref","unstructured":"Lescow, H., Thomas, W.: Logical specifications of infinite computations. In: A Decade of Concurrency. de Bakker, J.W., et al. (eds.) Lecture Notes in Computer Science, vol. 803, pp. 583\u2013621. Springer, Heidelberg (1994)","DOI":"10.1007\/3-540-58043-3_29"},{"key":"101_CR27","doi-asserted-by":"crossref","unstructured":"Meyer, A.R.: Weak monadic second order theory of successor is not elementary recursive, logic colloquium (Boston, Mass., 1972\u20131973). Lecture Notes in Mathematics, vol. 453, pp. 132\u2013154. Springer, Berlin (1975)","DOI":"10.1007\/BFb0064872"},{"key":"101_CR28","volume-title":"Descriptive Set Theory","author":"Y.N. Moschovakis","year":"1980","unstructured":"Moschovakis Y.N.: Descriptive Set Theory. North-Holland, Amsterdam (1980)"},{"key":"101_CR29","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0304-3975(85)90136-7","volume":"39","author":"M. Parigot","year":"1985","unstructured":"Parigot M., Pelz E.: A logical approach to Petri net languages. Theor. Comput. Sci. 39, 155\u2013169 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"101_CR30","volume-title":"Infinite words, automata, semigroups, logic and games. Pure and Applied Mathematics, vol. 141","author":"D. Perrin","year":"2004","unstructured":"Perrin D., Pin J.-E.: Infinite words, automata, semigroups, logic and games. Pure and Applied Mathematics, vol. 141 . Elsevier, Amsterdam (2004)"},{"key":"101_CR31","doi-asserted-by":"crossref","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. Ann. Math. Artif. Intell. 16, 343\u2013384 (1996)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"4","key":"101_CR32","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1017\/S0022481200027894","volume":"53","author":"J-P. Ressayre","year":"1988","unstructured":"Ressayre J-P.: Formal languages defined by the underlying structure of their words. J. Symb. Log. 53(4), 1009\u20131026 (1988)","journal-title":"J. Symb. Log."},{"key":"101_CR33","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers","year":"1967","unstructured":"Rogers H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)"},{"key":"101_CR34","unstructured":"Safra, S.: Complexity of Automata on Infinite Objects. Ph.D. Thesis, Weizmann Institute of Science, Rehovot, Israel (1989)"},{"key":"101_CR35","volume-title":"Mathematical Logic","author":"J.R. Shoenfield","year":"1967","unstructured":"Shoenfield J.R.: Mathematical Logic. Addison-Wesley, Reading (1967)"},{"key":"101_CR36","unstructured":"Simonnet, P.: Automates et Th\u00e9orie Descriptive. Ph.D. Thesis, Universit\u00e9 Paris 7, March (1992)"},{"key":"101_CR37","unstructured":"Simonnet, P.: Automate d\u2019Arbres Infinis et Choix Bor\u00e9lien. Comptes Rendus de l\u2019Acad\u00e9mie des Sciences, Paris, t.316, S\u00e9rie 1, pp. 97\u2013100, (1993)"},{"key":"101_CR38","doi-asserted-by":"crossref","unstructured":"Staiger L. (1997) \u03c9-Languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol 3, pp. 339\u2013388. Springer, Berlin (1997)","DOI":"10.1007\/978-3-642-59126-6_6"},{"key":"101_CR39","first-page":"133","volume-title":"Handbook of Theoretical Computer Science vol. B","author":"W. Thomas","year":"1990","unstructured":"Thomas W.: Automata on Infinite Objects. In: Van Leeuwen, J.(eds) Handbook of Theoretical Computer Science vol. B, pp. 133\u2013191. Elsevier, Amsterdam (1990)"},{"key":"101_CR40","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Languages, vol. 3.","author":"W. Thomas","year":"1997","unstructured":"Thomas W.: Languages, automata and logic. In: Rozenberg, G., Salomaa, A.(eds) Handbook of Formal Languages, vol. 3., pp. 389\u2013456. Springer, Heidelberg (1997)"},{"key":"101_CR41","unstructured":"Wadge, W.W.: Reducibility and determinateness on the Baire space. Ph.D. Thesis, Berkeley (1983)"},{"key":"101_CR42","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0019-9958(79)90653-3","volume":"43","author":"K. Wagner","year":"1979","unstructured":"Wagner K.: On omega regular sets. Inf. Control 43, 123\u2013177 (1979)","journal-title":"Inf. Control"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-008-0101-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00153-008-0101-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-008-0101-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T15:36:42Z","timestamp":1558625802000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00153-008-0101-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,29]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["101"],"URL":"https:\/\/doi.org\/10.1007\/s00153-008-0101-7","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7,29]]}}}