A Complexity Bound for Determinisation of Min-Plus Weighted Automata
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917459992248320 |
|---|---|
| author | Almagor, Shaull Arbel, Guy Sheinvald, Sarai |
| author_facet | Almagor, Shaull Arbel, Guy Sheinvald, Sarai |
| contents | The determinisation problem for min-plus (tropical) weighted automata was recently shown to be decidable. However, the proof is purely existential, relying on several non-constructive arguments. Our contribution in this work is twofold: first, we present the first complexity bound for this problem, placing it in the Fast-growing hierarchy. Second, our techniques introduce a versatile framework to analyse runs of weighted automata in a constructive manner. In particular, this simplifies the previous decidability argument and provides a tighter analysis, thus serving as a critical step towards a tight complexity bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_01221 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Complexity Bound for Determinisation of Min-Plus Weighted Automata Almagor, Shaull Arbel, Guy Sheinvald, Sarai Formal Languages and Automata Theory The determinisation problem for min-plus (tropical) weighted automata was recently shown to be decidable. However, the proof is purely existential, relying on several non-constructive arguments. Our contribution in this work is twofold: first, we present the first complexity bound for this problem, placing it in the Fast-growing hierarchy. Second, our techniques introduce a versatile framework to analyse runs of weighted automata in a constructive manner. In particular, this simplifies the previous decidability argument and provides a tighter analysis, thus serving as a critical step towards a tight complexity bound. |
| title | A Complexity Bound for Determinisation of Min-Plus Weighted Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2602.01221 |