A Kleene-Schützenberger theorem for trace series over bounded lattices (Q2882389)

The author investigates the relation between the recognizability and the rationality of weighted trace languages with weights in a bimonoid, i.e., an algebra with two monoid structures. The bimonoids considered here have various additional properties like local finiteness, commutativity or idempotence. The two special types of rationality studied, \(c\)-rationality and \(mc\)-rationality, are defined by restricting the use of the iteration operation.NEWLINENEWLINE The main theorem states that a trace series over a bi-locally finite strong bimonoid is recognizable if and only if it is \(mc\)-rational, and that, if the bimonoid is also idempotent and commutative, then \(c\)-rationality implies recognizability. In particular, for trace series over a bounded lattice, recognizability, \(mc\)-rationality and \(c\)-rationality are equivalent properties.