On the Minimisation of Deterministic and History-Deterministic Generalised (co)Büchi Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913167291973632 |
|---|---|
| author | Casares, Antonio Idir, Olivier Kuperberg, Denis Mascle, Corto Prakash, Keya |
| author_facet | Casares, Antonio Idir, Olivier Kuperberg, Denis Mascle, Corto Prakash, Keya |
| contents | We present a polynomial-time algorithm minimising the number of states of history-deterministic generalised coBüchi automata, building on the work of Abu Radi and Kupferman on coBüchi automata. On the other hand, we establish that the minimisation problem for both deterministic and history-deterministic generalised Büchi automata is NP-complete, as well as the problem of minimising at the same time the number of states and colours of history-deterministic generalised coBüchi automata. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_18090 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Minimisation of Deterministic and History-Deterministic Generalised (co)Büchi Automata Casares, Antonio Idir, Olivier Kuperberg, Denis Mascle, Corto Prakash, Keya Formal Languages and Automata Theory We present a polynomial-time algorithm minimising the number of states of history-deterministic generalised coBüchi automata, building on the work of Abu Radi and Kupferman on coBüchi automata. On the other hand, we establish that the minimisation problem for both deterministic and history-deterministic generalised Büchi automata is NP-complete, as well as the problem of minimising at the same time the number of states and colours of history-deterministic generalised coBüchi automata. |
| title | On the Minimisation of Deterministic and History-Deterministic Generalised (co)Büchi Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2407.18090 |