Abstract : We study the problem of whether regular expressions for nested words can be compiled to small deterministic nested word au-tomata (NWAs). In theory, we obtain a positive answer for small deter-ministic regular expressions for nested words. In practice of navigational path queries, nondeterministic NWAs are obtained for which NWA de-terminization explodes. We show that practical good solutions can be obtained by using stepwise hedge automata as intermediates.
Iovka Boneva, Joachim Niehren, Momar Sakho. Nested Regular Expressions can be Compiled to Small Deterministic Nested Word Automata. CSR 2020 - 15th International Computer Science Symposium in Russia, Jun 2020, Ekaterinburg, Russia. ⟨hal-02532706v2⟩