{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T18:10:37Z","timestamp":1725905437495},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319628080"},{"type":"electronic","value":"9783319628097"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-62809-7_4","type":"book-chapter","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T08:37:57Z","timestamp":1500539877000},"page":"75-79","source":"Crossref","is-referenced-by-count":0,"title":["Connecting Decidability and Complexity for\u00a0MSO Logic"],"prefix":"10.1007","author":[{"given":"Micha\u0142","family":"Skrzypczak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,21]]},"reference":[{"key":"4_CR1","unstructured":"Blumensath, A., Colcombet, T., Parys, P.: On a fragment of AMSO and tiling systems. In: STACS, pp. 19:1\u201319:14 (2016)"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-30124-0_7","volume-title":"Computer Science Logic","author":"M Boja\u0144czyk","year":"2004","unstructured":"Boja\u0144czyk, M.: A bounding quantifier. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol. 3210, pp. 41\u201355. Springer, Heidelberg (2004). doi: 10.1007\/978-3-540-30124-0_7"},{"issue":"3","key":"4_CR3","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1007\/s00224-010-9279-2","volume":"48","author":"M Boja\u0144czyk","year":"2011","unstructured":"Boja\u0144czyk, M.: Weak MSO with the unbounding quantifier. Theor. Comput. Syst. 48(3), 554\u2013576 (2011)","journal-title":"Theor. Comput. Syst."},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-662-43951-7_4","volume-title":"Automata, Languages, and Programming","author":"M Boja\u0144czyk","year":"2014","unstructured":"Boja\u0144czyk, M.: Weak MSO+U with path quantifiers over infinite trees. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 38\u201349. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-43951-7_4"},{"key":"4_CR5","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Bounds in $$\\omega $$ -regularity. In: LICS, pp. 285\u2013296 (2006)"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-662-43951-7_5","volume-title":"Automata, Languages, and Programming","author":"M Boja\u0144czyk","year":"2014","unstructured":"Boja\u0144czyk, M., Gogacz, T., Michalewski, H., Skrzypczak, M.: On the decidability of MSO+U on infinite trees. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 50\u201361. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-43951-7_5"},{"key":"4_CR7","unstructured":"Boja\u0144czyk, M., Parys, P., Toru\u0144czyk, S.: The MSO+U theory of (n, $$<$$ ) is undecidable. In: STACS, pp. 1\u20138 (2016)"},{"key":"4_CR8","unstructured":"Boja\u0144czyk, M., Toru\u0144czyk, S.: Deterministic automata and extensions of weak MSO. In: FSTTCS, pp. 73\u201384 (2009)"},{"key":"4_CR9","first-page":"1","volume-title":"The Collected Works of J. Richard B\u00fcchi,","author":"JR B\u00fcchi","year":"1962","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second-order arithmetic. In: Lane, S.M., Siefkes, D. (eds.) The Collected Works of J. Richard B\u00fcchi, pp. 1\u201311. Springer, New York (1962)"},{"key":"4_CR10","first-page":"662","volume":"8","author":"A Carayol","year":"2010","unstructured":"Carayol, A., L\u00f6ding, C., Niwi\u0144ski, D., Walukiewicz, I.: Choice functions and well-orderings over the infinite binary tree. Cent. Europ. J. of Math. 8, 662\u2013682 (2010)","journal-title":"Cent. Europ. J. of Math."},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-642-22012-8_9","volume-title":"Automata, Languages and Programming","author":"O Carton","year":"2011","unstructured":"Carton, O., Colcombet, T., Puppis, G.: Regular languages of words over countable linear orderings. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 125\u2013136. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-22012-8_9"},{"key":"4_CR12","unstructured":"Friedman, H.: Some systems of second order arithmetic and their use. pp. 235\u2013242 (1975)"},{"key":"4_CR13","volume-title":"The Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axioms of Set Theory","author":"K G\u00f6del","year":"1940","unstructured":"G\u00f6del, K.: The Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axioms of Set Theory. Princeton University Press, New Jersy (1940)"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-662-44522-8_26","volume-title":"Mathematical Foundations of Computer Science 2014","author":"T Gogacz","year":"2014","unstructured":"Gogacz, T., Michalewski, H., Mio, M., Skrzypczak, M.: Measure properties of game tree languages. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014. LNCS, vol. 8634, pp. 303\u2013314. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-44522-8_26"},{"issue":"2\u20133","key":"4_CR15","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0003-4843(82)90004-3","volume":"23","author":"Y Gurevich","year":"1982","unstructured":"Gurevich, Y., Shelah, S.: Monadic theory of order and topology in ZFC. Annal. Math. Logic 23(2\u20133), 179\u2013198 (1982)","journal-title":"Annal. Math. Logic"},{"issue":"1","key":"4_CR16","doi-asserted-by":"crossref","first-page":"87","DOI":"10.3233\/FI-2012-728","volume":"119","author":"S Hummel","year":"2012","unstructured":"Hummel, S., Skrzypczak, M.: The topological complexity of MSO+U and related automata models. Fundam. Inf. 119(1), 87\u2013111 (2012)","journal-title":"Fundam. Inf."},{"key":"4_CR17","volume-title":"Set Theory","author":"T Jech","year":"2002","unstructured":"Jech, T.: Set Theory. Springer, Hiedelberg (2002)"},{"key":"4_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4190-4","volume-title":"Classical descriptive set theory","author":"A Kechris","year":"1995","unstructured":"Kechris, A.: Classical descriptive set theory. Springer, New York (1995)"},{"key":"4_CR19","first-page":"415","volume":"35","author":"AN Kolmogorov","year":"1928","unstructured":"Kolmogorov, A.N.: Operations sur des ensembles. Mat. Sb. 35, 415\u2013422 (1928). (in Russian, summary in French)","journal-title":"Mat. Sb."},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Ko\u0142odziejczyk, L.A., Michalewski, H.: How unprovable is Rabin\u2019s decidability theorem? In: LICS, pp. 788\u2013797 (2016)","DOI":"10.1145\/2933575.2934543"},{"key":"4_CR21","unstructured":"Ko\u0142odziejczyk, L.A., Michalewski, H., Pradic, P., Skrzypczak, M.: The logical strength of B\u00fcchi\u2019s decidability theorem. In: CSL, pp. 36:1\u201336:16 (2016)"},{"issue":"2","key":"4_CR22","doi-asserted-by":"crossref","first-page":"609","DOI":"10.2178\/jsl\/1333566640","volume":"77","author":"J Liu","year":"2012","unstructured":"Liu, J.: $${\\sf RT}^{2}_{2}$$ does not imply $${\\sf WKL}_{0}$$ . J. Symbol. Logic 77(2), 609\u2013620 (2012)","journal-title":"J. Symbol. Logic"},{"issue":"5","key":"4_CR23","doi-asserted-by":"crossref","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. Control 9(5), 521\u2013530 (1966)","journal-title":"Inf. Control"},{"key":"4_CR24","first-page":"1","volume":"141","author":"MO Rabin","year":"1969","unstructured":"Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. Am. Math. Soc. 141, 1\u201335 (1969)","journal-title":"Trans. Am. Math. Soc."},{"issue":"6","key":"4_CR25","doi-asserted-by":"crossref","first-page":"870","DOI":"10.1016\/j.ic.2006.12.004","volume":"205","author":"A Rabinovich","year":"2007","unstructured":"Rabinovich, A.: On decidability of monadic logic of order over the naturals extended by monadic predicates. Inf. Comput. 205(6), 870\u2013889 (2007)","journal-title":"Inf. Comput."},{"issue":"3","key":"4_CR26","doi-asserted-by":"crossref","first-page":"379","DOI":"10.2307\/1971037","volume":"102","author":"S Shelah","year":"1975","unstructured":"Shelah, S.: The monadic theory of order. Annal. Math. 102(3), 379\u2013419 (1975)","journal-title":"Annal. Math."},{"key":"4_CR27","series-title":"Perspectives in Logic","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581007","volume-title":"Subsystems of Second Order Arithmetic","author":"SG Simpson","year":"2009","unstructured":"Simpson, S.G.: Subsystems of Second Order Arithmetic. Perspectives in Logic, 2nd edn. Cambridge University Press, Association for Symbolic Logic, Cambridge, Poughkeepsie (2009)","edition":"2"},{"key":"4_CR28","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 Reflections and Perspectives","author":"W Thomas","year":"1994","unstructured":"Thomas, W., Lescow, H.: Logical specifications of infinite computations. In: Bakker, J.W., Roever, W.-P., Rozenberg, G. (eds.) REX 1993. LNCS, vol. 803, pp. 583\u2013621. Springer, Heidelberg (1994). doi: 10.1007\/3-540-58043-3_29"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62809-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,13]],"date-time":"2020-10-13T01:19:20Z","timestamp":1602551960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-62809-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319628080","9783319628097"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62809-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}