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

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

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), p. 305-322 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

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.

Publié le : 2005-01-01

MR 2132594 | Zbl 1102.68060

DOI : https://doi.org/10.1051/ita:2005018
Classification: 68Q45, 68R99

@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},
     volume = {39},
     year = {2005},
     pages = {305-322},
     doi = {10.1051/ita:2005018},
     mrnumber = {2132594},
     zbl = {1102.68060},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 305-322. doi : 10.1051/ita:2005018. http://gdmltest.u-ga.fr/item/ITA_2005__39_1_305_0/

Bibliographie

[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 0969.68526

[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 1073.68668

[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 0959.08002

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

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

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

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

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

[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 0976.03045

[11] D. Kuske, Towards a language theory for infinite N-free pomsets. Theoret. Comput. Sci. 299 (2003) 347-386. | Zbl 1040.68055

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

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

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

[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 0877.20045

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

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

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