Unambiguisability and Register Minimisation of Min-Plus Models
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_ | 1866914515953647616 |
|---|---|
| author | Almagor, Shaull Arbel, Guy Sheinvald, Sarai |
| author_facet | Almagor, Shaull Arbel, Guy Sheinvald, Sarai |
| contents | We study the unambiguisability problem for min-plus (tropical) weighted automata (WFAs), and the counter-minimisation problem for tropical Cost Register Automata (CRAs), which are expressively-equivalent to WFAs. Both problems ask whether the "amount of nondeterminism" in the model can be reduced. We show that WFA unambiguisability is decidable, thus resolving this long-standing open problem. Our proof is via reduction to WFA determinisability, which was recently shown to be decidable. On the negative side, we show that CRA counter minimisation is undecidable, even for a fixed number of registers (specifically, already for 7 registers). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_09484 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Unambiguisability and Register Minimisation of Min-Plus Models Almagor, Shaull Arbel, Guy Sheinvald, Sarai Formal Languages and Automata Theory We study the unambiguisability problem for min-plus (tropical) weighted automata (WFAs), and the counter-minimisation problem for tropical Cost Register Automata (CRAs), which are expressively-equivalent to WFAs. Both problems ask whether the "amount of nondeterminism" in the model can be reduced. We show that WFA unambiguisability is decidable, thus resolving this long-standing open problem. Our proof is via reduction to WFA determinisability, which was recently shown to be decidable. On the negative side, we show that CRA counter minimisation is undecidable, even for a fixed number of registers (specifically, already for 7 registers). |
| title | Unambiguisability and Register Minimisation of Min-Plus Models |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2512.09484 |