{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T23:51:58Z","timestamp":1767138718538,"version":"build-2238731810"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031562211","type":"print"},{"value":"9783031562228","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-56222-8_9","type":"book-chapter","created":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T04:02:30Z","timestamp":1710820950000},"page":"155-171","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Uniform Framework for\u00a0Language Inclusion Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9403-2860","authenticated-orcid":false,"given":"Kyveli","family":"Doveri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3625-6003","authenticated-orcid":false,"given":"Pierre","family":"Ganty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1351-8824","authenticated-orcid":false,"given":"Chana","family":"Weil-Kennedy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,20]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 202\u2013211. ACM (2004). https:\/\/doi.org\/10.1145\/1007352.1007390","DOI":"10.1145\/1007352.1007390"},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1145\/2429069.2429124","volume":"48","author":"F Bonchi","year":"2013","unstructured":"Bonchi, F., Pous, D.: Checking NFA equivalence with bisimulations up to congruence. ACM SIGPLAN Not. 48, 457\u2013468 (2013). https:\/\/doi.org\/10.1145\/2429069.2429124","journal-title":"ACM SIGPLAN Not."},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/3-540-58027-1_27","volume-title":"Mathematical Foundations of Programming Semantics","author":"H Calbrix","year":"1994","unstructured":"Calbrix, H., Nivat, M., Podelski, A.: Ultimately periodic words of rational $$\\omega $$-languages. In: Brookes, S., Main, M., Melton, A., Mislove, M., Schmidt, D. (eds.) MFPS 1993. LNCS, vol. 802, pp. 554\u2013566. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58027-1_27"},{"issue":"6","key":"9_CR4","doi-asserted-by":"publisher","first-page":"1837","DOI":"10.1016\/j.jcss.2011.12.006","volume":"78","author":"S Crespi Reghizzi","year":"2012","unstructured":"Crespi Reghizzi, S., Mandrioli, D.: Operator precedence and the visibly pushdown property. J. Comput. Syst. Sci. 78(6), 1837\u20131867 (2012). https:\/\/doi.org\/10.1016\/j.jcss.2011.12.006","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"9_CR5","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/BF01213206","volume":"31","author":"A de Luca","year":"1994","unstructured":"de Luca, A., Varricchio, S.: Well quasi-orders and regular languages. Acta Informatica 31(6), 539\u2013557 (1994). https:\/\/doi.org\/10.1007\/BF01213206","journal-title":"Acta Informatica"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/11817963_5","volume-title":"Computer Aided Verification","author":"M De Wulf","year":"2006","unstructured":"De Wulf, M., Doyen, L., Henzinger, T.A., Raskin, J.-F.: Antichains: a new algorithm for checking universality of finite automata. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 17\u201330. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11817963_5"},{"key":"9_CR7","doi-asserted-by":"publisher","unstructured":"Doveri, K., Ganty, P., Had\u017ei-\u0110oki\u0107, L.: Antichains algorithms for the inclusion problem between $$\\omega $$-VPL. In: Sankaranarayanan, S., Sharygina, N. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2023. Lecture Notes in Computer Science, vol. 13993. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30823-9_15","DOI":"10.1007\/978-3-031-30823-9_15"},{"key":"9_CR8","doi-asserted-by":"publisher","unstructured":"Doveri, K., Ganty, P., Mazzocchi, N.: FORQ-based language inclusion formal testing. In: Shoham, S., Vizel, Y. (eds.) Computer Aided Verification. CAV 2022. Lecture Notes in Computer Science, vol. 13372. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-13188-2_6","DOI":"10.1007\/978-3-031-13188-2_6"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4230\/LIPIcs.CONCUR.2021.3","volume":"203","author":"K Doveri","year":"2021","unstructured":"Doveri, K., Ganty, P., Parolini, F., Ranzato, F.: Inclusion testing of b\u00fcchi automata based on well-quasiorders. Leibniz Int. Proc. Inform. 203, 1\u201322 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2021.3","journal-title":"Leibniz Int. Proc. Inform."},{"key":"9_CR10","unstructured":"Esparza, J., Rossmanith, P., Schwoon, S.: A uniform framework for problems on context-free grammars. Bull. Eur. Assoc. Theor. Comput. Sci. 72, 169\u2013177 (2000). https:\/\/archive.model.in.tum.de\/um\/bibdb\/esparza\/ufpcfg.pdf"},{"issue":"3","key":"9_CR11","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1145\/321172.321179","volume":"10","author":"RW Floyd","year":"1963","unstructured":"Floyd, R.W.: Syntactic analysis and operator precedence. J. ACM 10(3), 316\u2013333 (1963). https:\/\/doi.org\/10.1145\/321172.321179","journal-title":"J. ACM"},{"key":"9_CR12","unstructured":"Gallier, J.: Languages, automata, theory of computation, preprint on webpage at https:\/\/www.cis.upenn.edu\/~jean\/gbooks\/toc.pdf"},{"issue":"4","key":"9_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3462673","volume":"22","author":"P Ganty","year":"2021","unstructured":"Ganty, P., Ranzato, F., Valero, P.: Complete abstractions for checking language inclusion. ACM Trans. Comput. Logic 22(4), 1\u201340 (2021). https:\/\/doi.org\/10.1145\/3462673","journal-title":"ACM Trans. Comput. Logic"},{"key":"9_CR14","doi-asserted-by":"publisher","unstructured":"Ganty, P., Valero, P.: Regular expression search on compressed text. In: 2019 Data Compression Conference (DCC), pp. 528\u2013537. IEEE (2019). https:\/\/doi.org\/10.1109\/DCC.2019.00061","DOI":"10.1109\/DCC.2019.00061"},{"issue":"4","key":"9_CR15","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1145\/322217.322224","volume":"27","author":"SA Greibach","year":"1980","unstructured":"Greibach, S.A., Friedman, E.P.: Superdeterministic PDAs: a subcase with a decidable inclusion problem. J. ACM 27(4), 675\u2013700 (1980). https:\/\/doi.org\/10.1145\/322217.322224","journal-title":"J. ACM"},{"key":"9_CR16","doi-asserted-by":"publisher","unstructured":"Henzinger, T.A., Kebis, P., Mazzocchi, N., Sara\u00e7, N.E.: Regular methods for operator precedence languages. arXiv:2305.03447 (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2023.129","DOI":"10.4230\/LIPIcs.ICALP.2023.129"},{"key":"9_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/978-3-319-26850-7_22","volume-title":"Networked Systems","author":"L Hol\u00edk","year":"2015","unstructured":"Hol\u00edk, L., Meyer, R.: Antichains for the verification of recursive programs. In: Bouajjani, A., Fauconnier, H. (eds.) NETYS 2015. LNCS, vol. 9466, pp. 322\u2013336. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-26850-7_22"},{"issue":"3","key":"9_CR18","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(82)90073-1","volume":"18","author":"S Istrail","year":"1982","unstructured":"Istrail, S.: Generalization of the ginsburg-rice sch\u00fctzenberger fixed-point theorem for context-sensitive and recursive-enumerable languages. Theor. Comput. Sci. 18(3), 333\u2013341 (1982)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9_CR19","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1006\/jcss.1999.1643","volume":"59","author":"P Jan\u010dar","year":"1999","unstructured":"Jan\u010dar, P., Esparza, J., Moller, F.: Petri nets and regular processes. J. Comput. Syst. Sci. 59(3), 476\u2013503 (1999). https:\/\/doi.org\/10.1006\/jcss.1999.1643","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR20","unstructured":"Kasai, T., Iwata, S.: Some problems in formal language theory known as decidable are proved EXPTIME complete (1992). https:\/\/www.kurims.kyoto-u.ac.jp\/~kyodo\/kokyuroku\/contents\/pdf\/0796-02.pdf"},{"key":"9_CR21","unstructured":"Maquet, N.: New algorithms and data structures for the emptiness problem of alternating automata, Ph. D. thesis, Universit\u00e9 Libre de Bruxelles, Belgium (2011). http:\/\/hdl.handle.net\/2013\/ULB-DIPOT:oai:dipot.ulb.ac.be:2013\/209961"},{"key":"9_CR22","doi-asserted-by":"publisher","unstructured":"Valero Mej\u00eda, P.: On the use of quasiorders in formal language theory, Ph. D. thesis, Universidad Politecnica de Madrid - University Library (2020). https:\/\/doi.org\/10.20868\/upm.thesis.64477","DOI":"10.20868\/upm.thesis.64477"}],"updated-by":[{"DOI":"10.1007\/978-3-031-56222-8_17","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T00:00:00Z","timestamp":1730937600000}}],"container-title":["Lecture Notes in Computer Science","Taming the Infinities of Concurrency"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-56222-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,16]],"date-time":"2024-11-16T17:02:05Z","timestamp":1731776525000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-56222-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031562211","9783031562228"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-56222-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"20 March 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"7 November 2024","order":2,"name":"change_date","label":"Change Date","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"A correction has been published.","order":4,"name":"change_details","label":"Change Details","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}}]}}