2024/09/13 by Manfred Droste, Droste, Manfred, Heiko Vogler +1
Computer Science · #03D15 (Secondary) #68Q45 (Primary) 03D05 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic, programming, and type systems #Petri Nets in System Modeling
paper · pdf · doi:10.48550/arxiv.2409.08727
openalex publication_date 2024/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider weighted automata over words and over trees where the weight algebras are strong bimonoids, i.e., semirings which may lack distributivity. It is well known that, for each such weighted automaton, its run semantics and its initial algebra semantics can be different, due to the presence of nondeterminism and the absence of distributivity. Here we investigate the question under which conditions on the strong bimonoid the support of the run semantics equals the support of the initial algebra semantics. We prove a characterization of this equality in terms of strongly zero-sum-free strong bimonoids (for weighted automata over words) and in terms of bi-strongly zero-sum-free strong bimonoids (for weighted automata over trees). We also consider shortly the images of the two semantics functions.