Shuffle binoids

 Access to full text

 Full (PDF)

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

1. Zoltán Ésik, Zoltán L. Németh, Algebraic and graph-theoretic properties of infinite $n$-posets
2. A. Szepietowski, There is no complete axiom system for shuffle expressions
3. A. Szepietowski, There is no complete axiom system for shuffle expressions
4. Zoltán Ésik, Zoltán L. Németh, Algebraic and graph-theoretic properties of infinite -posets