Nested Regular Expressions can be Compiled to Small Deterministic Nested Word Automata
| Autor: | Iovka Boneva, Momar Sakho, Joachim Niehren |
|---|---|
| Přispěvatelé: | Linking Dynamic Data (LINKS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data [LINKS], Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 (CRIStAL), Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Nested word Computer science [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] 0102 computer and information sciences 02 engineering and technology Hedge (linguistics) 01 natural sciences Automaton Nondeterministic algorithm 010201 computation theory & mathematics Path (graph theory) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Regular expression MESH: Nested Words Streams Automata XML Computer Science::Databases Computer Science::Formal Languages and Automata Theory |
| Zdroj: | CSR 2020-15th International Computer Science Symposium in Russia CSR 2020-15th International Computer Science Symposium in Russia, Jun 2020, Ekaterinburg, Russia Computer Science – Theory and Applications ISBN: 9783030500252 CSR 15th International Computer Science Symposium in Russia 15th International Computer Science Symposium in Russia, Jul 2020, Ekaterinburg, Russia |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|