×

Actions, wreath products of \(\mathcal C\)-varieties and concatenation product. (English) Zbl 1143.68048

Summary: The framework of \(\mathcal C\)-varieties, introduced by the third author, extends the scope of Eilenberg’s variety theory to new classes of languages. In this paper, we first define \(\mathcal C\)-varieties of actions, which are closely related to automata, and prove their equivalence with the original definition of \(\mathcal C\)-varieties of stamps. Next, we complete the study of the wreath product initiated by Ésik and Ito by extending its definition to \(\mathcal C\)-varieties in two different ways, which are proved to be equivalent. We also state an extension of the wreath product principle, a standard tool of language theory. Finally, our main result generalizes to \(\mathcal C\)-varieties the algebraic characterization of the closure under product of a variety of languages.

MSC:

68Q70 Algebraic theory of languages and automata
08A70 Applications of universal algebra in computer science
08B25 Products, amalgamated products, and other kinds of limits and colimits
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barrington, D. A.M.; Compton, K. J.; Straubing, H.; Thérien, D., Regular languages in \(NC^1\), J. Comput. Systems Sci., 44, 478-499 (1992) · Zbl 0757.68057
[2] Branco, M., Varieties of languages, (Gomes, G.; Pin, J.-É.; Silva, P., Semigroups, Algorithms, Automata and Languages (2002), World Scientific: World Scientific Singapore), 91-132 · Zbl 1031.20052
[3] Eilenberg, S., Automata, Languages and Machines, Vol. B (1976), Academic Press, Harcourt Brace Jovanovich Publishers: Academic Press, Harcourt Brace Jovanovich Publishers New York, With two chapters (“Depth decomposition theorem” and “Complexity of semigroups and morphisms”) by Bret Tilson (Ed.), Pure Appl. Math. 59
[4] Ésik, Z., Results on homomorphic realization of automata by \(\alpha_0\)-products, Theoret. Comput. Sci., 87, 2, 229-249 (1991) · Zbl 0744.68104
[5] Z. Ésik, Extended temporal logic on finite words and wreath products of monoids with distinguished generators, in: Ito et al. (Eds.), Developments in Language Theory. Sixth Internat. Conf., DLT 2002, Kyoto, Japan, September 18-21, Lecture Notes in Computer Science, Vol. 2450, Springer, Berlin, 2002, pp. 43-58.; Z. Ésik, Extended temporal logic on finite words and wreath products of monoids with distinguished generators, in: Ito et al. (Eds.), Developments in Language Theory. Sixth Internat. Conf., DLT 2002, Kyoto, Japan, September 18-21, Lecture Notes in Computer Science, Vol. 2450, Springer, Berlin, 2002, pp. 43-58. · Zbl 1015.03025
[6] Ésik, Z.; Ito, M., Temporal logic with cyclic counting and the degree of aperiodicity of finite automata, Acta Cybernet., 16, 1-28 (2003) · Zbl 1027.68074
[7] Ésik, Z.; Larsen, K. G., Regular languages definable by Lindström quantifiers, Theoret. Inform. Appl., 37, 179-241 (2003) · Zbl 1046.20042
[8] Kunc, M., Equational description of pseudovarieties of homomorphisms, Theoret. Inform. Appl., 37, 243-254 (2003) · Zbl 1045.20049
[9] Pin, J.-É., Varieties of Formal Languages (1986), North Oxford, London and Plenum: North Oxford, London and Plenum New York, (Translation of Variétés de langages formels) · Zbl 0632.68069
[10] J.-É. Pin, Syntactic semigroups, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 1, Springer, Berlin, 1997, pp. 679-746 (Chapter 10).; J.-É. Pin, Syntactic semigroups, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 1, Springer, Berlin, 1997, pp. 679-746 (Chapter 10).
[11] Pin, J.-É.; Straubing, H., Some results on \(C\)-varieties, Theoret. Inform. Appl., 39, 239-262 (2005) · Zbl 1083.20059
[12] Pin, J.-É.; Weil, P., The wreath product principle for ordered semigroups, Comm. Algebra, 30, 5677-5713 (2002) · Zbl 1017.06008
[13] Schützenberger, M.-P., On finite monoids having only trivial subgroups, Inform. Control, 8, 190-194 (1965) · Zbl 0131.02001
[14] Straubing, H., Aperiodic homomorphisms and the concatenation product of recognizable sets, J. Pure Appl. Algebra, 15, 3, 319-327 (1979) · Zbl 0407.20056
[15] Straubing, H., Families of recognizable sets corresponding to certain varieties of finite monoids, J. Pure Appl. Algebra, 15, 3, 305-318 (1979) · Zbl 0414.20056
[16] Straubing, H., Relational morphisms and operations on recognizable sets, RAIRO Inform. Theoret., 15, 149-159 (1981) · Zbl 0463.20049
[17] Straubing, H., Finite Automata, Formal Logic, and Circuit Complexity (1994), Birkhäuser Boston Inc.: Birkhäuser Boston Inc. Boston, MA · Zbl 0816.68086
[18] H. Straubing, On logical descriptions of regular languages, in: LATIN 2002, Lecture Notes in Computer Science, Vol. 2286, Springer, Berlin, 2002, pp. 528-538.; H. Straubing, On logical descriptions of regular languages, in: LATIN 2002, Lecture Notes in Computer Science, Vol. 2286, Springer, Berlin, 2002, pp. 528-538. · Zbl 1059.03034
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.