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.

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.

DOI : 10.1051/ita:2005018
Classification : 68Q45, 68R99
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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ita:2005018/

[1] S.L. Bloom and Z. Ésik, Shuffle binoids. Theoret. Inform. Appl. 32 (1998) 175-198.

[2] Z. Ésik, Free algebras for generalized automata and language theory. RIMS Kokyuroku 1166, Kyoto University, Kyoto (2000) 52-58. | Zbl

[3] Z. Ésik and Z.L. Németh, Automata on series-parallel biposets, in Proc. DLT'01. Lect. Notes Comput. Sci. 2295 (2002) 217-227. | Zbl

[4] Z. Ésik and S. Okawa, Series and parallel operations on pomsets, in Proc. FST & TCS'99. Lect. Notes Comput. Sci. 1738 (1999) 316-328. | Zbl

[5] J.L. Gischer, The equational theory of pomsets. Theoret. Comput. Sci. 61 (1988) 199-224. | Zbl

[6] J. Grabowski, On partial languages. Fund. Inform. 4 (1981) 427-498. | Zbl

[7] K. Hashiguchi, S. Ichihara and S. Jimbo, Formal languages over free binoids. J. Autom. Lang. Comb. 5 (2000) 219-234. | Zbl

[8] K. Hashiguchi, Y. Wada and S. Jimbo, Regular binoid expressions and regular binoid languages. Theoret. Comput. Sci. 304 (2003) 291-313. | Zbl

[9] D. Kuske, Infinite series-parallel posets: logic and languages, in Proc. ICALP 2000. Lect. Notes Comput. Sci. 1853 (2001) 648-662. | Zbl

[10] D. Kuske, 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] D. Kuske, Towards a language theory for infinite N-free pomsets. Theoret. Comput. Sci. 299 (2003) 347-386. | Zbl

[12] K. Lodaya and P. Weil, Kleene iteration for parallelism, in Proc. FST & TCS'98. Lect. Notes Comput. Sci. 1530 (1998) 355-366. | Zbl

[13] K. Lodaya and P. Weil, Series-parallel languages and the bounded-width property. Theoret. Comput. Sci. 237 (2000) 347-380. | Zbl

[14] K. Lodaya and P. Weil, Rationality in algebras with series operation. Inform. Comput. 171 (2001) 269-293. | MR | Zbl

[15] D. Perrin and J.-E. Pin, 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

[16] D. Perrin and J.-E. Pin, Infinite Words. Pure and Applied Mathematics 141, Academic Press (2003). | Zbl

[17] J. Valdes, R.E. Tarjan and E.L. Lawler, The recognition of series-parallel digraphs. SIAM J. Comput. 11 (1982) 298-313. | Zbl

[18] Th. Wilke, An algebraic theory for regular languages of finite and infinite words. Internat. J. Algebra Comput. 3 (1993) 447-489. | Zbl

Cité par Sources :