论文标题
基于模式的自动机确定
Schema-Based Automata Determinization
论文作者
论文摘要
我们提出了一种基于架构的算法确定嵌套单词上的有限自动机和逐步的树篱自动机。这个想法是将基于模式的清洁直接集成到自动机确定中。我们证明了我们的新算法的正确性，并表明它与标准确定性更有效，然后是基于模式的清洁。我们的实现允许为XPath查询的示例获得一个小的确定性自动机，其中标准确定性产生了一个巨大的逐步篱笆自动机，基于模式的清洁效果超出内存。
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.
