Joachim Niehren (Inria, Université de Lille, France) |
Momar Sakho (Inria, Université de Lille, France) |
Antonio Al Serhali (Inria, Université de Lille, France) |
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. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.370.4 | bibtex | |
Comments and questions to: eptcs@eptcs.org |
For website issues: webmaster@eptcs.org |