We consider two-sorted algebras of finite and infinite partial words equipped with the sub-sumption preorder and the operations of series and parallel product and omega power. It is shown that the valid equations and inequations of these algebras can be described by an infinite collection of simple axioms, and that no finite axiomatization exists. We also prove similar results for two related preorders, namely for the induced partial subword preorder and the partial subword preorder. Along the way of proving these results, we provide a concrete description of the free algebras in the corresponding varieties in terms of generalized series-parallel partial words.
展开▼
