[Back]

S. Sokolova, H. Woracek:
"Proper semirings and proper convex functors";
in: "ASC Report 22/2017", issued by: Institute for Analysis and Scientific Computing; Vienna University of Technology, Wien, 2017, ISBN: 978-3-902627-10-0, 1 - 32.

Esik and Maletti introduced the notion of a proper semir-ing and proved that some important (classes of) semirings - Noethe-rian semirings, natural numbers - are proper. Properness matters as the equivalence problem for weighted automata over proper and finitely and effectively presented semirings is decidable. Milius generalised the notion of properness from a semiring to a functor. As a consequence, a semiring is proper if and only if its associated "cubic functor" is proper. More-over, properness of a functor renders soundness and completeness proofs of axiomatizations of equivalent behaviour.
In this paper we provide a method for proving properness of functors, and instantiate it to cover both the known cases and several novel ones:(1) properness of the semirings of positive rationals and positive reals, via properness of the corresponding cubic functors; and (2) properness of two functors on (positive) convex algebras. The latter functors are important for axiomatizing trace equivalence of probabilistic transition systems. Our proofs rely on results that stretch all the way back to Hilbert and Minkowski.

proper semirings, proper functors, coalgebra, weighted au-tomata, probabilistic transition systems

http://www.asc.tuwien.ac.at/preprint/2017/asc22x2017.pdf