A -labeled -poset is an (at most) countable set, labeled in the set , equipped with partial orders. The collection of all -labeled -posets is naturally equipped with binary product operations and -ary product operations. Moreover, the -ary product operations give rise to -power operations. We show that those -labeled -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 , this variety coincides with the class of -semigroups of Perrin and Pin. Moreover, we show that those -labeled -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 -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.
Mots-clés : poset, $n$-poset, composition, free algebra, equational logic
@article{ITA_2005__39_1_305_0, author = {\'Esik, Zolt\'an and N\'emeth, Zolt\'an L.}, title = {Algebraic and graph-theoretic properties of infinite $n$-posets}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {305--322}, publisher = {EDP-Sciences}, volume = {39}, number = {1}, year = {2005}, doi = {10.1051/ita:2005018}, mrnumber = {2132594}, zbl = {1102.68060}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2005018/} }
TY - JOUR AU - Ésik, Zoltán AU - Németh, Zoltán L. TI - Algebraic and graph-theoretic properties of infinite $n$-posets JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2005 SP - 305 EP - 322 VL - 39 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2005018/ DO - 10.1051/ita:2005018 LA - en ID - ITA_2005__39_1_305_0 ER -
%0 Journal Article %A Ésik, Zoltán %A Németh, Zoltán L. %T Algebraic and graph-theoretic properties of infinite $n$-posets %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 305-322 %V 39 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2005018/ %R 10.1051/ita:2005018 %G en %F ITA_2005__39_1_305_0
Ésik, Zoltán; Németh, Zoltán L. Algebraic and graph-theoretic properties of infinite $n$-posets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 305-322. doi : 10.1051/ita:2005018. http://archive.numdam.org/articles/10.1051/ita:2005018/
[1] Shuffle binoids. Theoret. Inform. Appl. 32 (1998) 175-198.
and ,[2] Free algebras for generalized automata and language theory. RIMS Kokyuroku 1166, Kyoto University, Kyoto (2000) 52-58. | Zbl
,[3] Automata on series-parallel biposets, in Proc. DLT'01. Lect. Notes Comput. Sci. 2295 (2002) 217-227. | Zbl
and ,[4] Series and parallel operations on pomsets, in Proc. FST & TCS'99. Lect. Notes Comput. Sci. 1738 (1999) 316-328. | Zbl
and ,[5] The equational theory of pomsets. Theoret. Comput. Sci. 61 (1988) 199-224. | Zbl
,[6] On partial languages. Fund. Inform. 4 (1981) 427-498. | Zbl
,[7] Formal languages over free binoids. J. Autom. Lang. Comb. 5 (2000) 219-234. | Zbl
, and ,[8] Regular binoid expressions and regular binoid languages. Theoret. Comput. Sci. 304 (2003) 291-313. | Zbl
, and ,[9] Infinite series-parallel posets: logic and languages, in Proc. ICALP 2000. Lect. Notes Comput. Sci. 1853 (2001) 648-662. | Zbl
,[10] A model theoretic proof of Büchi-type theorems and first-order logic for N-free pomsets, in Proc. STACS'01. Lect. Notes Comput. Sci. 2010 (2001) 443-454. | Zbl
,[11] Towards a language theory for infinite N-free pomsets. Theoret. Comput. Sci. 299 (2003) 347-386. | Zbl
,[12] Kleene iteration for parallelism, in Proc. FST & TCS'98. Lect. Notes Comput. Sci. 1530 (1998) 355-366. | Zbl
and ,[13] Series-parallel languages and the bounded-width property. Theoret. Comput. Sci. 237 (2000) 347-380. | Zbl
and ,[14] Rationality in algebras with series operation. Inform. Comput. 171 (2001) 269-293. | MR | Zbl
and ,[15] Semigroups and automata on infinite words, in Semigroups, Formal Languages and Groups (York, 1993), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 466 (1995) 49-72. | Zbl
and ,[16] Infinite Words. Pure and Applied Mathematics 141, Academic Press (2003). | Zbl
and ,[17] The recognition of series-parallel digraphs. SIAM J. Comput. 11 (1982) 298-313. | Zbl
, and ,[18] An algebraic theory for regular languages of finite and infinite words. Internat. J. Algebra Comput. 3 (1993) 447-489. | Zbl
,Cité par Sources :