Shuffle binoids
Bloom, S. L. ; Ésik, Z.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 32 (1998), p. 175-198 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1998-01-01
@article{ITA_1998__32_4-6_175_0,
     author = {Bloom, S. L. and \'Esik, Z.},
     title = {Shuffle binoids},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {32},
     year = {1998},
     pages = {175-198},
     mrnumber = {1672727},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1998__32_4-6_175_0}
}

Bloom, S. L.; Ésik, Z. Shuffle binoids. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 32 (1998) pp. 175-198. http://gdmltest.u-ga.fr/item/ITA_1998__32_4-6_175_0/

[Blo76] S. L. Bloom, Varieties of ordered algebras. Journal of Computer and System Sciences, Vol. 45, 1976, pp. 200-212. | MR 427204 | Zbl 0337.06008

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

[BÉ96] S. L. Bloom and Z. Ésik, Free shuffle algebras in language varieties. Theoretical Computer Science, Vol. 163, 1996, pp. 55-98. | MR 1407015 | Zbl 0874.68171

[BÉ97] S. L. Bloom and Z. Ésik, Axiomatizing shuffle and concatenation in languages. Information and Computation, Vol. 139, 1997, pp. 62-91. | MR 1482961 | Zbl 0892.68055

[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. | MR 1351278 | Zbl 0874.08002

[Bof90] M. Boffa, Une remarque sur les systèmes complets d'identités rationnelles, Theoret. Inform. Appl., Vol. 24, 1990, pp. 419-423. | Numdam | MR 1079723 | Zbl 0701.68059

[Bof95] M. Boffa, Une condition impliquant toutes les identités rationnelles, Theoret. Inform. Appl., Vol. 29, 1995, pp. 515-518. | Numdam | MR 1377029 | Zbl 0881.68071

[ÉB95] Z. Esik and L. Bernátsky, Scott induction and equational proofs, in: Mathematical Foundations of Programming Semantics'95, ENTCS, Vol. 1, 1995. | MR 1486847 | Zbl 0910.68129

[É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. | MR 1466455

[És98] Z. Ésik, Group axioms for iteration, Information and Computation, to appear. | MR 1674307 | Zbl 0924.68143

[Gis84] J. L. Gischer, Partial Orders and the Axiomatic Theory of Shuffle. PhD thesis, Stanford University, Computer Science Dept., 1984.

[Gis88] J. L. Gischer, The equational theory of pomsets. Theoretical Computer Science, Vol. 61, 1988, pp. 199-224. | MR 980242 | Zbl 0669.68015

[Gra81] J. Grabowski, On partial languages. Fundamenta Informatica, Vol. IV(2), 1981, pp. 427-498. | MR 645249 | Zbl 0468.68088

[Koz94] D. Kozen, A completeness theorem for Kleene algebras and the algebra of regular events, Information and Computation, Vol. 110, 1994, pp. 366-390. | MR 1276741 | Zbl 0806.68082

[Kr91] D. Krob, Complete Systems of B-rational identities, Theoretical Computer Science, Vol. 89, 1991, pp. 207-343. | MR 1133622 | Zbl 0737.68053

[Kuc90] L. Kucera, Combinatorial Algorithms, Adam Hilger (Bristol and Philadelphia), 1990. | MR 1100475 | Zbl 0731.68084

[Pra86] V. Pratt, Modeling concurrency with partial orders. Internat. J. Parallel Processing, Vol. 15, 1986, pp. 33-71. | MR 867968 | Zbl 0622.68034

[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. | MR 1127189 | Zbl 0900.68316

[Tsc94] Steven T. Tschantz, Languages under concatenation and shuffling, Mathematical Structures in Computer Science, Vol. 4, 1994, pp. 505-511. | MR 1322185 | Zbl 0829.68077

[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. | MR 652904 | Zbl 0478.68065

[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. | MR 1250247 | Zbl 0791.68116

[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. | MR 1129938 | Zbl 0766.68083