通过动态合并等价状态，加速有限自动机的确定化过程。
Deconstructing Subset Construction -- Reducing While Determinizing
- 用等价状态注册表实时合并语言等价的节点，减少搜索空间。
- 在真实与合成数据上显著改善最坏情况下的确定化效率。
- 适用于自动序列分析，适合需要高效自动机构建的研究者。
我们提出一种新的非确定有限自动机（NFA）规范化视角，通过引入中间最小化步骤，在线减少探索空间。核心是等价注册表，用于追踪并合并语言等价的状态，并支持凸性闭包和模拟等优化。该方法具有通用性，可嵌入经典子集构造或Brzozowski方法中。我们在自动序列相关的合成与真实世界实例上评估了该方法，发现其特别提升了最坏情况下的性能。我们发布了开源实现库。
原文摘要 · Abstract (English)
We present a novel perspective on the NFA canonization problem, which introduces intermediate minimization steps to reduce the exploration space on-the-fly. Central to our approach are equivalence registries which track and unify language-equivalent states, and allow for additional optimizations such as convexity closures and simulation. Due to the generality of our approach, these concepts can be embedded in classic subset construction or Brzozowski's approach. We evaluate our approach on a set of synthetic and real-world examples from automatic sequences and observe that we are able to improve especially worst-case scenarios. We provide an open-source library implementing our approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。