Title :

Subhedge Projection for Stepwise Hedge Automata

Author(s) :

Al Serhali, Antonio [Auteur]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]

Conference title :

24th International Symposium on Fundamentals of Computation Theory, FCT 2023

City :

Trier

Country :

Allemagne

Start date of the conference :

2023-09-18

English keyword(s) :

Automata
Query answering
Nested words
Streaming

HAL domain(s) :

Informatique [cs]/Traitement du texte et du document
Informatique [cs]/Théorie et langage formel [cs.FL]

English abstract : [en]

We show how to evaluate stepwise hedge automata (Shas) with subhedge projection. This requires passing finite state information top-down, so we introduce the notion of downward stepwise hedge automata. We use them to define ...
Show more >We show how to evaluate stepwise hedge automata (Shas) with subhedge projection. This requires passing finite state information top-down, so we introduce the notion of downward stepwise hedge automata. We use them to define an in-memory and a streaming evaluator with subhedge projection for SHAs. We then tune the streaming evaluator so that it 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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL