Deconstructing Subset Construction -- Reducing While Determinizing
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908952975900672 |
|---|---|
| author | Nicol, John Frohme, Markus |
| author_facet | Nicol, John Frohme, Markus |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10319 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deconstructing Subset Construction -- Reducing While Determinizing Nicol, John Frohme, Markus Formal Languages and Automata Theory Machine Learning 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. |
| title | Deconstructing Subset Construction -- Reducing While Determinizing |
| topic | Formal Languages and Automata Theory Machine Learning |
| url | https://arxiv.org/abs/2505.10319 |