{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:19:46Z","timestamp":1760145586754,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T00:00:00Z","timestamp":1722556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We demonstrate how to evaluate stepwise hedge automata (Shas) with subhedge projection while completely projecting irrelevant subhedges. Since this requires passing finite state information top-down, we introduce the notion of downward stepwise hedge automata. We use them to define in-memory and streaming evaluators with complete subhedge projection for Shas. We then tune the evaluators so that they can decide on membership at the earliest time point. We apply our algorithms to the problem of answering regular XPath queries on Xml streams. Our experiments show that complete subhedge projection of Shas can indeed speed up earliest query answering on Xml streams so that it becomes competitive with the best existing streaming tools for XPath queries.<\/jats:p>","DOI":"10.3390\/a17080339","type":"journal-article","created":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T16:14:58Z","timestamp":1722615298000},"page":"339","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complete Subhedge Projection for Stepwise Hedge Automata"],"prefix":"10.3390","volume":"17","author":[{"given":"Antonio","family":"Al Serhali","sequence":"first","affiliation":[{"name":"Inria Center, University of Lille, 59000 Lille, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2611-8950","authenticated-orcid":false,"given":"Joachim","family":"Niehren","sequence":"additional","affiliation":[{"name":"Inria Center, University of Lille, 59000 Lille, France"}]}],"member":"1968","published-online":{"date-parts":[[2024,8,2]]},"reference":[{"key":"ref_1","unstructured":"Marian, A., and Sim\u00e9on, J. Projecting XML Documents. Proceedings of the VLDB."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Frisch, A. (2004, January 22\u201327). Regular Tree Language Recognition with Static Information. Proceedings of the Exploring New Frontiers of Theoretical Informatics, IFIP 18th World Computer Congress, TCS 3rd International Conference on Theoretical Computer Science, Toulouse, France.","DOI":"10.1007\/1-4020-8141-3_50"},{"key":"ref_3","first-page":"882","article-title":"XPath Whole Query Optimization","volume":"3","author":"Maneth","year":"2010","journal-title":"VLPB J."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Sebastian, T., and Niehren, J. (2016, January 23\u201328). Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams. Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Harrachov, Czech Republic.","DOI":"10.1007\/978-3-662-49192-8_49"},{"key":"ref_5","unstructured":"Kay, M. (2024, July 22). The Saxon XSLT and XQuery Processor. Available online: https:\/\/www.saxonica.com."},{"key":"ref_6","unstructured":"Gienieczko, M., Murlak, F., and Paperman, C. (May, January 27). Supporting Descendants in SIMD-Accelerated JSONPath. Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, La Jolla, CA, USA."},{"key":"ref_7","unstructured":"Al Serhali, A., and Niehren, J. (2022, January 9\u201311). A Benchmark Collection of Deterministic Automata for XPath Queries. Proceedings of the XML Prague 2022, Prague, Czech Republic."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Niehren, J., and Sakho, M. (2021). Determinization and Minimization of Automata for Nested Words Revisited. Algorithms, 14.","DOI":"10.3390\/a14030068"},{"key":"ref_9","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., and Tommasi, M. (2024, July 22). Tree Automata Techniques and Applications. Available online: http:\/\/tata.gforge.inria.fr."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0022-0000(67)80022-9","article-title":"Characterizing derivation trees of context-free grammars through a generalization of automata theory","volume":"1","author":"Thatcher","year":"1967","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Alur, R. (2007, January 11\u201314). Marrying Words and Trees. Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Beijing, China.","DOI":"10.1145\/1265530.1265564"},{"key":"ref_12","unstructured":"Babai, L. (2004, January 13\u201316). Visibly pushdown languages. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","article-title":"Pebbling Mountain Ranges and its Application of DCFL-Recognition","volume":"Volume 85","year":"1980","journal-title":"Proceedings of the Automata, Languages and Programming, 7th Colloquium"},{"key":"ref_14","first-page":"1","article-title":"Input Driven Languages are Recognized in log n Space","volume":"Volume 102","author":"Karpinski","year":"1985","journal-title":"Topics in the Theory of Computation"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/2636805.2636821","article-title":"Complexity of input-driven pushdown automata","volume":"45","author":"Okhotin","year":"2014","journal-title":"SIGACT News"},{"key":"ref_16","first-page":"49","article-title":"Schema-Based Automata Determinization","volume":"Volume 370","author":"Ganty","year":"2022","journal-title":"Proceedings of the 13th International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2022"},{"key":"ref_17","unstructured":"Lick, A., and Schmitz, S. (2024, July 22). XPath Benchmark. Available online: https:\/\/archive.softwareheritage.org\/browse\/directory\/1ea68cf5bb3f9f3f2fe8c7995f1802ebadf17fb5."},{"key":"ref_18","unstructured":"Candan, K.S., Chen, Y., Snodgrass, R.T., Gravano, L., Fuxman, A., Candan, K.S., Chen, Y., Snodgrass, R.T., Gravano, L., and Fuxman, A. High-performance complex event processing over XML streams. Proceedings of the SIGMOD Conference."},{"key":"ref_19","unstructured":"Grez, A., Riveros, C., and Ugarte, M. (2019, January 26\u201328). A Formal Framework for Complex Event Processing. Proceedings of the 22nd International Conference on Database Theory (ICDT 2019), Lisbon, Portugal."},{"key":"ref_20","first-page":"19:1","article-title":"Streaming Enumeration on Nested Documents","volume":"Volume 220","author":"Olteanu","year":"2022","journal-title":"Proceedings of the 25th International Conference on Database Theory, ICDT 2022"},{"key":"ref_21","first-page":"53","article-title":"Earliest Query Answering for Deterministic Stepwise Hedge Automata","volume":"Volume 14151","author":"Nagy","year":"2023","journal-title":"Proceedings of the Implementation and Application of Automata\u201427th International Conference, CIAA 2023"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-3-642-03409-1_12","article-title":"Earliest Query Answering for Deterministic Nested Word Automata","volume":"Volume 5699","author":"Gauwin","year":"2009","journal-title":"Proceedings of the 17th International Symposium on Fundamentals of Computer Theory"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.tcs.2015.01.017","article-title":"Early nested word automata for XPath query answering on XML streams","volume":"578","author":"Debarbieux","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","first-page":"16","article-title":"Subhedge Projection for Stepwise Hedge Automata","volume":"Volume 14292","author":"Fernau","year":"2023","journal-title":"Proceedings of the Fundamentals of Computation Theory\u201424th International Symposium, FCT 2023"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/978-3-540-49382-2_12","article-title":"Locating Matches of Tree Patterns in Forests","volume":"Volume 1530","author":"Neumann","year":"1998","journal-title":"Proceedings of the Foundations of Software Technology and Theoretical Computer Science"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.ipl.2008.08.002","article-title":"Streaming Tree Automata","volume":"109","author":"Gauwin","year":"2008","journal-title":"Inf. Process. Lett."},{"key":"ref_27","unstructured":"Franceschet, M. (2020, October 25). XPathMark Performance Test. Available online: https:\/\/users.dimi.uniud.it\/~massimo.franceschet\/xpathmark\/PTbench.html."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1145\/767193.767195","article-title":"XDuce: A Statically Typed XML Processing Language","volume":"3","author":"Hosoya","year":"2003","journal-title":"ACM Trans. Internet Technol."},{"key":"ref_29","unstructured":"G\u00e9cseg, F., and Steinby, M. (1984). Tree Automata, Akad\u00e9miai Kiad\u00f3."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","article-title":"Language Identification in the Limit","volume":"10","author":"Gold","year":"1967","journal-title":"Inf. Control."},{"key":"ref_31","first-page":"105","article-title":"Querying Unranked Trees with Stepwise Tree Automata","volume":"Volume 3091","year":"2004","journal-title":"Proceedings of the Rewriting Techniques and Applications, 15th International Conference, RTA 2004"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/S0019-9958(68)90999-6","article-title":"D\u00e9finition et etude des bilangages r\u00e9guliers","volume":"13","author":"Pair","year":"1968","journal-title":"Inf. Control"},{"key":"ref_33","unstructured":"Murata, M. (2024, July 22). Hedge Automata: A Formal Model for XML Schemata. Available online: http:\/\/www.xml.gr.jp\/relax\/hedge_nice.html."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1016\/j.jcss.2006.10.021","article-title":"On the Minimization of XML Schemas and Tree Automata for Unranked Trees","volume":"73","author":"Martens","year":"2007","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_35","unstructured":"Niehren, J. (2024). Stepwise Hedge Automata are exponentially more succinct than Forest Automata, in preparation."},{"key":"ref_36","first-page":"107","article-title":"Forest algebras","volume":"Volume 2","author":"Flum","year":"2008","journal-title":"Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/8\/339\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:29:18Z","timestamp":1760110158000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/8\/339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,2]]},"references-count":36,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2024,8]]}},"alternative-id":["a17080339"],"URL":"https:\/\/doi.org\/10.3390\/a17080339","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,8,2]]}}}