Decidability Boundaries for the Finite-Image Property of Weighted Finite Automata
A weighted finite automaton has the finite-image property if the image of the weighted language associated with it is finite. We show two undecidability results concerning the finite-image property of weighted finite automata over semirings, respectively strong bimonoids. Firstly, we give a computab...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2023
|
| Sorozat: | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
34 No. 6 |
| Tárgyszavak: | |
| doi: | 10.1142/S0129054123450041 |
| mtmt: | 34153907 |
| Online Access: | http://publicatio.bibl.u-szeged.hu/36185 |
| Tartalmi kivonat: | A weighted finite automaton has the finite-image property if the image of the weighted language associated with it is finite. We show two undecidability results concerning the finite-image property of weighted finite automata over semirings, respectively strong bimonoids. Firstly, we give a computable idempotent commutative past-finite ordered semiring such that it is undecidable, for an arbitrary deterministic weighted finite automaton A over that semiring, whether A has the finite-image property. Secondly, we give a computable commutative past-finite monotonic ordered strong bimonoid such that it is undecidable, for an arbitrary weighted finite automaton A over that strong bimonoid, whether A has the finite-image property. This shows that recent decidability results for suitable weighted finite automata over past-finite monotonic strong bimonoids cannot be extended to natural classes of ordered semirings and ordered strong bimonoids without further assumptions. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 633-653 |
| ISSN: | 0129-0541 |