{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:30:32Z","timestamp":1767929432125,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T00:00:00Z","timestamp":1467676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,7,5]]},"DOI":"10.1145\/2933575.2934527","type":"proceedings-article","created":{"date-parts":[[2016,10,14]],"date-time":"2016-10-14T13:34:47Z","timestamp":1476452087000},"page":"96-105","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["The Diagonal Problem for Higher-Order Recursion Schemes is Decidable"],"prefix":"10.1145","author":[{"given":"Lorenzo","family":"Clemente","sequence":"first","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Parys","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Salvati","sequence":"additional","affiliation":[{"name":"University of Bordeaux, CNRS, INRIA, Bordeaux, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Walukiewicz","sequence":"additional","affiliation":[{"name":"University of Bordeaux, CNRS, INRIA, Bordeaux, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/646254.684109"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321488"},{"key":"e_1_3_2_1_3_1","volume-title":"Proc. of ICALP'16","author":"Asada K.","year":"2016","unstructured":"K. Asada and N. Kobayashi . On word and frontier languages of unsafe higher-order grammars . In Proc. of ICALP'16 , 2016 . To appear. K. Asada and N. Kobayashi. On word and frontier languages of unsafe higher-order grammars. In Proc. of ICALP'16, 2016. To appear."},{"key":"e_1_3_2_1_4_1","series-title":"LNCS","first-page":"473","volume-title":"Proc. of LATA'15","author":"Bachmeier G.","year":"2015","unstructured":"G. Bachmeier , M. Luttenberger , and M. Schlund . Finite automata for the sub- and superword closure of CFLs: Descriptional and computational complexity . In In Proc. of LATA'15 , volume 8977 of LNCS , pages 473 -- 485 , 2015 . G. Bachmeier, M. Luttenberger, and M. Schlund. Finite automata for the sub- and superword closure of CFLs: Descriptional and computational complexity. In In Proc. of LATA'15, volume 8977 of LNCS, pages 473--485, 2015."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000191"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.40"},{"key":"e_1_3_2_1_7_1","series-title":"LIPIcs","first-page":"163","volume-title":"Proc. of FSTTCS'15","author":"Clemente L.","year":"2015","unstructured":"L. Clemente , P. Parys , S. Salvati , and I. Walukiewicz . Ordered tree-pushdown systems . In In Proc. of FSTTCS'15 , volume 45 of LIPIcs , pages 163 -- 177 , 2015 . L. Clemente, P. Parys, S. Salvati, and I. Walukiewicz. Ordered tree-pushdown systems. In In Proc. of FSTTCS'15, volume 45 of LIPIcs, pages 163--177, 2015."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934527"},{"key":"e_1_3_2_1_9_1","unstructured":"H. Comon M. Dauchet R. Gilleron C. L\u00f6ding F. Jacquemard D. Lugiez S. Tison and M. Tommasi. Tree automata techniques and applications. http:\/\/www.grappa.univ-lille3.fr\/tata 2007.  H. Comon M. Dauchet R. Gilleron C. L\u00f6ding F. Jacquemard D. Lugiez S. Tison and M. Tommasi. Tree automata techniques and applications. http:\/\/www.grappa.univ-lille3.fr\/tata 2007."},{"key":"e_1_3_2_1_10_1","volume-title":"Bulletin of EATCS","author":"Courcelle B.","year":"1991","unstructured":"B. Courcelle . On constructing obstruction sets of words . Bulletin of EATCS , 1991 . B. Courcelle. On constructing obstruction sets of words. Bulletin of EATCS, 1991."},{"key":"e_1_3_2_1_11_1","series-title":"LNCS","first-page":"173","volume-title":"FCT'15","author":"Czerwi\u0144ski W.","year":"2015","unstructured":"W. Czerwi\u0144ski , W. Martens , L. van Rooijen , and M. Zeitoun . A note on decidable separability by piecewise testable languages . In FCT'15 , volume 9210 of LNCS , pages 173 -- 185 , 2015 . W. Czerwi\u0144ski, W. Martens, L. van Rooijen, and M. Zeitoun. A note on decidable separability by piecewise testable languages. In FCT'15, volume 9210 of LNCS, pages 173--185, 2015."},{"key":"e_1_3_2_1_12_1","volume-title":"A characterization for decidable separability by piecewise testable languages. Submitted","author":"Czerwi\u0144ski W.","year":"2015","unstructured":"W. Czerwi\u0144ski , W. Martens , L. van Rooijen , M. Zeitoun , and G. Zetzsche . A characterization for decidable separability by piecewise testable languages. Submitted , 2015 . W. Czerwi\u0144ski, W. Martens, L. van Rooijen, M. Zeitoun, and G. Zetzsche. A characterization for decidable separability by piecewise testable languages. Submitted, 2015."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90009-3"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.036"},{"key":"e_1_3_2_1_15_1","series-title":"LNCS","first-page":"466","volume-title":"Proc. of ICALP'10","author":"Habermehl P.","year":"2010","unstructured":"P. Habermehl , R. Meyer , and H. Wimmel . The downward-closure of Petri net languages . In In Proc. of ICALP'10 , volume 6199 of LNCS , pages 466 -- 477 , 2010 . P. Habermehl, R. Meyer, and H. Wimmel. The downward-closure of Petri net languages. In In Proc. of ICALP'10, volume 6199 of LNCS, pages 466--477, 2010."},{"key":"e_1_3_2_1_16_1","series-title":"LIPIcs","first-page":"457","volume-title":"FSTTCS","author":"Hague M.","year":"2011","unstructured":"M. Hague . Parameterised pushdown systems with non-atomic writes . In FSTTCS , volume 13 of LIPIcs , pages 457 -- 468 , 2011 . M. Hague. Parameterised pushdown systems with non-atomic writes. In FSTTCS, volume 13 of LIPIcs, pages 457--468, 2011."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837627"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.34"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"e_1_3_2_1_20_1","first-page":"230","volume-title":"ICDT 2015","volume":"31","author":"Hofman P.","year":"2015","unstructured":"P. Hofman and W. Martens . Separability by short subsequences and subwords . In ICDT 2015 , volume 31 of LIPIcs, pages 230 -- 246 , 2015 . P. Hofman and W. Martens. Separability by short subsequences and subwords. In ICDT 2015, volume 31 of LIPIcs, pages 230--246, 2015."},{"key":"e_1_3_2_1_21_1","volume-title":"Complexity of model checking recursion schemes for fragments of the modal mu-calculus. Logical Methods in Computer Science, 7(4)","author":"Kobayashi N.","year":"2011","unstructured":"N. Kobayashi and C.-H. L. Ong . Complexity of model checking recursion schemes for fragments of the modal mu-calculus. Logical Methods in Computer Science, 7(4) , 2011 . N. Kobayashi and C.-H. L. Ong. Complexity of model checking recursion schemes for fragments of the modal mu-calculus. Logical Methods in Computer Science, 7(4), 2011."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.015"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00646-1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.38"},{"key":"e_1_3_2_1_25_1","series-title":"LIPIcs","first-page":"72","volume-title":"Proc. of CONCUR'15","author":"Torre S. L.","year":"2015","unstructured":"S. L. Torre , A. Muscholl , and I. Walukiewicz . Safety of parametrized asynchronous shared-memory systems is almost always decidable . In In Proc. of CONCUR'15 , volume 42 of LIPIcs , pages 72 -- 84 , 2015 . S. L. Torre, A. Muscholl, and I. Walukiewicz. Safety of parametrized asynchronous shared-memory systems is almost always decidable. In In Proc. of CONCUR'15, volume 42 of LIPIcs, pages 72--84, 2015."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90156-5"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_35"},{"key":"e_1_3_2_1_28_1","series-title":"LIPIcs","first-page":"743","volume-title":"Proc. of STACS'15","author":"Zetzsche G.","year":"2015","unstructured":"G. Zetzsche . Computing downward closures for stacked counter automata. In In Proc. of STACS'15 , volume 30 of LIPIcs , pages 743 -- 756 , 2015 . G. Zetzsche. Computing downward closures for stacked counter automata. In In Proc. of STACS'15, volume 30 of LIPIcs, pages 743--756, 2015."}],"event":{"name":"LICS '16: 31st Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"New York NY USA","acronym":"LICS '16","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"]},"container-title":["Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2933575.2934527","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2933575.2934527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:53Z","timestamp":1750222493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2933575.2934527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,5]]},"references-count":28,"alternative-id":["10.1145\/2933575.2934527","10.1145\/2933575"],"URL":"https:\/\/doi.org\/10.1145\/2933575.2934527","relation":{},"subject":[],"published":{"date-parts":[[2016,7,5]]},"assertion":[{"value":"2016-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}