×

Free shuffle algebras in language varieties. (English) Zbl 0874.68171

Summary: We give simple concrete descriptions of the free algebras in the varieties generated by the “shuffle semirings” L\(_{\Sigma}:=(P(\Sigma ^{\ast}),+,\cdot ,\otimes ,0,1)\), or the semirings R\(_{\Sigma}:=(R(\Sigma ^{\ast}),+,\cdot ,\otimes ,^{\ast},0,1)\), where \(P(\Sigma ^{\ast})\) is the collection of all subsets of the free monoid \(\Sigma ^{\ast}\), and \(R(\Sigma ^{\ast})\) is the collection of all regular subsets. The operation \(x\otimes\) y is the shuffle product.

MSC:

68Q45 Formal languages and automata
08A70 Applications of universal algebra in computer science
08B20 Free algebras
16Y60 Semirings
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aceto, L., Full abstraction for series-parallel pomsets, (Proc. TAPSOFT ’91. Proc. TAPSOFT ’91, Lecture Notes in Computer Science, Vol. 493 (1991), Springer,: Springer, Berlin), 1-40 · Zbl 0967.68517
[2] Aceto, L.; Hennessy, M., Towards action refinement in process algebras, Inform. and Comput., 103, 204-269 (1993) · Zbl 0779.68028
[3] Bloom, S. L., Varieties of ordered algebras, J. Comput. System Sci., 45, 200-212 (1976) · Zbl 0337.06008
[4] Bloom, S. L.; Ésik, Z., Free shuffle algebras in language varieties: extended abstract, (Proc. Latin ’95 Theoretical Informatics. Proc. Latin ’95 Theoretical Informatics, Lecture Notes in Computer Science, Vol. 911 (1995), Springer,: Springer, Berlin), 99-111 · Zbl 1495.68144
[5] Bloom, S. L.; Ésik, Z., Nonfinite axiomatizability of shuffle inequalities, (Proc. TAPSOFT ’95. Proc. TAPSOFT ’95, Lecture Notes in Computer Science, Vol. 915 (1995), Springer,: Springer, Berlin), 318-333 · Zbl 1496.68206
[6] Ésik, Z.; Bertol, M., Nonfinite axiomatizability of the equational theory of shuffle, (Proc. ICALP ’95. Proc. ICALP ’95, Lecture Notes in Computer Science, Vol. 944 (1995), Springer,: Springer, Berlin), 27-38 · Zbl 0903.68114
[7] Feigenbaum, J.; Kahn, J. A.; Lund, C., Complexity results for pomset languages, SIAM J. Discrete Math., 6, 432-442 (1993) · Zbl 0781.68058
[8] Garey, M. R.; Johnson, D. S., (Computers and Intractability, A Guide to the Theory of NP Completeness (1979), Freeman,: Freeman, New York) · Zbl 0411.68039
[9] Gischer, J. L., Partial orders and the axiomatic theory of shuffle, (Ph.D. Thesis (1984), Stanford University, Computer Science Dept.)
[10] Gischer, J. L., The equational theory of pomsets, Theoret. Comput. Sci., 61, 199-224 (1988) · Zbl 0669.68015
[11] Grabowski, J., On partial languages, Fund. Inform., IV, 427-498 (1981) · Zbl 0468.68088
[12] Kucera, L., Combinatorial Algorithms (1990), Adam Hilger,: Adam Hilger, Bristol · Zbl 0731.68084
[13] Mayer, A. J.; Stockmeyer, L. J., The complexity of word problems — this time with interleaving, Inform. and Comput., 115, 293-311 (1994)
[14] Meyer, A., Some decision problems. Abstract of an Invited Talk, (Proc. STACS ’95. Proc. STACS ’95, Lecture Notes in Computer Science, Vol. 900 (1995), Springer,: Springer, Berlin), 349
[15] A. Meyer and A. Rabinovich, private communication.; A. Meyer and A. Rabinovich, private communication.
[16] Pratt, V., Modeling concurrency with partial orders, Internat. J. Parallel Processing, 15, 33-71 (1986) · Zbl 0622.68034
[17] Stirling, C., Temporal logic for CCS, (Rozenberg, G.; de Bakker, J. W.; de Roever, W.-P., Linear Time, Branching Time and Partial Order in Logics and Models of Concurrency. Linear Time, Branching Time and Partial Order in Logics and Models of Concurrency, Lecture Notes in Computer Science, Vol. 354 (1989), Springer,: Springer, Berlin), 660-672 · Zbl 0683.68016
[18] Tschantz, S. T., Languages under concatenation and shuffling, Math. Struct. Comput. Sci., 4, 505-511 (1994) · Zbl 0829.68077
[19] Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series-parallel digraphs, SIAM J. Comput., 11, 298-313 (1981) · Zbl 0478.68065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.