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 (CRIStAL) - 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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-02532706
Contributor : Inria Links <>
Submitted on : Sunday, April 5, 2020 - 11:11:35 PM
Last modification on : Tuesday, April 7, 2020 - 2:07:02 AM

File

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

Identifiers

  • HAL Id : hal-02532706, version 1

Collections

Citation

Iovka Boneva, Joachim Niehren, Momar Sakho. Nested Regular Expressions can be Compiled to Small Deterministic Nested Word Automata. 15th International Computer Science Symposium in Russia, Jul 2020, Ekaterinburg, Russia. ⟨hal-02532706⟩

Share

Metrics

Record views

33

Files downloads

133