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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

- Volume: 39, Issue: 1, page 305-322
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topÉsik, Zoltán, and Németh, Zoltán L.. "Algebraic and graph-theoretic properties of infinite $n$-posets." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.1 (2005): 305-322. <http://eudml.org/doc/246097>.

@article{Ésik2005,

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.},

author = {Ésik, Zoltán, Németh, Zoltán L.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {poset; $n$-poset; composition; free algebra; equational logic},

language = {eng},

number = {1},

pages = {305-322},

publisher = {EDP-Sciences},

title = {Algebraic and graph-theoretic properties of infinite $n$-posets},

url = {http://eudml.org/doc/246097},

volume = {39},

year = {2005},

}

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

PB - EDP-Sciences

VL - 39

IS - 1

SP - 305

EP - 322

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

LA - eng

KW - poset; $n$-poset; composition; free algebra; equational logic

UR - http://eudml.org/doc/246097

ER -

## References

top- [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. Zbl0969.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. Zbl1073.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. Zbl0959.08002
- [5] J.L. Gischer, The equational theory of pomsets. Theoret. Comput. Sci. 61 (1988) 199–224. Zbl0669.68015
- [6] J. Grabowski, On partial languages. Fund. Inform. 4 (1981) 427–498. Zbl0468.68088
- [7] K. Hashiguchi, S. Ichihara and S. Jimbo, Formal languages over free binoids. J. Autom. Lang. Comb. 5 (2000) 219–234. Zbl0965.68038
- [8] K. Hashiguchi, Y. Wada and S. Jimbo, Regular binoid expressions and regular binoid languages. Theoret. Comput. Sci. 304 (2003) 291–313. Zbl1045.68081
- [9] D. Kuske, Infinite series-parallel posets: logic and languages, in Proc. ICALP 2000. Lect. Notes Comput. Sci. 1853 (2001) 648–662. Zbl0973.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. Zbl0976.03045
- [11] D. Kuske, Towards a language theory for infinite N-free pomsets. Theoret. Comput. Sci. 299 (2003) 347–386. Zbl1040.68055
- [12] K. Lodaya and P. Weil, Kleene iteration for parallelism, in Proc. FST & TCS’98. Lect. Notes Comput. Sci. 1530 (1998) 355–366. Zbl0932.68060
- [13] K. Lodaya and P. Weil, Series-parallel languages and the bounded-width property. Theoret. Comput. Sci. 237 (2000) 347–380. Zbl0939.68042
- [14] K. Lodaya and P. Weil, Rationality in algebras with series operation. Inform. Comput. 171 (2001) 269-293. Zbl1005.68100MR1872782
- [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. Zbl0877.20045
- [16] D. Perrin and J.-E. Pin, Infinite Words. Pure and Applied Mathematics 141, Academic Press (2003). Zbl1094.68052
- [17] J. Valdes, R.E. Tarjan and E.L. Lawler, The recognition of series-parallel digraphs. SIAM J. Comput. 11 (1982) 298–313. Zbl0478.68065
- [18] Th. Wilke, An algebraic theory for regular languages of finite and infinite words. Internat. J. Algebra Comput. 3 (1993) 447–489. Zbl0791.68116

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.