The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916844089114624 |
|---|---|
| author | Daviaud, Laure Purser, David Tcheng, Marie |
| author_facet | Daviaud, Laure Purser, David Tcheng, Marie |
| contents | We show that the big-O problem for max-plus automata is decidable and PSPACE-complete. The big-O (or affine domination) problem asks whether, given two max-plus automata computing functions f and g, there exists a constant c such that f < cg+ c. This is a relaxation of the containment problem asking whether f < g, which is undecidable. Our decidability result uses Simon's forest factorisation theorem, and relies on detecting specific elements, that we call witnesses, in a finite semigroup closed under two special operations: stabilisation and flattening. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_05229 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete) Daviaud, Laure Purser, David Tcheng, Marie Formal Languages and Automata Theory Logic in Computer Science We show that the big-O problem for max-plus automata is decidable and PSPACE-complete. The big-O (or affine domination) problem asks whether, given two max-plus automata computing functions f and g, there exists a constant c such that f < cg+ c. This is a relaxation of the containment problem asking whether f < g, which is undecidable. Our decidability result uses Simon's forest factorisation theorem, and relies on detecting specific elements, that we call witnesses, in a finite semigroup closed under two special operations: stabilisation and flattening. |
| title | The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete) |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2304.05229 |