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

RAIRO - Theoretical Informatics and Applications (2010)

- 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 39.1 (2010): 305-322. <http://eudml.org/doc/92763>.

@article{Ésik2010,

abstract = {
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.
},

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

journal = {RAIRO - Theoretical Informatics and Applications},

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

language = {eng},

month = {3},

number = {1},

pages = {305-322},

publisher = {EDP Sciences},

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

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

volume = {39},

year = {2010},

}

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

DA - 2010/3//

PB - EDP Sciences

VL - 39

IS - 1

SP - 305

EP - 322

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

LA - eng

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

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

ER -

## References

top- S.L. Bloom and Z. Ésik, Shuffle binoids. Theoret. Inform. Appl.32 (1998) 175–198.
- Z. Ésik, Free algebras for generalized automata and language theory. RIMS Kokyuroku 1166, Kyoto University, Kyoto (2000) 52–58. Zbl0969.68526
- 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
- 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
- J.L. Gischer, The equational theory of pomsets. Theoret. Comput. Sci.61 (1988) 199–224. Zbl0669.68015
- J. Grabowski, On partial languages. Fund. Inform.4 (1981) 427–498. Zbl0468.68088
- K. Hashiguchi, S. Ichihara and S. Jimbo, Formal languages over free binoids. J. Autom. Lang. Comb. 5 (2000) 219–234. Zbl0965.68038
- K. Hashiguchi, Y. Wada and S. Jimbo, Regular binoid expressions and regular binoid languages. Theoret. Comput. Sci.304 (2003) 291–313. Zbl1045.68081
- D. Kuske, Infinite series-parallel posets: logic and languages, in Proc. ICALP 2000. Lect. Notes Comput. Sci.1853 (2001) 648–662. Zbl0973.68164
- 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
- D. Kuske, Towards a language theory for infinite N-free pomsets. Theoret. Comput. Sci.299 (2003) 347–386. Zbl1040.68055
- K. Lodaya and P. Weil, Kleene iteration for parallelism, in Proc. FST & TCS'98. Lect. Notes Comput. Sci.1530 (1998) 355–366. Zbl0932.68060
- K. Lodaya and P. Weil, Series-parallel languages and the bounded-width property. Theoret. Comput. Sci.237 (2000) 347–380. Zbl0939.68042
- K. Lodaya and P. Weil, Rationality in algebras with series operation. Inform. Comput.171 (2001) 269-293. Zbl1005.68100
- 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.
- D. Perrin and J.-E. Pin, Infinite Words. Pure and Applied Mathematics 141, Academic Press (2003).
- J. Valdes, R.E. Tarjan and E.L. Lawler, The recognition of series-parallel digraphs. SIAM J. Comput.11 (1982) 298–313. Zbl0478.68065
- 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.