A Kleene-Schutzenberger Theorem for Trace Series over Bounded Lattices
We study weighted trace automata with weights in strong bimonoids. Traces form a generalization of words that allow to model concurrency; strong bimonoids are algebraic structures that can be regarded as "semirings without distributivity". A very important example for the latter arc hounded lattices, especially non-distributive ones. We show that if both operations of the bimonoid are locally finite, then the classes of recognizable and me-rational trace series coincide and, in general, are properly contained in the class of e-rational series. Moreover, if, in addition, in the bimonoid the addition is idempotent and the multiplication is commutative, then all three classes coincide.
traces concurrency weighted automata multi-valued logics formal power series