Skip to Main content Skip to Navigation
Conference papers

Nested Regular Expressions can be Compiled to Small Deterministic Nested Word Automata

Iovka Boneva 1 Joachim Niehren 1 Momar Sakho 1
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-02532706
Contributor : Inria Links <>
Submitted on : Sunday, July 19, 2020 - 3:12:19 PM
Last modification on : Friday, December 11, 2020 - 6:44:06 PM

File

0-short.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02532706, version 2

Collections

Citation

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⟩

Share

Metrics

Record views

59

Files downloads

261