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.

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.

Classification : 68Q45, 68R99
Mots clés : poset, $n$-poset, composition, free algebra, equational logic

[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