Schema-Based Automata Determinization
| Autor: | Niehren, Joachim, Sakho, Momar, Serhali, Antonio Al |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | EPTCS 370, 2022, pp. 49-65 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.4204/EPTCS.370.4 |
| Popis: | We propose an algorithm for schema-based determinization of finite automata on words and of step-wise hedge automata on nested words. The idea is to integrate schema-based cleaning directly into automata determinization. We prove the correctness of our new algorithm and show that it is alway smore efficient than standard determinization followed by schema-based cleaning. Our implementation permits to obtain a small deterministic automaton for an example of an XPath query, where standard determinization yields a huge stepwise hedge automaton for which schema-based cleaning runs out of memory. Comment: In Proceedings GandALF 2022, arXiv:2209.09333 |
| Databáze: | arXiv |
| Externí odkaz: |
|