Proper semirings and proper convex functors

DOI10.1007/978-3-319-89366-2_18MaRDI QIDQ1652997zbMATH OpenOpenAlexFDO

Authors Ana Sokolova, Harald Woracek

Publication date 17 July 2018

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1802.07830

zbMATH Keywords

coalgebraprobabilistic transition systemsproper functorsproper semiringsweighted automata

Mathematics Subject Classification ID

Semirings (16Y60) Special properties of functors (faithful, full, etc.) (18A22) Algebraic theory of languages and automata (68Q70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: Esik and Maletti introduced the notion of a proper semiring and proved that some important (classes of) semirings -- Noetherian semirings, natural numbers -- are proper. Properness matters as the equivalence problem for weighted automata over a semiring which is proper and finitely and effectively presented 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. Moreover, properness of a functor renders soundness and completeness proofs for 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.

Recommendations

• Proper functors and their rational fixed point
• Proper functors and fixed points for finite behaviour
• scientific article; zbMATH DE number 1163637
• Proper/residually-finite idempotent semirings.
• The validity of weighted automata

Cited in

(8)

• On algebras with effectful iteration
• Stronger Lie derivations on \(MA\)-semirings
• Proper functors and their rational fixed point
• Proper functors and fixed points for finite behaviour
• Fun with semirings
• scientific article; zbMATH DE number 5174682 (Why is no real title available?)
• A completeness theorem for probabilistic regular expressions
• A complete inference system for probabilistic infinite trace equivalence

This page was built for publication: Proper semirings and proper convex functors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1652997)