{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T09:51:37Z","timestamp":1719827497443},"reference-count":40,"publisher":"EDP Sciences","issue":"1","funder":[{"name":"JSPS KAKENHI","award":["26540001","15H03634"],"award-info":[{"award-number":["26540001","15H03634"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1051\/ita\/2017006","type":"journal-article","created":{"date-parts":[[2017,7,7]],"date-time":"2017-07-07T07:04:08Z","timestamp":1499411048000},"page":"29-50","source":"Crossref","is-referenced-by-count":1,"title":["The determinacy strength of pushdown<i>\u03c9<\/i>-languages"],"prefix":"10.1051","volume":"51","author":[{"given":"Wenjuan","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuyuki","family":"Tanaka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2017,7,7]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"R. Alur and P. Madhusudan, Visibly pushdown languages, in Proc. of the 36th Annual ACM Symposium on Theory of Computing, STOC\u201904 (2004) 202\u2013211.","DOI":"10.1145\/1007352.1007390"},{"key":"R2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-4(4:16)2008","volume":"4","author":"Bollig","year":"2008","journal-title":"Log. Methods Comput. Sci."},{"key":"R3","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1090\/S0002-9947-1969-0280205-0","volume":"138","author":"B\u00fcchi","year":"1969","journal-title":"Trans. Amer. Math. Soc."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"T. Cachat, Higher order pushdown automata, the Caucal hierarchy of graphs and parity games, in International Colloquium on Automata, Languages, and Programming. Springer Berlin Heidelberg (2003) 556\u2013569.","DOI":"10.1007\/3-540-45061-0_45"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"T. Cachat, J. Duparc and W. Thomas, Solving pushdown games with a \\hbox{${\\rm \\Sigma}^0_3$}\u03a330 winning condition, in International Workshop on Computer Science Logic. Springer Berlin Heidelberg (2002) 322\u2013336.","DOI":"10.1007\/3-540-45793-3_22"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Carayol, M. Hague, A. Meyer, C.H. Ong and O. Serre, Winning regions of higher-order pushdown games, in LICS \u201908 Proc. of the 2008 23rd Annual IEEE Symposium on Logic in Computer Science (2008) 193\u2013204.","DOI":"10.1109\/LICS.2008.41"},{"key":"R7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2016.08.012","volume":"656","author":"Carotenuto","year":"2016","journal-title":"Theoret. Comput. Sci."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"D. Carotenuto, A. Murano and A. Peron, 2-visibly pushdown automata, in International Conference Developments in Language Theory. Springer Berlin Heidelberg (2007) 132\u2013144.","DOI":"10.1007\/978-3-540-73208-2_15"},{"key":"R9","first-page":"1","volume":"3","author":"Chadha","year":"2011","journal-title":"Log. Methods Comput. Sci."},{"key":"R10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/S0022-0000(77)80004-4","volume":"15","author":"Cohen","year":"1977","journal-title":"J. Comput. Syst. Sci."},{"key":"R11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(93)90349-X","volume":"110","author":"Engelfriet","year":"1993","journal-title":"Theoret. Comput. Sci."},{"key":"R12","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1016\/j.apal.2016.05.005","volume":"167","author":"Finkel","year":"2016","journal-title":"Ann. Pure Appl. Logic"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"O. Finkel, Topological complexity of context free \u03c9-languages: A survey, in Language, Culture, Computation: Studies in Honor of Yaacov Choueka, vol. 8001 of Lect. Notes Comput. Sci. Springer (2014) 50\u201377.","DOI":"10.1007\/978-3-642-45321-2_4"},{"key":"R14","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.2178\/jsl.7804050","volume":"78","author":"Finkel","year":"2013","journal-title":"J. Symb. Log."},{"key":"R15","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1017\/S0960129506005597","volume":"16","author":"Finkel","year":"2006","journal-title":"Math. Struct. Comput. Sci."},{"key":"R16","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0304-3975(02)00327-4","volume":"299","author":"Finkel","year":"2003","journal-title":"Theoret. Comput. Sci."},{"key":"R17","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1016\/S0304-3975(00)00405-9","volume":"262","author":"Finkel","year":"2001","journal-title":"Theoret. Comput. Sci."},{"key":"R18","doi-asserted-by":"crossref","first-page":"685","DOI":"10.2307\/2273508","volume":"43","author":"Harrington","year":"1978","journal-title":"J. Symb. Log."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"D.R. Hirschfeldt, Slicing the truth: On the computable and reverse mathematics of combinatorial principles. In Vol. 28 of Lect. Notes Ser., edited by Institute for Math. Sci., National University of Singapore. World Scientific (2014).","DOI":"10.1142\/9208"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"E. Jeandel, On immortal configurations in Turing machines, in Conference on Computability in Europe. Vol. 7318 of Lect. Notes Comput. Sci. Springer Berlin Heidelberg (2012) 334\u2013343","DOI":"10.1007\/978-3-642-30870-3_34"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"C. L\u00f6ding, P. Madhusudan and O. Serre, Visibly pushdown games, in Proc. of Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2004. Springer Berlin Heidelberg (2005) 408\u2013420.","DOI":"10.1007\/978-3-540-30538-5_34"},{"key":"R22","doi-asserted-by":"crossref","first-page":"363","DOI":"10.2307\/1971035","volume":"102","author":"Martin","year":"1975","journal-title":"Ann. Math."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"D.A. Martin, Measurable cardinals and analytic games. Fund. Math. 66 (1969\/1970) 287\u2013291.","DOI":"10.4064\/fm-66-3-287-291"},{"key":"R24","doi-asserted-by":"crossref","first-page":"452","DOI":"10.2178\/jsl\/1185803618","volume":"72","author":"MedSalem","year":"2007","journal-title":"J. Symb. Log."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"A. Montalb\u00e1n and R.A. Shore, The limits of determinacy in second order arithmetic, in Proc. London Math. Soc. 104 (2012) 223\u2013252.","DOI":"10.1112\/plms\/pdr022"},{"key":"R26","doi-asserted-by":"crossref","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"Minsky","year":"1961","journal-title":"Ann. Math."},{"key":"R27","unstructured":"M.L. Minsky, Computation: finite and infinite machines. Prentice-Hall, Inc. (1967)."},{"key":"R28","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1002\/malq.200610041","volume":"53","author":"Nemoto","year":"2007","journal-title":"MLQ Math. Log. Q."},{"key":"R29","doi-asserted-by":"crossref","first-page":"940","DOI":"10.1017\/jsl.2015.2","volume":"80","author":"Schweber","year":"2015","journal-title":"J. Symb. Log."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"O. Serre, Games with winning conditions of high Borel complexity, in International Colloquium on Automata, Languages, and Programming. Vol. 3142 of Lect. Notes Math. Springer Berlin Heidelberg (2004) 1150\u20131162.","DOI":"10.1007\/978-3-540-27836-8_95"},{"key":"R31","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/j.tcs.2005.10.024","volume":"350","author":"Serre","year":"2006","journal-title":"Theoret. Comput. Sci."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"S.G. Simpson, Subsystems of second order arithmetic. Perspectives in Logic. Association for Symbolic Logic, Poughkeepsie, NY, 2nd edition. Cambridge University Press, Cambridge (2009).","DOI":"10.1017\/CBO9780511581007"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"L. Staiger, \u03c9-languages,in Chapter 6 of the Handbook of Formal Languages. Vol. 3, edited by G. Rozenberg and A. Salomaa. Springer Verlag, Berlin (1997) 339\u2013387.","DOI":"10.1007\/978-3-642-59126-6_6"},{"key":"R34","unstructured":"J.R. Steel, Determinateness and subsystems of analysis. Ph.D. thesis, University of California, Berkeley (1977)."},{"key":"R35","unstructured":"K. Tanaka, Descriptive set theory and subsystems of analysis. Ph.D. thesis, University of California, Berkeley (1986)."},{"key":"R36","doi-asserted-by":"crossref","unstructured":"S.L. Torre, M. Napoli and G. Parlato, A unifying approach for multistack pushdown automata.Math. Foundations Comput. Sci. Springer Berlin Heidelberg (2014) 377\u2013389.","DOI":"10.1007\/978-3-662-44522-8_32"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"S.L. Torre, P. Madhusudan and G. Parlato, A robust class of context-sensitive languages, in 22nd Annual IEEE Symposium on Logic in Comput. Sci. IEEE Ph.D. thesis, University (2007) 161\u2013170.","DOI":"10.1109\/LICS.2007.9"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"W. Thomas, Infinite games and verification (extended abstract of a tutorial). Lect. Notes Comput. Sci. (2002) 58\u201364.","DOI":"10.1007\/3-540-45657-0_5"},{"key":"R39","unstructured":"I. Walukiewicz, Pushdown processes: Games and model-checking, in International Conference on Computer Aided Verification. Springer Berlin Heidelberg (1996) 62\u201374."},{"key":"R40","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1006\/inco.2000.2894","volume":"164","author":"Walukiewicz","year":"2001","journal-title":"Inf. Comput."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2017006\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T22:02:49Z","timestamp":1569708169000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2017006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":40,"journal-issue":{"issue":"1"},"alternative-id":["ita160068"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2017006","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}