Journal article
Image-binary automata
- Abstract:
- We introduce a certain restriction of weighted automata over the rationals, called image-binary automata. We show that such automata accept the regular languages, can be exponentially more succinct than corresponding NFAs, and allow for polynomial complementation, union, and intersection. This compares favourably with unambiguous automata whose complementation requires a superpolynomial state blowup. We also study an infinite-word version, image-binary B¨uchi automata. We show that such automata are amenable to probabilistic model checking, similarly to unambiguous B¨uchi automata. We provide algorithms to translate k-ambiguous B¨uchi automata to image-binary B¨uchi automata, leading to model-checking algorithms with optimal computational complexity.
- Publication status:
- Accepted
- Peer review status:
- Peer reviewed
Actions
Authors
- Publisher:
- World Scientific Publishing
- Journal:
- International Journal of Foundations of Computer Science More from this journal
- Acceptance date:
- 2024-09-06
- EISSN:
-
1793-6373
- ISSN:
-
0129-0541
- Language:
-
English
- Pubs id:
-
2068170
- Local pid:
-
pubs:2068170
- Deposit date:
-
2024-12-02
Terms of use
- Copyright holder:
- Kiefer and Widdershoven
- Copyright date:
- 2024
- Rights statement:
- © The Author(s) This is an Open Access article published by World Scientific Publishing Company. It is distributed under the terms of the Creative Commons Attribution 4.0 (CC BY) License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record