Algebraic and graph-theoretic properties of infinite n-posets

Department of Computer Science, University of Szeged, P.O.B. 652, 6701 Szeged, Hungary; zlnemeth@inf.u-szeged.hu

Abstract

A Σ-labeled n-poset is an (at most) countable set, labeled in the set Σ, equipped with n partial orders. The collection of all Σ-labeled n-posets is naturally equipped with n binary product operations and n ω-ary product operations. Moreover, the ω-ary product operations give rise to n ω-power operations. We show that those Σ-labeled n-posets that can be generated from the singletons by the binary and ω-ary product operations form the free algebra on Σ in a variety axiomatizable by an infinite collection of simple equations. When n = 1, this variety coincides with the class of ω-semigroups of Perrin and Pin. Moreover, we show that those Σ-labeled n-posets that can be generated from the singletons by the binary product operations and the ω-power operations form the free algebra on Σ in a related variety that generalizes Wilke's algebras. We also give graph-theoretic characterizations of those n-posets contained in the above free algebras. Our results serve as a preliminary study to a development of a theory of higher dimensional automata and languages on infinitary associative structures.