Eilenberg’s variety theorem without Boolean operations. (English) Zbl 07798807
Summary: Eilenberg’s variety theorem marked a milestone in the algebraic theory of regular languages by establishing a formal correspondence between properties of regular languages and properties of finite monoids recognizing them. Motivated by classes of languages accepted by quantum finite automata, we introduce basic varieties of regular languages, a weakening of Eilenberg’s original concept that does not require closure under any boolean operations, and prove a variety theorem for them. To do so, we investigate the algebraic recognition of languages by lattice bimodules, generalizing Klíma and Polák’s lattice algebras, and we utilize the duality between algebraic completely distributive lattices and posets.
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Schützenberger, M.-P., On finite monoids having only trivial subgroups. Inf. Control, 2, 190-194 (1965) · Zbl 0131.02001 |
| [2] | Eilenberg, S., Automata, Languages, and Machines (1974), Academic Press · Zbl 0317.94045 |
| [3] | Wilke, T., An Eilenberg theorem for infinity-languages, 588-599 |
| [4] | Pin, J.-E., A variety theorem without complementation. Russ. Math., 80-90 (1995) |
| [5] | Polák, L., Syntactic semiring of a language, 611-620 |
| [6] | Golovkins, M.; Pin, J.-E., Varieties generated by certain models of reversible finite automata, 83-93 |
| [7] | Kondacs, A.; Watrous, J., On the power of quantum finite state automata, 66-75 |
| [8] | Klíma, O.; Polák, L., Syntactic structures of regular languages. Theor. Comput. Sci., 125-141 (2019) · Zbl 1436.68177 |
| [9] | Gehrke, M.; Grigorieff, S.; Pin, J.-E., Duality and equational theory of regular languages, 246-257 · Zbl 1165.68049 |
| [10] | Salamanca, J., Unveiling Eilenberg-type correspondences: Birkhoff’s theorem for (finite) algebras + duality (2017), preprint |
| [11] | Urbat, H.; Adámek, J.; Chen, L.-T.; Milius, S., Eilenberg theorems for free, 43:1-43:14 |
| [12] | Adámek, J.; Milius, S.; Myers, R.; Urbat, H., Generalized Eilenberg theorem: varieties of languages in a category. ACM Trans. Comput. Log., 1, 3:1-3:47 (2019) · Zbl 1407.68315 |
| [13] | Bojańczyk, M., Recognisable Languages over Monads. Proc. DLT, 1-13 (2015), Springer · Zbl 1434.68307 |
| [14] | Birkmann, F.; Milius, S.; Urbat, H., On language varieties without Boolean operations, 3-15 · Zbl 07405973 |
| [15] | Manes, E., Algebraic Theories. Graduate Texts in Mathematics (1976), Springer · Zbl 0353.18007 |
| [16] | Markowsky, G., Free completely distributive lattices. Proc. Am. Math. Soc., 227-228 (1979) · Zbl 0377.06005 |
| [17] | Pin, J.-É., Mathematical foundations of automata theory (December 2020), available at |
| [18] | Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (2002), Cambridge University Press · Zbl 1002.06001 |
| [19] | Ambainis, A.; Yakaryılmaz, A., Automata and quantum computing (2018), preprint |
| [20] | Brodsky, A.; Pippenger, N., Characterizations of 1-way quantum finite automata. SIAM J. Comput., 73-91 (1999) |
| [21] | Rabin, M. O., Probabilistic automata. Inf. Control, 3, 230-245 (1963) · Zbl 0182.33602 |
| [22] | Ambainis, A.; Freivalds, R., 1-way quantum finite automata: strengths, weaknesses and generalizations, 332-341 |
| [23] | Ambainis, A.; Bonner, R.; Freivalds, R.; Ķikusts, A., Probabilities to accept languages by quantum finite automata, 174-183 · Zbl 0944.68118 |
| [24] | Moore, C.; Crutchfield, J. P., Quantum automata and quantum grammars. Theor. Comput. Sci., 1-2, 275-306 (2000) · Zbl 0939.68037 |
| [25] | Ambainis, A.; Ķikusts, A.; Valdats, M., On the class of languages recognizable by 1-way quantum finite automata, 75-86 · Zbl 0976.68087 |
| [26] | Reiterman, J., The Birkhoff theorem for finite algebras. Algebra Univers., 1, 1-10 (1982) · Zbl 0484.08007 |
| [27] | Chen, L.-T.; Adámek, J.; Milius, S.; Urbat, H., Profinite monads, profinite equations, and Reiterman’s theorem, 531-547 · Zbl 1474.18010 |
| [28] | Milius, S.; Urbat, H., Equational axiomatization of algebras with structure, 400-417 · Zbl 1524.08003 |
| [29] | MacLane, S., Categories for the Working Mathematician. Graduate Texts in Mathematics (1998), Springer · Zbl 0906.18001 |
| [30] | Pedicchio, M. C.; Wood, R. J., Groupoidal completely distributive lattices. J. Pure Appl. Algebra, 1, 339-350 (1999) · Zbl 0936.18004 |
| [31] | Borceux, F., Handbook of Categorical Algebra: Volume 2, Categories and Structures. Cambridge Studies in Philosophy (1994), Cambridge University Press · Zbl 0843.18001 |
| [32] | Adámek, J.; Herrlich, H.; Strecker, G. E., Abstract and Concrete Categories - The Joy of Cats (2009), Dover Publications |
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.
