Shuffle binoids

S. L. Bloom; Z. Ésik

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

  • Volume: 32, Issue: 4-6, page 175-198
  • ISSN: 0988-3754

How to cite


Bloom, S. L., and Ésik, Z.. "Shuffle binoids." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 32.4-6 (1998): 175-198. <>.

author = {Bloom, S. L., Ésik, Z.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {4-6},
pages = {175-198},
publisher = {EDP-Sciences},
title = {Shuffle binoids},
url = {},
volume = {32},
year = {1998},

AU - Bloom, S. L.
AU - Ésik, Z.
TI - Shuffle binoids
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1998
PB - EDP-Sciences
VL - 32
IS - 4-6
SP - 175
EP - 198
LA - eng
UR -
ER -


  1. [Blo76] S. L. BLOOM, Varieties of ordered algebras. Journal of Computer and System Sciences, Vol. 45, 1976, pp. 200-212. Zbl0337.06008MR427204
  2. [BÉ95] S. L. BLOOM and Z. ÉSIK, Nonfinite axiomatizability of shuffle inequalities. In Proceedings of TAPSOFT'95, volume 915 of Lecture Notes in Computer Science, 1995, pp. 318-333. 
  3. [BÉ96] S. L. BLOOM and Z. ÉSIK, Free shuffle algebras in language varieties. Theoretical Computer Science, Vol. 163, 1996, pp. 55-98. Zbl0874.68171MR1407015
  4. [BÉ97] S. L. BLOOM and Z. ÉSIK, Axiomatizing shuffle and concatenation in languages. Information and Computation, Vol. 139, 1997, pp. 62-91. Zbl0892.68055MR1482961
  5. [BÉSt] S. L. BLOOM, Z. ÉSIK and Gh. STEFANESCU, Equational theories of relations and regular sets. In Proc. of Words, Languages and Combinatorics, II, M. ITO and M. JÜRGENSEN Eds., Kyoto, 1992 World Scientific, 1994, pp. 40-48. Zbl0874.08002MR1351278
  6. [Bof90] M. BOFFA, Une remarque sur les systèmes complets d'identités rationnelles, Theoret. Inform. Appl., Vol. 24, 1990, pp. 419-423. Zbl0701.68059MR1079723
  7. [Bof95] M. BOFFA, Une condition impliquant toutes les identités rationnelles, Theoret. Inform. Appl., Vol. 29, 1995, pp. 515-518. Zbl0881.68071MR1377029
  8. [ÉB95] Z. Esik and L. BERNÁTSKY, Scott induction and equational proofs, in: Mathematical Foundations of Programming Semantics'95, ENTCS, Vol. 1, 1995. Zbl0910.68129MR1486847
  9. [ÉBrt95] Z. ÉSIK and M. BERTOL, Nonfinite axiomatizability of the equational theory of shuffle. In Proceedings of ICALP 95, volume 944 of Lecture Notes in Computer Science, 1995, pp. 27-38. MR1466455
  10. [És98] Z. ÉSIK, Group axioms for iteration, Information and Computation, to appear. Zbl0924.68143MR1674307
  11. [Gis84] J. L. GISCHER, Partial Orders and the Axiomatic Theory of Shuffle. PhD thesis, Stanford University, Computer Science Dept., 1984. 
  12. [Gis88] J. L. GISCHER, The equational theory of pomsets. Theoretical Computer Science, Vol. 61, 1988, pp. 199-224. Zbl0669.68015MR980242
  13. [Gra81] J. GRABOWSKI, On partial languages. Fundamenta Informatica, Vol. IV(2), 1981, pp. 427-498. Zbl0468.68088MR645249
  14. [Koz94] D. KOZEN, A completeness theorem for Kleene algebras and the algebra of regular events, Information and Computation, Vol. 110, 1994, pp. 366-390. Zbl0806.68082MR1276741
  15. [Kr91] D. KROB, Complete Systems of B-rational identities, Theoretical Computer Science, Vol. 89, 1991, pp. 207-343. Zbl0737.68053MR1133622
  16. [Kuc90] L. KUCERA, Combinatorial Algorithms, Adam Hilger (Bristol and Philadelphia), 1990. Zbl0731.68084MR1100475
  17. [Pra86] V. PRATT, Modeling concurrency with partial orders. Internat. J. Parallel Processing, Vol. 15, 1986, pp. 33-71. Zbl0622.68034MR867968
  18. [WT90] W. THOMAS, Automata on infinite objects. In Handbook of Theoretical Computer Science, Vol. B, Formal Models and Semantics, MIT Press, 1990, pp. 133-192. Zbl0900.68316MR1127189
  19. [Tsc94] Steven T. TSCHANTZ, Languages under concatenation and shuffling, Mathematical Structures in Computer Science, Vol. 4, 1994, pp. 505-511. Zbl0829.68077MR1322185
  20. [VTL81] J. VALDES, R. E. TARJAN and E. L. LAWLER, The recognition of series-parallel digraphs. SIAM Journal of Computing, Vol. 11(2), 1981, pp. 298-313. Zbl0478.68065MR652904
  21. [Wil93] T. WILKE, An algebraic theory for regular languages of finite and infinite words. International Journal of Algebra and Computation, Vol. 3, 1993, pp. 447-489. Zbl0791.68116MR1250247
  22. [Wil91] T. WILKE, An Eilenberg Theorem for ∞-languages. In "Automata, Languages and Programming", Proc. of 18th ICALP Conference, Vol. 510 of Lecture Notes in Computer Science, 1991, pp. 588-599. Zbl0766.68083MR1129938

NotesEmbed ?


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.