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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationLATA 2020: Language and Automata Theory and Applications
EditorsAlberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron
PublisherSpringer
Pages17-32
Number of pages16
ISBN (Print)9783030406073
DOIs
Publication statusPublished - 2020
Externally publishedYes
Event14th International Conference on Language and Automata Theory and Applications, LATA 2020 - Milan, Italy
Duration: 4 Mar 20206 Mar 2020

Publication series

NameLecture Notes in Computer Science
Volume12038
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Language and Automata Theory and Applications, LATA 2020
Country/TerritoryItaly
CityMilan
Period4/03/206/03/20

Keywords

  • Containment problem
  • Decidability
  • Equivalence problem
  • Max-plus automata
  • Probabilistic automata
  • Weighted automata

Cite this