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. Lecture Notes in Computer Science, 12038. (pp. 17-32). Cham: Springer Verlag. ISBN 9783030406073

Abstract

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 https://doi.org/10.1007/978-3-030-40608-0_2.
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 Mathematics, Computer Science & Engineering > Computer Science
Date Deposited: 15 May 2020 08:47
URI: https://openaccess.city.ac.uk/id/eprint/24184
[img]
Preview
Text - Accepted Version
Download (341kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login