City Research Online

Containment and equivalence of weighted automata: Probabilistic and max-plus cases

Daviaud, L. ORCID: 0000-0002-9220-7118 (2020). Containment and equivalence of weighted automata: Probabilistic and max-plus cases. In: Language and Automata Theory and Applications. LATA 2020. doi: 10.1007/978-3-030-40608-0_2


This paper surveys some results regarding decision problems for probabilistic and max-plus automata, such as containment and equivalence. Probabilistic and max-plus automata are part of the general family of weighted automata, whose semantics are maps from words to real values. Given two weighted automata, the equivalence problem asks whether their semantics are the same, and the containment problem whether one is point-wise smaller than the other one. These problems have been studied intensively and this paper will review some techniques used to show (un)decidability and state a list of open questions that still remain.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: The final authenticated publication is available online at
Publisher Keywords: Weighted automata, Probabilistic automata, Max-plus automata, Equivalence problem, Containment problem, Decidability
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science
[thumbnail of LataPaper.pdf]
Text - Accepted Version
Download (341kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login