Algebraic and graph-theoretic properties of infinite $n$-posets

Ésik, Zoltán  ; Németh, Zoltán L.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 305-322

Résumé

A $\Sigma$-labeled $n$-poset is an (at most) countable set, labeled in the set $\Sigma$, equipped with $n$ partial orders. The collection of all $\Sigma$-labeled $n$-posets is naturally equipped with $n$ binary product operations and $n$ $\omega$-ary product operations. Moreover, the $\omega$-ary product operations give rise to $n$ $\omega$-power operations. We show that those $\Sigma$-labeled $n$-posets that can be generated from the singletons by the binary and $\omega$-ary product operations form the free algebra on $\Sigma$ in a variety axiomatizable by an infinite collection of simple equations. When $n=1$, this variety coincides with the class of $\omega$-semigroups of Perrin and Pin. Moreover, we show that those $\Sigma$-labeled $n$-posets that can be generated from the singletons by the binary product operations and the $\omega$-power operations form the free algebra on $\Sigma$ 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.

Détail

DOI : 10.1051/ita:2005018

Classification : 68Q45, 68R99
Keywords: poset, $n$-poset, composition, free algebra, equational logic