City Research Online

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 Science & Technology > Computer Science

Export

Downloads