Complete Subhedge Projection for Stepwise Hedge Automata

Antonio Al Serhali (1) , Joachim Niehren (1)

1 LINKS - Linking Dynamic Data

We show 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 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 subhedge projection of SHAs can indeed speed up earliest query answering on XML streams.

Mots clés: Automata; Query answering; Nested words; Streaming

Domaines: Traitement du texte et du document; Théorie et langage formel [cs.FL]

Antonio Al Serhali, Joachim Niehren. Complete Subhedge Projection for Stepwise Hedge Automata. 2024. ⟨hal-04421323v2⟩