Purandar Bhaduri - Coalgebras for Bisimulation of Weighted Automata over Semirings

lmcs:8441 - Logical Methods in Computer Science, January 16, 2023, Volume 19, Issue 1 - https://doi.org/10.46298/lmcs-19(1:4)2023
Coalgebras for Bisimulation of Weighted Automata over Semirings

Authors: Purandar Bhaduri

    Weighted automata are a generalization of nondeterministic automata that associate a weight drawn from a semiring $K$ with every transition and every state. Their behaviours can be formalized either as weighted language equivalence or weighted bisimulation. In this paper we explore the properties of weighted automata in the framework of coalgebras over (i) the category $\mathsf{SMod}$ of semimodules over a semiring $K$ and $K$-linear maps, and (ii) the category $\mathsf{Set}$ of sets and maps. We show that the behavioural equivalences defined by the corresponding final coalgebras in these two cases characterize weighted language equivalence and weighted bisimulation, respectively. These results extend earlier work by Bonchi et al. using the category $\mathsf{Vect}$ of vector spaces and linear maps as the underlying model for weighted automata with weights drawn from a field $K$. The key step in our work is generalizing the notions of linear relation and linear bisimulation of Boreale from vector spaces to semimodules using the concept of the kernel of a $K$-linear map in the sense of universal algebra. We also provide an abstract procedure for forward partition refinement for computing weighted language equivalence. Since for weighted automata defined over semirings the problem is undecidable in general, it is guaranteed to halt only in special cases. We provide sufficient conditions for the termination of our procedure. Although the results are similar to those of Bonchi et al., many of our proofs are new, especially those about the coalgebra in $\mathsf{SMod}$ characterizing weighted language equivalence.

    Volume: Volume 19, Issue 1
    Published on: January 16, 2023
    Accepted on: December 19, 2022
    Submitted on: September 3, 2021
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science,F.1.1,F.4.3


    Consultation statistics

    This page has been seen 427 times.
    This article's PDF has been downloaded 181 times.