Papers for

automata system engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Limits on building final coalgebras over modules from rings

Final coalgebras over R-modules

Abstract: Final coalgebras and the coinduction principle for coalgebras over $R$-modules, where $R$ is a commutative ring, are essential in determining the denotational behaviour of various types of linear weighted automata. The goal of this paper is to provide lower and upper bounds on the ordinals that are needed to construct final coalgebras over $R$-modules as the limit of a transfinite sequence of functor iterations. We give an example of a binary intersection preserving finitary functor on the category of abelian groups, which is the category of modules over integers, that fails to converge in $ω\cdot 2$ steps, thus settling an open problem of Adámek, Milius, and Moss. Then we relate this to the failure of the Artinian property of the integers and show that all finitary functors on $R$-modules for a Noetherian ring $R$ with Krull dimension $n$, which preserve countable directed intersections and a generalised notion of monomorphism, converge in $ω\cdot (n + 2)$ steps. We also establish how the connection between Aczel-Mendler bisimulation and behavioural equivalence is mediated by the functor $\operatorname{Ext}^1$. These results show that homological algebra tools can play an important role in coalgebra.

Mon 2 NovLogic in Computer Science
The gist
Figuring out how certain mathematical objects called final coalgebras form over modules defined by rings is important for understanding some types of automated systems. The authors show that for modules over the integers, forming these objects may take longer than previously expected, solving a known problem. They also connect this to deeper properties of the ring involved, providing general bounds on how long the process can take for more complex rings. Their work uses advanced tools from homological algebra to better understand when and how these coalgebras come together.
Open → 2611.03174v1