{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:17:17Z","timestamp":1760203037604,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030134341"},{"type":"electronic","value":"9783030134358"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-13435-8_27","type":"book-chapter","created":{"date-parts":[[2019,2,13]],"date-time":"2019-02-13T15:18:36Z","timestamp":1550071116000},"page":"368-380","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Extensions of the Caucal Hierarchy?"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7247-1408","authenticated-orcid":false,"given":"Pawe\u0142","family":"Parys","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,2,14]]},"reference":[{"key":"27_CR1","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). \n                      https:\/\/doi.org\/10.1007\/978-3-540-30124-0_7"},{"issue":"3","key":"27_CR2","doi-asserted-by":"publisher","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. Theory Comput. Syst. 48(3), 554\u2013576 (2011). \n                      https:\/\/doi.org\/10.1007\/s00224-010-9279-2","journal-title":"Theory Comput. Syst."},{"key":"27_CR3","doi-asserted-by":"publisher","unstructured":"Boja\u0144czyk, M., Parys, P., Toru\u0144czyk, S.: The MSO+U theory of (N, \n                      \n                        \n                      \n                      $$<$$\n                    ) is undecidable. In: STACS, pp. 21:1\u201321:8 (2016). \n                      https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.21","DOI":"10.4230\/LIPIcs.STACS.2016.21"},{"key":"27_CR4","doi-asserted-by":"publisher","unstructured":"Boja\u0144czyk, M., Toru\u0144czyk, S.: Weak MSO+U over infinite trees. In: STACS, pp. 648\u2013660 (2012). \n                      https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2012.648","DOI":"10.4230\/LIPIcs.STACS.2012.648"},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/3-540-45061-0_45","volume-title":"Automata, Languages and Programming","author":"T Cachat","year":"2003","unstructured":"Cachat, T.: Higher order pushdown automata, the Caucal hierarchy of graphs and parity games. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 556\u2013569. Springer, Heidelberg (2003). \n                      https:\/\/doi.org\/10.1007\/3-540-45061-0_45"},{"key":"27_CR6","unstructured":"Carayol, A.: Automates infinis, logiques et langages. Ph.D. thesis. Universit\u00e9 de Rennes 1 (2006)"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-540-24597-1_10","volume-title":"FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science","author":"A Carayol","year":"2003","unstructured":"Carayol, A., W\u00f6hrle, S.: The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol. 2914, pp. 112\u2013123. Springer, Heidelberg (2003). \n                      https:\/\/doi.org\/10.1007\/978-3-540-24597-1_10"},{"key":"27_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-61440-0_128","volume-title":"Automata, Languages and Programming","author":"D Caucal","year":"1996","unstructured":"Caucal, D.: On infinite transition graphs having a decidable monadic theory. In: Meyer, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 194\u2013205. Springer, Heidelberg (1996). \n                      https:\/\/doi.org\/10.1007\/3-540-61440-0_128"},{"key":"27_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/3-540-45687-2_13","volume-title":"Mathematical Foundations of Computer Science 2002","author":"D Caucal","year":"2002","unstructured":"Caucal, D.: On infinite terms having a decidable monadic theory. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 165\u2013176. Springer, Heidelberg (2002). \n                      https:\/\/doi.org\/10.1007\/3-540-45687-2_13"},{"key":"27_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"901","DOI":"10.1007\/978-3-540-73420-8_77","volume-title":"Automata, Languages and Programming","author":"T Colcombet","year":"2007","unstructured":"Colcombet, T.: A combinatorial theorem for trees. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 901\u2013912. Springer, Heidelberg (2007). \n                      https:\/\/doi.org\/10.1007\/978-3-540-73420-8_77"},{"key":"27_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/978-3-642-38536-0_34","volume-title":"Computer Science \u2013 Theory and Applications","author":"T Colcombet","year":"2013","unstructured":"Colcombet, T.: Composition with algebra at the background - on a question by Gurevich and Rabinovich on the monadic theory of linear orderings. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 391\u2013404. Springer, Heidelberg (2013). \n                      https:\/\/doi.org\/10.1007\/978-3-642-38536-0_34"},{"key":"27_CR12","doi-asserted-by":"publisher","unstructured":"Colcombet, T., L\u00f6ding, C.: Transforming structures by set interpretations. Log. Methods Comput. Sci. 3(2) (2007). \n                      https:\/\/doi.org\/10.2168\/LMCS-3(2:4)2007","DOI":"10.2168\/LMCS-3(2:4)2007"},{"issue":"1","key":"27_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(94)90268-2","volume":"126","author":"B Courcelle","year":"1994","unstructured":"Courcelle, B.: Monadic second-order definable graph transductions: a survey. Theoret. Comput. Sci. 126(1), 53\u201375 (1994). \n                      https:\/\/doi.org\/10.1016\/0304-3975(94)90268-2","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"27_CR14","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0168-0072(97)00048-1","volume":"92","author":"B Courcelle","year":"1998","unstructured":"Courcelle, B., Walukiewicz, I.: Monadic second-order logic, graph coverings and unfoldings of transition systems. Ann. Pure Appl. Logic 92(1), 35\u201362 (1998). \n                      https:\/\/doi.org\/10.1016\/S0168-0072(97)00048-1","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1","key":"27_CR15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0890-5401(91)90015-T","volume":"95","author":"J Engelfriet","year":"1991","unstructured":"Engelfriet, J.: Iterated stack automata and complexity classes. Inf. Comput. 95(1), 21\u201375 (1991). \n                      https:\/\/doi.org\/10.1016\/0890-5401(91)90015-T","journal-title":"Inf. Comput."},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"23","DOI":"10.4204\/EPTCS.77.4","volume":"77","author":"Axel Haddad","year":"2012","unstructured":"Haddad, A.: IO vs OI in higher-order recursion schemes. In: FICS, pp. 23\u201330 (2012). \n                      https:\/\/doi.org\/10.4204\/EPTCS.77.4","journal-title":"Electronic Proceedings in Theoretical Computer Science"},{"key":"27_CR17","doi-asserted-by":"publisher","unstructured":"Hague, M., Murawski, A.S., Ong, C.L., Serre, O.: Collapsible pushdown automata and recursion schemes. In: LICS, pp. 452\u2013461 (2008). \n                      https:\/\/doi.org\/10.1109\/LICS.2008.34","DOI":"10.1109\/LICS.2008.34"},{"issue":"1","key":"27_CR18","doi-asserted-by":"publisher","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. Inform. 119(1), 87\u2013111 (2012). \n                      https:\/\/doi.org\/10.3233\/FI-2012-728","journal-title":"Fundam. Inform."},{"key":"27_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-45931-6_15","volume-title":"Foundations of Software Science and Computation Structures","author":"T Knapik","year":"2002","unstructured":"Knapik, T., Niwi\u0144ski, D., Urzyczyn, P.: Higher-order pushdown trees are easy. In: Nielsen, M., Engberg, U. (eds.) FoSSaCS 2002. LNCS, vol. 2303, pp. 205\u2013222. Springer, Heidelberg (2002). \n                      https:\/\/doi.org\/10.1007\/3-540-45931-6_15"},{"key":"27_CR20","doi-asserted-by":"publisher","unstructured":"Ong, C.L.: On model-checking trees generated by higher-order recursion schemes. In: LICS, pp. 81\u201390 (2006). \n                      https:\/\/doi.org\/10.1109\/LICS.2006.38","DOI":"10.1109\/LICS.2006.38"},{"key":"27_CR21","doi-asserted-by":"publisher","unstructured":"Parys, P.: Variants of collapsible pushdown systems. In: CSL, pp. 500\u2013515 (2012). \n                      https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2012.500","DOI":"10.4230\/LIPIcs.CSL.2012.500"},{"key":"27_CR22","unstructured":"Parys, P.: Recursion schemes, the MSO logic, and the U quantifier (submitted). \n                      https:\/\/arxiv.org\/abs\/1810.04763"},{"key":"27_CR23","unstructured":"Parys, P.: A type system describing unboundedness (submitted). \n                      https:\/\/hal.archives-ouvertes.fr\/hal-01850934"},{"key":"27_CR24","doi-asserted-by":"publisher","unstructured":"Parys, P.: On the significance of the collapse operation. In: LICS, pp. 521\u2013530 (2012). \n                      https:\/\/doi.org\/10.1109\/LICS.2012.62","DOI":"10.1109\/LICS.2012.62"},{"issue":"2","key":"27_CR25","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/s00224-017-9769-6","volume":"61","author":"V Penelle","year":"2017","unstructured":"Penelle, V.: Rewriting higher-order stack trees. Theory Comput. Syst. 61(2), 536\u2013580 (2017). \n                      https:\/\/doi.org\/10.1007\/s00224-017-9769-6","journal-title":"Theory Comput. Syst."},{"issue":"1\u20132","key":"27_CR26","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0304-3975(01)00185-2","volume":"275","author":"I Walukiewicz","year":"2002","unstructured":"Walukiewicz, I.: Monadic second-order logic on tree-like structures. Theoret. Comput. Sci. 275(1\u20132), 311\u2013346 (2002). \n                      https:\/\/doi.org\/10.1016\/S0304-3975(01)00185-2","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-13435-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T22:47:57Z","timestamp":1558478877000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-13435-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030134341","9783030134358"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-13435-8_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"14 February 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Language and Automata Theory and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. Petersburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 March 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 March 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"lata2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/lata2019.irdta.eu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"98","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"31","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"5","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"6-7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}