Affiliations: Institut für Theoretische Informatik, Technische Universität Ilmenau, Germany. [email protected]
Note: [] Address for correspondence: Institut für Theoretische Informatik, TU Ilmenau, Postfach 10 05 65, D-98684 Ilmenau, Germany
Abstract: 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 are bounded lattices, especially non-distributive ones. We show that if both operations of the bimonoid are locally finite, then the classes of recognizable and mc-rational trace series coincide and, in general, are properly contained in the class of c-rational series. Moreover, if, in addition, in the bimonoid the addition is idempotent and the multiplication is commutative, then all three classes coincide.
Keywords: weighted automata, concurrency, multi-valued logics, traces, formal power series
