Nested Regular Expressions Can Be Compiled to Small Deterministic Nested Word Automata
Iovka Boneva, Joachim Niehren, Momar Sakho · Lecture notes in computer science · 2020
We study the problem of whether regular expressions for nested words can be compiled to small deterministic nested word automata ( NWA s). In theory, we obtain a positive answer for small deterministic regular expressions for nested words. In practice of navigational path queries, nondeterministic NWA s are obtained for which NWA determinization explodes. We show that practical good solutions can be obtained by using stepwise hedge automata as intermediates.