A Theorem on Supports of Weighted Tree Automata Over Strong Bimonoids
Maryam Ghorani, Heiko Vogler · New Mathematics and Natural Computation · 2022
We investigate weighted tree automata over strong bimonoids. Intuitively, strong bimonoids are semirings which may lack the distributivity laws. For instance, each (not necessarily distributive) bounded lattice is a strong bimonoid. In general, for a weighted tree automaton over a strong bimonoid, its run semantics is different from its initial algebra semantics. We prove that for positive strong bimonoids the supports of these semantics are equal, and we also deal with a kind of reverse statement.