spacer
EDP Sciences Journals List
Home arrow Document
Subscriber Authentication Point
   
Issue Theoret. Informatics Appl.
Volume 39, Number 1, January-March 2005
Imre Simon, the tropical computer scientist
Page(s) 305 - 322
DOI 10.1051/ita:2005018

Theoret. Informatics Appl. 39, 305-322 (2005)
DOI: 10.1051/ita:2005018

Algebraic and graph-theoretic properties of infinite n-posets

Zoltán Ésik and Zoltán L. Németh

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


Abstract
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.


Mathematics Subject Classification. 68Q45, 68R99

Key words: Poset -- n-poset -- composition -- free algebra -- equational logic


© EDP Sciences 2005


What is OpenURL?