Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915306352410624 |
|---|---|
| author | Jecker, Ismaël Mazowiecki, Filip Purser, David |
| author_facet | Jecker, Ismaël Mazowiecki, Filip Purser, David |
| contents | We study the determinisation and unambiguisation problems of weighted automata over the rational field: Given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton? Recent results by Bell and Smertnig show that the problem is decidable, however they do not provide any complexity bounds. We show that both problems are in PSPACE for polynomially-ambiguous weighted automata. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_02204 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata Jecker, Ismaël Mazowiecki, Filip Purser, David Formal Languages and Automata Theory Logic in Computer Science We study the determinisation and unambiguisation problems of weighted automata over the rational field: Given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton? Recent results by Bell and Smertnig show that the problem is decidable, however they do not provide any complexity bounds. We show that both problems are in PSPACE for polynomially-ambiguous weighted automata. |
| title | Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2310.02204 |