On language varieties without Boolean operations. (English) Zbl 07405973
Leporati, Alberto (ed.) et al., Language and automata theory and applications. 15th international conference, LATA 2021, Milan, Italy, March 1–5, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12638, 3-15 (2021).
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.
For the entire collection see [Zbl 1470.68022].
For the entire collection see [Zbl 1470.68022].
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | Adámek, J., Milius, S., Myers, R., Urbat, H.: Generalized Eilenberg theorem: varieties of languages in a category. ACM Trans. Comput. Log. 20(1), 3:1-3:47 (2019) · Zbl 1407.68315 |
| [2] | Ambainis, A., Yakaryılmaz, A.: Automata and quantum computing (2018). https://arxiv.org/abs/1507.01988 · Zbl 1237.68082 |
| [3] | Ambainis, A., Beaudry, M., Golovkins, M., Kikusts, A., Mercer, M., Thérien, D.: Algebraic results on quantum automata. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 93-104. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24749-4_9 · Zbl 1122.68079 |
| [4] | Ambainis1, A., Ķikusts, A., Valdats, M.: On the class of languages recognizable by 1-way quantum finite automata. In: Ferreira, A. Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 75-86. Springer, Heidelberg (2001). doi:10.1007/3-540-44693-1_7 · Zbl 0976.68087 |
| [5] | Bojańczyk, M.; Potapov, I., Recognisable languages over monads, Developments in Language Theory, 1-13 (2015), Cham: Springer, Cham · Zbl 1434.68307 · doi:10.1007/978-3-319-21500-6_1 |
| [6] | Brodsky, A.; Pippenger, N., Characterizations of 1-way quantum finite automata, SIAM J. Comput., 31, 73-91 (1999) · Zbl 1051.68062 |
| [7] | Chen, L-T; Adámek, J.; Milius, S.; Urbat, H.; Jacobs, B.; Löding, C., Profinite monads, profinite equations, and Reiterman’s theorem, Foundations of Software Science and Computation Structures, 531-547 (2016), Heidelberg: Springer, Heidelberg · Zbl 1474.18010 · doi:10.1007/978-3-662-49630-5_31 |
| [8] | Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order, 2 edn. Cambridge University Press, Cambridge (2002) · Zbl 1002.06001 |
| [9] | Eilenberg, S.: Automata, Languages, and Machines. Academic Press, Cambridge (1974) · Zbl 0317.94045 |
| [10] | Gehrke, M.; Grigorieff, S.; Pin, JÉ; Aceto, L.; Damgård, I.; Goldberg, LA; Halldórsson, MM; Ingólfsdóttir, A.; Walukiewicz, I., Duality and equational theory of regular languages, Automata, Languages and Programming, 246-257 (2008), Heidelberg: Springer, Heidelberg · Zbl 1165.68049 · doi:10.1007/978-3-540-70583-3_21 |
| [11] | Golovkins, M.; Pin, J-E; Chen, DZ; Lee, DT, Varieties generated by certain models of reversible finite automata, Computing and Combinatorics, 83-93 (2006), Heidelberg: Springer, Heidelberg · Zbl 1162.68480 · doi:10.1007/11809678_11 |
| [12] | Klíma, O.; Polák, L., Syntactic structures of regular languages, Theoret. Comput. Sci., 800, 125-141 (2019) · Zbl 1436.68177 · doi:10.1016/j.tcs.2019.10.020 |
| [13] | Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings of the FOCS, pp. 66-75. IEEE (1997) |
| [14] | Markowsky, G., Free completely distributive lattices, Proc. Amer. Math. Soc., 74, 227-228 (1979) · Zbl 0377.06005 · doi:10.1090/S0002-9939-1979-0524290-9 |
| [15] | Milius, S.; Urbat, H.; Bojańczyk, M.; Simpson, A., Equational axiomatization of algebras with structure, Foundations of Software Science and Computation Structures, 400-417 (2019), Cham: Springer, Cham · Zbl 1524.08003 · doi:10.1007/978-3-030-17127-8_23 |
| [16] | Pin, JE, A variety theorem without complementation, Russ. Math., 39, 80-90 (1995) |
| [17] | Polák, L.; Sgall, J.; Pultr, A.; Kolman, P., Syntactic semiring of a language, Mathematical Foundations of Computer Science 2001, 611-620 (2001), Heidelberg: Springer, Heidelberg · Zbl 1005.68526 · doi:10.1007/3-540-44683-4_53 |
| [18] | Reiterman, J., The Birkhoff theorem for finite algebras, Algebra Universalis, 14, 1, 1-10 (1982) · Zbl 0484.08007 · doi:10.1007/BF02483902 |
| [19] | Salamanca, J.: Unveiling Eilenberg-type correspondences: Birkhoff’s theorem for (finite) algebras + duality (2017). https://arxiv.org/abs/1702.02822 |
| [20] | Schützenberger, MP, On finite monoids having only trivial subgroups, Inform. Control, 8, 2, 190-194 (1965) · Zbl 0131.02001 · doi:10.1016/S0019-9958(65)90108-7 |
| [21] | Urbat, H., Adámek, J., Chen, L.T., Milius, S.: Eilenberg theorems for free. In: Proceedings of the MFCS. LIPIcs, vol. 83, pp. 43:1-43:14 (2017) · Zbl 1441.68139 |
| [22] | Wilke, T.: An Eilenberg theorem for infinity-languages. In: Proceedings of the ICALP. LNCS, vol. 510, pp. 588-599. Springer, Heidelberg (1991) · Zbl 0766.68083 |
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.
