Recognizable languages in divisibility monoids
Manfred Droste, Dietrich Kuske · Mathematical Structures in Computer Science · 2001
We define the class of divisibility monoids that arise as quotients of the free monoid Σ* modulo certain equations of the form ab = cd. These form a much larger class than free partially commutative monoids, and we show, under certain assumptions, that the recognizable languages in these divisibility monoids coincide with c-rational languages. The proofs rely on Ramsey's theorem, distributive lattice theory and on Hashigushi's rank function generalized to these monoids. We obtain Ochmański's theorem on recognizable languages in free partially commutative monoids as a consequence.