Algebraic and graph-theoretic properties of infinite n-posets

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

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

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

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.