We consider the problem of determinizing and minimizing automata for nested words in practice. For this we compile the nested regular expressions ($\mathit{NREs}$) from the usual XPath benchmark to nested word automata ($\mathit{NWAs}$). The determinization of these $\mathit{NWAs}$, however, fails to produce reasonably small automata. In the best case, huge deterministic $\mathit{NWAs}$ are produced after few hours, even for relatively small $\mathit{NREs}$ of the benchmark. We propose a different approach to the determinization of automata for nested words. For this, we introduce stepwise hedge automata ($\mathit{SHA}$s) that generalize naturally on both (stepwise) tree automata and on finite word automata. We then show how to determinize $\mathit{SHA}$s, yielding reasonably small deterministic automata for the $\mathit{NREs}$ from the XPath benchmark. The size of deterministic $\mathit{SHA}$s automata can be reduced further by a novel minimization algorithm for a subclass of $\mathit{SHA}$s. In order to understand why the new approach to determinization and minimization works so nicely, we investigate the relationship between $\mathit{NWAs}$ and $\mathit{SHA}$s further. Clearly, deterministic $\mathit{SHA}$s can be compiled to deterministic $\mathit{NWAs}$ in linear time, and conversely $\mathit{NWAs}$ can be compiled to nondeterministic $\mathit{SHA}$s in polynomial time. Therefore, we can use $\mathit{SHA}$s as intermediates for determinizing $\mathit{NWAs}$, while avoiding the huge size increase with the usual determinization algorithm for $\mathit{NWAs}$. Notably, the $\mathit{NWAs}$ obtained from the $\mathit{SHA}$s perform bottom-up and left-to-right computations only, but no top-down computations. This $\mathit{NWA}$ behavior can be distinguished syntactically by the (weak) single-entry property, suggesting a close relationship between $\mathit{SHA}$s and single-entry $\mathit{NWAs}$. In particular, it turns out that the usual determinization algorithm for $\mathit{NWAs}$ behaves well for single-entry $\mathit{NWAs}$, while it quickly explodes without the single-entry property. Furthermore, it is known that the class of deterministic multi-module single-entry $\mathit{NWAs}$ enjoys unique minimization. The subclass of deterministic $\mathit{SHA}$s to which our novel minimization algorithm applies is different though, in that we do not impose multiple modules. As further optimizations for reducing the sizes of the constructed $\mathit{SHA}$s, we propose schema-based cleaning and symbolic representations based on apply-else rules that can be maintained by determinization. We implemented the optimizations and report the experimental results for the automata constructed for the XPathMark benchmark.

Requêtes logiques sur les hyperflux: Les hyperflux sont des collections de flux de données avec références. Sachant qu’ils permettent la réception de données en parallèle plutôt que de manière purement séquentielle, l’on peut espérer que des données structurées transmises par leur biais puissent être traitées avec une latence moindre qu’avec un flux. Nous proposons ainsi de développer des algorithmes d’évaluation de requêtes logiques sur les hyperflux de données. Pour ce faire, nous nous intéressons à la faisabilité théorique et pratique d’un algorithme de décision du problème de certitude d’une réponse (CQA) sur les hyperflux. Nous étudions la complexité du CQA sur les hyperflux. Nous montrons d’abord que le CQA est intimement lié à des problèmes de correspondance de motifs dans les langages réguliers, et donc aux problèmes d’habitation des transitions d’automates de mots et d’arbres. Cela nous permet d’établir une classification de la complexité du CQA pour des classes d’automates et d’hyperflux variées. Nous obtenons des résultats en temps polynomial pour les hyperflux linéaires sans compression et les requêtes dé-finies par des automates déterministes pour forêts. Pour le cas général, la complexité atteint ExpTime. Nous développons ensuite un algo-rithme efficace pour l’approximation du CQA sur les hyperflux. Cet algorithme a une grande couverture, du fait qu’il s’applique à des hy-perflux et des classes d’automates arbitraires, et s’exécute en temps polynomial. Cependant, il ne détecte pas toujours les réponses certaines avec une latence minimale. La troisième contribution est un algorithme pour le CQA sur les flux, qui s’exécute en temps polynomial dans le cas de requêtes booléennes. Cet algorithme est aussi efficace en pratique pour le cas monadique, à l’inverse de toutes les précédentes propo-sitions. Nous le montrons expérimentalement en appliquant l’algorithme aux requêtes navigationnelles XPath habituellement prises pour référence, avec lesquelles toutes les approches précédentes de CQA sans approximation ont échoué. L’utilisation d’automates spéciaux pour les forêts a permis la mise en place dudit algorithme.