×

Axiomatizing shuffle and concatenation in languages. (English) Zbl 0892.68055

Summary: We consider the variety \({\mathbf L}{\mathbf a}{\mathbf n}{\mathbf g}\) generated by all language structures \((P_\Sigma,\cdot, \otimes, +, 0,1)\), and the variety \({\mathbf L}{\mathbf g}_\leq\) of ordered algebras generated by the structures \((P_\Sigma, \cdot, \otimes, 0, 1,\subseteq)\), where \(P_\Sigma\) is the power set of \(\Sigma^*\), and where \(B\cdot C\) is the complex concatenation of the languages \(B\), \(C\subseteq \Sigma^*\), \(B\otimes C\) is their shuffle product, and \(B+C\) is their union. We prove that for each finite set \(E\) of equations valid in \({\mathbf L}{\mathbf a}{\mathbf n}{\mathbf g}\) there is a (finite) model \(S_E\) of \(E\) in which some inequation valid in \({\mathbf L}{\mathbf g}_\leq\) fails. It follows that neither variety is finitely axiomatizable.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bloom, S. L.; Ésik, Z., Equational axioms for regular sets, Math. Structures Comput. Sci., 3, 1-24 (1993) · Zbl 0796.68153
[2] Bloom, S. L.; Ésik, Z., Nonfinite axiomatizability of shuffle inequalities, Proceedings of TAPSOFT ’95. Proceedings of TAPSOFT ’95, Lecture Notes in Computer Science, 915 (1995), Springer-Verlag: Springer-Verlag Berlin/New York, p. 318-333 · Zbl 1496.68206
[3] Bloom, S. L.; Ésik, Z., Free shuffle algebras in language varieties, Theoret. Comput. Sci., 163, 55-98 (1996) · Zbl 0874.68171
[4] Bloom, S. L., Varieties of ordered algebras, J. Comput. System Sci., 45, 200-212 (1976) · Zbl 0337.06008
[5] Ésik, Z.; Bertol, M., Nonfinite axiomatizability of the equational theory of shuffle, Proceedings of ICALP’95. Proceedings of ICALP’95, Lecture Notes in Computer Science, 944 (1995), Springer-Verlag: Springer-Verlag Berlin/New York, p. 27-38 · Zbl 1412.68141
[6] Jay, L. Gischer, 1984, Partial Orders and the Axiomatic Theory of Shuffle, Computer Science Dept. Stanford University; Jay, L. Gischer, 1984, Partial Orders and the Axiomatic Theory of Shuffle, Computer Science Dept. Stanford University · Zbl 0471.68063
[7] Gischer, Jay L., The equational theory of pomsets, Theoret. Comput. Sci., 61, 199-224 (1988) · Zbl 0669.68015
[8] Grabowski, Jan, On partial languages, Fund. Inform., IV, 427-498 (1981) · Zbl 0468.68088
[9] Pratt, V. R., Action logic and pure induction, Logics in AI: European Workshop JELIA’90, Amsterdam, September 1990. Logics in AI: European Workshop JELIA’90, Amsterdam, September 1990, Lecture Notes in Computer Science, 478 (1990), Springer-Verlag: Springer-Verlag Berlin/New York, p. 97-120 · Zbl 0814.03024
[10] Tschantz, Steven T., Languages under concatenation and shuffling, Math. Structures Comput. Sci., 4, 505-511 (1994) · Zbl 0829.68077
[11] R. J. van Glabbeek, 1990, The refinement theorem for ST-bisimulation, IFIP TC2 Working Conference on Programming Concepts and Methods, M. BroyC. B. Jones, Lecture Notes in Computer Science, 27, 52, North-Holland, Amsterdam; R. J. van Glabbeek, 1990, The refinement theorem for ST-bisimulation, IFIP TC2 Working Conference on Programming Concepts and Methods, M. BroyC. B. Jones, Lecture Notes in Computer Science, 27, 52, North-Holland, Amsterdam
[12] R. J. van Glabbeek, 1995, The Difference between Splitting in \(nn\); R. J. van Glabbeek, 1995, The Difference between Splitting in \(nn\)
[13] Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series-parallel digraphs, SIAM J. Comput., 11, 298-313 (1981) · Zbl 0478.68065
[14] Vogler, Walter, Failure semantics based on interval semiwords is a congruence for refinement, Distrib. Comput., 4, 139-162 (1991) · Zbl 0723.68069
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.