{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T21:20:17Z","timestamp":1790284817023,"version":"4.1.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031308222","type":"print"},{"value":"9783031308239","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,22]],"date-time":"2023-04-22T00:00:00Z","timestamp":1682121600000},"content-version":"vor","delay-in-days":111,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We present a new streaming algorithm to validate JSON documents against a set of constraints given as a JSON schema. Among the possible values a JSON document can hold, objects are unordered collections of key-value pairs while arrays are ordered collections of values. We prove that there always exists a visibly pushdown automaton (VPA) that accepts the same set of JSON documents as a JSON schema. Leveraging this result, our approach relies on learning a VPA for the provided schema. As the learned VPA assumes a fixed order on the key-value pairs of the objects, we abstract its transitions in a special kind of graph, and propose an efficient streaming algorithm using the VPA and its graph to decide whether a JSON document is valid for the schema. We evaluate the implementation of our algorithm on a number of random JSON documents, and compare it to the classical validation algorithm.<\/jats:p>","DOI":"10.1007\/978-3-031-30823-9_14","type":"book-chapter","created":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T16:19:12Z","timestamp":1682093952000},"page":"271-289","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Validating Streaming JSON Documents with Learned VPAs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9680-9140","authenticated-orcid":false,"given":"V\u00e9ronique","family":"Bruy\u00e8re","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1200-4952","authenticated-orcid":false,"given":"Guillermo A.","family":"P\u00e9rez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5795-3265","authenticated-orcid":false,"given":"Ga\u00ebtan","family":"Staquet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,4,22]]},"reference":[{"key":"14_CR1","doi-asserted-by":"publisher","unstructured":"Richard A.\u00a0DeMillo, Richard J.\u00a0Lipton, Frederick G.\u00a0Sayward: Hints on Test Data Selection: Help for the Practicing Programmer. Computer 11(4), 34\u201341 (1978). https:\/\/doi.org\/10.1109\/C-M.1978.218136","DOI":"10.1109\/C-M.1978.218136"},{"key":"14_CR2","doi-asserted-by":"publisher","unstructured":"Rajeev Alur, Viraj Kumar, Madhusudan, P., Mahesh Viswanathan: Congruences for Visibly Pushdown Languages. In: Lu\u00eds Caires, Giuseppe F.\u00a0Italiano, Lu\u00eds Monteiro, Catuscia Palamidessi, Moti Yung (eds.) Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings. Lecture Notes in Computer Science, vol.\u00a03580, pp. 1102\u20131114. Springer (2005). https:\/\/doi.org\/10.1007\/11523468_89","DOI":"10.1007\/11523468_89"},{"key":"14_CR3","doi-asserted-by":"publisher","unstructured":"Rajeev Alur, Madhusudan, P.: Visibly pushdown languages. In: L\u00e1szl\u00f3 Babai (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. pp. 202\u2013211. ACM (2004). https:\/\/doi.org\/10.1145\/1007352.1007390","DOI":"10.1145\/1007352.1007390"},{"key":"14_CR4","doi-asserted-by":"publisher","unstructured":"Dana Angluin: Learning Regular Sets from Queries and Counterexamples. Inf. Comput. 75(2), 87\u2013106 (1987). https:\/\/doi.org\/10.1016\/0890-5401(87)90052-6","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"14_CR5","doi-asserted-by":"publisher","unstructured":"Iovka Boneva, Radu Ciucanu, Slawek Staworko: Schemas for Unordered XML on a DIME. Theory Comput. Syst. 57(2), 337\u2013376 (2015). https:\/\/doi.org\/10.1007\/s00224-014-9593-1","DOI":"10.1007\/s00224-014-9593-1"},{"key":"14_CR6","doi-asserted-by":"publisher","unstructured":"Tim Bray: The JavaScript Object Notation (JSON) Data Interchange Format. RFC 8259, 1\u201316 (2017). https:\/\/doi.org\/10.17487\/RFC8259","DOI":"10.17487\/RFC8259"},{"key":"14_CR7","doi-asserted-by":"publisher","unstructured":"V\u00e9ronique Bruy\u00e8re, Guillermo A.\u00a0P\u00e9rez, Ga\u00ebtan Staquet: Learning Realtime One-Counter Automata. In: Dana Fisman, Grigore Rosu (eds.) International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science, vol. 13243, pp. 244\u2013262. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-030-99524-9_13","DOI":"10.1007\/978-3-030-99524-9_13"},{"key":"14_CR8","unstructured":"John E.\u00a0Hopcroft, Jeffrey D.\u00a0Ullman: Introduction to Automata Theory, Languages and Computation, Second Edition. Addison-Wesley (2000)"},{"key":"14_CR9","unstructured":"Malte Isberner: Foundations of active automata learning: an algorithmic perspective. Ph.D. thesis, Technical University Dortmund, Germany (2015), http:\/\/hdl.handle.net\/2003\/34282"},{"key":"14_CR10","doi-asserted-by":"publisher","unstructured":"Malte Isberner, Falk Howar, Bernhard Steffen: The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning. In: Borzoo Bonakdarpour, Scott A.\u00a0Smolka (eds.) Runtime Verification - 5th International Conference, RV 2014, Toronto, ON, Canada, September 22-25, 2014. Proceedings. Lecture Notes in Computer Science, vol.\u00a08734, pp. 307\u2013322. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-11164-3_26","DOI":"10.1007\/978-3-319-11164-3_26"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Isberner, M., Howar, F., Steffen, B.: The Open-Source LearnLib. In: Kroening, D., P\u0103s\u0103reanu, C.S. (eds.) Computer Aided Verification. pp. 487\u2013495. Springer International Publishing, Cham (2015)","DOI":"10.1007\/978-3-319-21690-4_32"},{"key":"14_CR12","doi-asserted-by":"publisher","unstructured":"Yue Jia, Mark Harman: An Analysis and Survey of the Development of Mutation Testing. IEEE Trans. Software Eng. 37(5), 649\u2013678 (2011). https:\/\/doi.org\/10.1109\/TSE.2010.62","DOI":"10.1109\/TSE.2010.62"},{"key":"14_CR13","unstructured":"JSON Schema: JSON Schema website. Online (2015), https:\/\/json-schema.org"},{"key":"14_CR14","unstructured":"JSON.org: JSON.org website. Online (2013), https:\/\/www.json.org"},{"key":"14_CR15","doi-asserted-by":"publisher","unstructured":"Viraj Kumar, Madhusudan, P., Mahesh Viswanathan: Visibly pushdown automata for streaming XML. In: Carey L.\u00a0Williamson, Mary\u00a0Ellen Zurko, Peter F.\u00a0Patel-Schneider, Prashant J.\u00a0Shenoy (eds.) Proceedings of the 16th International Conference on World Wide Web, WWW 2007, Banff, Alberta, Canada, May 8-12, 2007. pp. 1053\u20131062. ACM (2007). https:\/\/doi.org\/10.1145\/1242572.1242714","DOI":"10.1145\/1242572.1242714"},{"key":"14_CR16","doi-asserted-by":"publisher","unstructured":"Wim Martens, Frank Neven, Matthias Niewerth, Thomas Schwentick: BonXai: Combining the Simplicity of DTD with the Expressiveness of XML Schema. ACM Trans. Database Syst. 42(3), 15:1\u201315:42 (2017). https:\/\/doi.org\/10.1145\/3105960","DOI":"10.1145\/3105960"},{"key":"14_CR17","doi-asserted-by":"publisher","unstructured":"Maik Merten, Bernhard Steffen, Falk Howar, Tiziana Margaria: Next Generation LearnLib. In: Parosh\u00a0Aziz Abdulla, Rustan M.\u00a0Leino, K. (eds.) Tools and Algorithms for the Construction and Analysis of Systems - 17th International Conference, TACAS 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Saarbr\u00fccken, Germany, March 26-April 3, 2011. Proceedings. Lecture Notes in Computer Science, vol.\u00a06605, pp. 220\u2013223. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-19835-9_18","DOI":"10.1007\/978-3-642-19835-9_18"},{"key":"14_CR18","doi-asserted-by":"publisher","unstructured":"Matthias Niewerth, Thomas Schwentick: Reasoning About XML Constraints Based on XML-to-Relational Mappings. Theory Comput. Syst. 62(8), 1826\u20131879 (2018). https:\/\/doi.org\/10.1007\/s00224-018-9846-5","DOI":"10.1007\/s00224-018-9846-5"},{"key":"14_CR19","doi-asserted-by":"publisher","unstructured":"Felipe Pezoa, Juan L.\u00a0Reutter, Fernando Su\u00e1rez, Mart\u00edn Ugarte, Domagoj Vrgoc: Foundations of JSON Schema. In: Jacqueline Bourdeau, Jim Hendler, Roger Nkambou, Ian Horrocks, Ben Y.\u00a0Zhao (eds.) Proceedings of the 25th International Conference on World Wide Web, WWW 2016, Montreal, Canada, April 11 - 15, 2016. pp. 263\u2013273. ACM (2016). https:\/\/doi.org\/10.1145\/2872427.2883029","DOI":"10.1145\/2872427.2883029"},{"key":"14_CR20","unstructured":"Schema for Azure Functions Proxies. Online, https:\/\/json.schemastore.org\/proxies.json"},{"key":"14_CR21","unstructured":"Schema for codecov configuration. Online, https:\/\/json.schemastore.org\/codecov.json"},{"key":"14_CR22","unstructured":"Schema for VIM plugins. Online, https:\/\/json.schemastore.org\/vim-addon-info.json"},{"key":"14_CR23","unstructured":"Schema for Visual Studio Code snippets. Online, https:\/\/raw.githubusercontent.com\/Yash-Singh1\/vscode-snippets-json-schema\/main\/schema.json"},{"key":"14_CR24","doi-asserted-by":"publisher","unstructured":"Thomas Schwentick: Foundations of XML Based on Logic and Automata: A Snapshot. In: Thomas Lukasiewicz, Attila Sali (eds.) Foundations of Information and Knowledge Systems - 7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings. Lecture Notes in Computer Science, vol.\u00a07153, pp. 23\u201333. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-28472-4_2","DOI":"10.1007\/978-3-642-28472-4_2"},{"key":"14_CR25","doi-asserted-by":"publisher","unstructured":"Luc Segoufin, Victor Vianu: Validating Streaming XML Documents. In: Lucian Popa, Serge Abiteboul, Phokion G.\u00a0Kolaitis (eds.) Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, Madison, Wisconsin, USA. pp. 53\u201364. ACM (2002). https:\/\/doi.org\/10.1145\/543613.543622","DOI":"10.1145\/543613.543622"},{"key":"14_CR26","unstructured":"Helmut Seidl, Thomas Schwentick, Anca Muscholl: Counting in trees. In: J\u00f6rg Flum, Erich Gr\u00e4del, Thomas Wilke (eds.) Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]. Texts in Logic and Games, vol.\u00a02, pp. 575\u2013612. Amsterdam University Press (2008)"},{"key":"14_CR27","unstructured":"Staquet, G.: AutomataLib, https:\/\/github.com\/DocSkellington\/automatalib"},{"key":"14_CR28","unstructured":"Staquet, G.: JSON Schema Tools, https:\/\/github.com\/DocSkellington\/JSONSchemaTools"},{"key":"14_CR29","unstructured":"Staquet, G.: LearnLib, https:\/\/github.com\/DocSkellington\/learnlib"},{"key":"14_CR30","unstructured":"Staquet, G.: Validating JSON Documents With Learned VPA, https:\/\/github.com\/DocSkellington\/ValidatingJSONDocumentsWithLearnedVPA"},{"key":"14_CR31","doi-asserted-by":"publisher","unstructured":"Staquet, G.: Validating Streaming JSON Documents with Learned VPAs (Nov 2022). https:\/\/doi.org\/10.5281\/zenodo.7309689","DOI":"10.5281\/zenodo.7309689"},{"key":"14_CR32","doi-asserted-by":"publisher","unstructured":"Nguyen\u00a0Van Tang: A Tighter Bound for the Determinization of Visibly Pushdown Automata. In: Axel Legay (ed.) Proceedings International Workshop on Verification of Infinite-State Systems, INFINITY 2009, Bologna, Italy, 31th August 2009. EPTCS, vol.\u00a010, pp. 62\u201376 (2009). https:\/\/doi.org\/10.4204\/EPTCS.10.5","DOI":"10.4204\/EPTCS.10.5"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30823-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:06:52Z","timestamp":1781024812000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30823-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031308222","9783031308239"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30823-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"22 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2023\/tacas","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}