Birkmann F, Milius S, Urbat H (2021)
Publication Type: Conference contribution
Publication year: 2021
Publisher: Springer Science and Business Media Deutschland GmbH
Book Volume: 12638 LNCS
Pages Range: 3-15
Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Event location: Milan, ITA
ISBN: 9783030681944
DOI: 10.1007/978-3-030-68195-1_1
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.
APA:
Birkmann, F., Milius, S., & Urbat, H. (2021). On Language Varieties Without Boolean Operations. In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 3-15). Milan, ITA: Springer Science and Business Media Deutschland GmbH.
MLA:
Birkmann, Fabian, Stefan Milius, and Henning Urbat. "On Language Varieties Without Boolean Operations." Proceedings of the 15th International Conference on Language and Automata Theory and Applications, LATA 2021, Milan, ITA Ed. Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron, Springer Science and Business Media Deutschland GmbH, 2021. 3-15.
BibTeX: Download