Containment and Equivalence of Weighted Automata:Probabilistic and Max-Plus Cases

Daviaud, Laure (2020) Containment and Equivalence of Weighted Automata:Probabilistic and Max-Plus Cases. In: LATA 2020: Language and Automata Theory and Applications. Lecture Notes in Computer Science . Springer, ITA, pp. 17-32. ISBN 9783030406073

Preview

PDF (ContainmentEquivalenceWeighted) - Accepted Version Download (341kB) | Preview

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.

Item Type:	Book Section
Additional Information:	Publisher Copyright: © Springer Nature Switzerland AG 2020.
Uncontrolled Keywords:	containment problem,decidability,equivalence problem,max-plus automata,probabilistic automata,weighted automata,theoretical computer science,computer science(all) ,/dk/atira/pure/subjectarea/asjc/2600/2614
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	14 Jun 2023 14:26
Last Modified:	14 Jun 2023 14:26
URI:	https://ueaeprints.uea.ac.uk/id/eprint/92391
DOI:	10.1007/978-3-030-40608-0_2

Downloads

Actions (login required)

View Item