{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T11:01:52Z","timestamp":1780743712909,"version":"3.54.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","award":["HR0011-19-C-0073"],"award-info":[{"award-number":["HR0011-19-C-0073"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,6,20]]},"abstract":"<jats:p>Accurate description of program inputs remains a critical challenge in the field of programming languages. Active learning, as a well-established field, achieves exact learning for regular languages. We offer an innovative grammar inference tool, V-Star, based on the active learning of visibly pushdown automata. V-Star deduces nesting structures of program input languages from sample inputs, employing a novel inference mechanism based on nested patterns. This mechanism identifies token boundaries and converts languages such as XML documents into VPLs. We then adapted Angluin\u2019s L-Star, an exact learning algorithm, for VPA learning, which improves the precision of our tool. Our evaluation demonstrates that V-Star effectively and efficiently learns a variety of practical grammars, including S-Expressions, JSON, and XML, and outperforms other state-of-the-art tools.<\/jats:p>","DOI":"10.1145\/3656458","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"2003-2026","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["V-Star: Learning Visibly Pushdown Grammars from Program Inputs"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2493-9111","authenticated-orcid":false,"given":"Xiaodong","family":"Jia","sequence":"first","affiliation":[{"name":"Pennsylvania State University, State College, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6109-6091","authenticated-orcid":false,"given":"Gang","family":"Tan","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, State College, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3605360"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265564"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_89"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007390"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"e_1_3_2_8_1","first-page":"901","article-title":"Fast Deterministic Black-box Context-free Grammar Inference","author":"Arefin M.","year":"2024","unstructured":"M. Arefin, S. Shetiya, Z. Wang, and C. Csallner. 2024. Fast Deterministic Black-box Context-free Grammar Inference. In 2024 IEEE\/ACM 46th International Conference on Software Engineering (ICSE). IEEE Computer Society, Los Alamitos, CA, USA, 901-901. https:\/\/doi.ieeecomputersociety.org\/","journal-title":"In 2024 IEEE\/ACM 46th International Conference on Software Engineering (ICSE). IEEE Computer Society, Los Alamitos, CA, USA"},{"key":"e_1_3_2_9_1","first-page":"113","article-title":"Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A Search","author":"Barbot Benoit","year":"2021","unstructured":"Benoit Barbot, Benedikt Bollig, Alain Finkel, Serge Haddad, Igor Khmelnitsky, Martin Leucker, Daniel Neider, Rajarshi Roy, and Lina Ye. 2021. Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A Search. In Proceedings ofthe Fifteenth International Conference on Grammatical Inference (Proceedings of Machine Learning Research, Vol. 153), Jane Chandlee, Remi Eyraud, Jeff Heinz, AdamJardine, and Menno van Zaanen (Eds.). PMLR, 113-129. https:\/\/proceedings.mlr.press\/v153\/barbot21a.html","journal-title":"In Proceedings ofthe Fifteenth International Conference on Grammatical Inference (Proceedings of Machine Learning Research, Vol. 153), Jane Chandlee, Remi Eyraud, Jeff Heinz, AdamJardine, and Menno van Zaanen (Eds.). PMLR"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062349"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523716"},{"key":"e_1_3_2_12_1","first-page":"279","article-title":"Instrumenting C programs with nested word monitors","author":"Chaudhuri Swarat","year":"2007","unstructured":"Swarat Chaudhuri and Rajeev Alur. 2007. Instrumenting C programs with nested word monitors. In Proceedings ofthe 14th International SPIN Conference on Model Checking Software (Berlin, Germany). Springer-Verlag, Berlin, Heidelberg, 279-283.","journal-title":"In Proceedings ofthe 14th International SPIN Conference on Model Checking Software (Berlin, Germany). Springer-Verlag, Berlin, Heidelberg"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1978.231496"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1233-3"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-011-0135-x"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.87284"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.08.002"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31424-7_41"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1707801.1706353"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.17877\/DE290R-4817"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868044.1868046"},{"key":"e_1_3_2_22_1","unstructured":"Malte Isberner. 2015. Foundations of active automata learning: an algorithmic perspective. https:\/\/api.semanticscholar.org\/CorpusID:45690562"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","unstructured":"Xiaodong Jia. 2024. V-Star Artifact. https:\/\/doi.org\/10.5281\/zenodo.10918754 10.5281\/zenodo.10918754 Zenodo.","DOI":"10.5281\/zenodo.10918754"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485528"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591472"},{"key":"e_1_3_2_26_1","unstructured":"Neil Kulkarni. 2023. Arvada. https:\/\/github.com\/neil-kulkarni\/arvada."},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE51524.2021.9678879"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11817949_14"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242714"},{"key":"e_1_3_2_30_1","first-page":"128","article-title":"On the learnability of infinitary regular sets","author":"Maler Oded","year":"1991","unstructured":"Oded Maler and Amir Pnueli. 1991. On the learnability of infinitary regular sets. In Proceedings of the Fourth Annual Workshop on Computational Learning Theory (Santa Cruz, California, USA) (COLT \u201891). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 128-138.","journal-title":"In Proceedings of the Fourth Annual Workshop on Computational Learning Theory (Santa Cruz, California, USA) (COLT \u201891). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2022.74"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920865"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213866"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SEFM.2006.39"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081180.1081189"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1021"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.047"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01068590"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338958"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656458","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:41:36Z","timestamp":1751661696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656458"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":38,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656458"],"URL":"https:\/\/doi.org\/10.1145\/3656458","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}