Two equational theories of partial words

Partial words are in our terminology isomorphism classes of labeled partial orders. We consider two structures. Starting with the partial orders reduced to a unique element, the first one is defined as the closure under the three operations of series product, parallel product and ω-power (ω-series product of the same partial word) and the second one as the closure under the three operations of series product, parallel product and ω-product (ω-series product of possibly different partial words). We show that the two equational theories can be axiomatized by an infinite collection of simple identities, and that no finite axiomatization exists. We characterize the free algebras in the corresponding varieties as algebras of certain partial words subject to order and graph theoretic conditions. We also show that the first equational theory is decidable.