×

Stone duality, topological algebra, and recognition. (English) Zbl 1339.06012

Working in the framework of extended Priestley duality for distributive lattices with additional operations, a first main result of the paper under review is that any topological algebra over a Boolean space is the extended Stone dual space of some Boolean algebra with additional operations. As a corollary, the profinite completion of any abstract algebra is the extended Stone dual space of the Boolean algebra of recognisable subsets of the abstract algebra endowed with suitable residuation operations. In particular, the fact that the profinite completion of the free monoid on a finite set of generators is the dual space of a Boolean algebra with additional operations based on the recognisable subsets of the free monoid underlies a number of recent results in automata theory including a generalisation of Eilenberg-Reiterman theory for regular languages, and a notion of compact recognition that finds applications to non-regular languages.

MSC:

06D50 Lattices and duality
06E15 Stone spaces (Boolean spaces) and related structures
20M35 Semigroups in automata theory, linguistics, etc.
22A30 Other topological algebraic systems and their representations
68Q70 Algebraic theory of languages and automata
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramsky, S., Domain theory in logical form, Ann. Pure Appl. Logic, 51, 1-2, 1-77 (1991) · Zbl 0737.03006
[2] Almeida, J., Finite Semigroups and Universal Algebra (1994), World Scientific: World Scientific Singapore
[3] Almeida, J., Profinite semigroups and applications, (Structural Theory of Automata, Semigroups, and Universal Algebra. Structural Theory of Automata, Semigroups, and Universal Algebra, NATO Sci. Ser. II Math. Phys. Chem., vol. 207 (2005), Springer: Springer Dordrecht), 1-45, Notes taken by Alfredo Costa · Zbl 1109.20050
[4] Ballester-Bolinches, A.; Pin, J.-É.; Soler-Escrivà, X., Formations of finite monoids and formal languages: Eilenberg’s variety theorem revisited, Forum Math., 26, 1737-1761 (2014) · Zbl 1310.20054
[5] Berstel, J.; Boasson, L.; Carton, O.; Petazzoni, B.; Pin, J.-É., Operations preserving recognizable languages, Theor. Comput. Sci., 354, 405-420 (2006) · Zbl 1088.68086
[6] Bezhanishvili, G.; Jansana, R., Priestley style duality for distributive meet-semilattices, Stud. Log., 98, 83-123 (2011) · Zbl 1238.03050
[7] Bezhanishvili, N.; Kupke, C.; Panangaden, P., Minimization via duality, (Ong, L.; Queiroz, R., Logic, Language, Information and Computation. Logic, Language, Information and Computation, Lect. Notes Comput. Sci., vol. 7456 (2012), Springer: Springer Berlin, Heidelberg), 191-205 · Zbl 1361.68157
[8] Birkhoff, G., Moore-Smith convergence in general topology, Ann. Math., 38, 39-56 (1937) · JFM 63.0567.06
[9] Birkhoff, G., Lattice Theory, Colloq. Publ. - Am. Math. Soc., vol. 25 (1979), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0126.03801
[10] Bojanczyk, M., Data monoids, (Schwentick, T.; Dürr, C., STACS. STACS, LIPIcs, vol. 9 (2011), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 105-116 · Zbl 1230.68146
[11] Bonchi, F.; Bonsangue, M.; Hansen, H.; Panangaden, P.; Rutten, J.; Silva, A., Algebra-coalgebra duality in Brzozowski’s minimization algorithm, ACM Trans. Comput. Log., 15, 3:1-3:29 (2014) · Zbl 1288.68174
[12] Borceux, F., Handbook of Categorical Algebra, vol. 1 (1994), Cambridge University Press, Cambridge Books Online
[13] Bourbaki, N., General Topology: Chapters 1-4, Elements of Mathematics (1998), Springer-Verlag: Springer-Verlag Berlin · Zbl 0894.54001
[14] Branco, M. J.; Pin, J.-É., Equations defining the polynomial closure of a lattice of regular languages, (Albers, S.; Marchetti-Spaccamela, A.; Matias, Y.; Nikoletseas, S.; Thomas, W., Automata, Languages and Programming. Automata, Languages and Programming, Lect. Notes Comput. Sci., vol. 5556 (2009), Springer: Springer Berlin, Heidelberg), 115-126 · Zbl 1248.68340
[15] Büchi, R., On a decision method in restricted second order arithmetic, (Proceedings of the International Congress on Logic, Methodology and Philosophy of Science (1962), Stanford University Press), 1-11 · Zbl 0147.25103
[16] Colcombet, T., The theory of stabilisation monoids and regular cost functions, (Albers, S.; Marchetti-Spaccamela, A.; Matias, Y.; Nikoletseas, S. E.; Thomas, W., ICALP (2). ICALP (2), Lect. Notes Comput. Sci., vol. 5556 (2009), Springer), 139-150 · Zbl 1248.68291
[17] Crawley, P.; Dilworth, R. P., Algebraic Theory of Lattices (1973), Prentice Hall · Zbl 0494.06001
[18] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (2002), Cambridge University Press · Zbl 1002.06001
[19] Dekkers, M., Stone duality: an application in the theory of formal languages (December 2008), Radboud Universiteit Nijmegen: Radboud Universiteit Nijmegen Netherlands, Master’s thesis
[20] Doner, J. E., Tree acceptors and some of their applications, J. Comput. Syst. Sci., 4, 406-451 (1970) · Zbl 0212.02901
[21] Esakia, L., Topological Kripke models, Sov. Math. Dokl., 15, 147-151 (1974) · Zbl 0296.02030
[22] Ésik, Z., Extended temporal logic on finite words and wreath products of monoids with distinguished generators, (Masami, Ito; etal., Developments in Language Theory. 6th International Conference, DLT 2002. Developments in Language Theory. 6th International Conference, DLT 2002, Kyoto, Japan, September 18-21. Developments in Language Theory. 6th International Conference, DLT 2002. Developments in Language Theory. 6th International Conference, DLT 2002, Kyoto, Japan, September 18-21, Lect. Notes Comput. Sci., vol. 2450 (2002), Springer: Springer Berlin), 43-58 · Zbl 1015.03025
[23] Gehrke, M., Stone duality and the recognisable languages over an algebra, (Kurz, A.; Lenisa, M.; Tarlecki, A., Algebra and Coalgebra in Computer Science. Algebra and Coalgebra in Computer Science, CALCO 2009. Algebra and Coalgebra in Computer Science. Algebra and Coalgebra in Computer Science, CALCO 2009, Lect. Notes Comput. Sci., vol. 5728 (2009), Springer: Springer Berlin), 236-250 · Zbl 1239.68047
[24] Gehrke, M., Duality and recognition, (Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, MFCS 2011. Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, MFCS 2011, Lect. Notes Comput. Sci., vol. 6907 (2011), Springer: Springer Berlin), 3-18 · Zbl 1343.68158
[25] Gehrke, M., Canonical extensions, Esakia spaces, and universal models, (Bezhanishvili, G., Leo Esakia on Duality in Modal and Intuitionistic Logics. Leo Esakia on Duality in Modal and Intuitionistic Logics, Outst. Contrib. Log., vol. 4 (2014), Springer: Springer Netherlands), 9-41 · Zbl 1350.03050
[26] Gehrke, M.; Grigorieff, S.; Pin, J.-É., Duality and Theory of Regular Languages, Lect. Notes Comput. Sci., vol. 5125, 246-257 (2008) · Zbl 1165.68049
[27] Gehrke, M.; Grigorieff, S.; Pin, J.-É., A topological approach to recognition, (Abramsky, S.; etal., ICALP 2010, Part II. ICALP 2010, Part II, Lect. Notes Comput. Sci., vol. 6199 (2010), Springer: Springer Berlin), 151-162 · Zbl 1288.68176
[28] Gehrke, M.; Jónsson, B., Bounded distributive lattices expansions, Math. Scand., 94, 2, 13-45 (2004) · Zbl 1077.06008
[29] Gehrke, M.; Priestley, H. A., Canonical extensions of double quasioperator algebras: an algebraic perspective on duality for certain algebras with binary operations, J. Pure Appl. Algebra, 209, 269-290 (2007) · Zbl 1110.06015
[30] Gehrke, M.; Priestley, H. A., Duality for quasioperator algebras via their canonical extensions, Stud. Log., 86, 31-68 (2007) · Zbl 1127.06009
[31] Goldblatt, R., Varieties of complex algebras, Ann. Pure Appl. Logic, 44, 173-242 (1989) · Zbl 0722.08005
[32] Hall, M., A topology for free groups and related groups, Ann. Math., 52, 127-139 (1950) · Zbl 0045.31204
[33] Hofmann, D., The enriched Vietoris monad on representable spaces, J. Pure Appl. Algebra, 218, 12, 2274-2318 (2014) · Zbl 1315.18007
[34] Jónsson, B.; Tarski, A., Boolean algebras with operators I, Am. J. Math., 73, 891-939 (1951) · Zbl 0045.31505
[35] Jónsson, B.; Tarski, A., Boolean algebras with operators II, Am. J. Math., 74, 127-162 (1952) · Zbl 0045.31601
[36] Kleene, S. C., Representation of events in nerve nets and finite automata, Automata Studies, 3-42 (1956)
[37] Kufleitner, M.; Lauser, A., Around dot-depth one, Int. J. Found. Comput. Sci., 23, 6, 1323-1340 (2012) · Zbl 1308.68071
[38] Kunc, M., Equational description of pseudovarieties of homomorphisms, Inform. Théor. Appl., 37, 243-254 (2003) · Zbl 1045.20049
[39] Mezei, J.; Wright, J. B., Algebraic automata and context-free sets, Inf. Control, 11, 3-29 (1967) · Zbl 0155.34301
[40] Nielsen, M.; Plotkin, G.; Winskel, G., Petri nets, event structures and domains, part 1, Theor. Comput. Sci., 13, 85-108 (1981) · Zbl 0452.68067
[41] Pin, J.-É., On reversible automata, (Proceedings of the First LATIN Conference. Proceedings of the First LATIN Conference, Saõ Paulo. Proceedings of the First LATIN Conference. Proceedings of the First LATIN Conference, Saõ Paulo, Lect. Notes Comput. Sci., vol. 583 (1992)), 401-416
[42] Pin, J.-É., A variety theorem without complementation, Russ. Math. (Iz. VUZ), 39, 80-90 (1995)
[43] Pin, J.-É., Profinite methods in automata theory, (Albers; Marion, STACS 2009. STACS 2009, LIPIcs. Leibniz Int. Proc. Inform., vol. 3 (2009), Schloss Dagstuhl), 31-50 · Zbl 1236.68175
[44] Pin, J.-É., Equational descriptions of languages, Int. J. Found. Comput. Sci., 23, 1227-1240 (2012) · Zbl 1283.68224
[45] Pin, J.-É.; Weil, P., A Reiterman theorem for pseudovarieties of finite first-order structures, Algebra Univers., 35, 577-595 (1996) · Zbl 0864.03024
[46] Pippenger, N., Regular languages and stone duality, Theory Comput. Syst., 30, 2, 121-134 (1997) · Zbl 0870.68092
[47] Polák, L., On varieties, generalized varieties and pseudovarieties of homomorphisms, (Contributions to General Algebra, vol. 16 (2005), Heyn: Heyn Klagenfurt), 173-188 · Zbl 1080.08007
[48] Priestley, H. A., Representation of distributive lattices by means of ordered stone spaces, Bull. Lond. Math. Soc., 2, 186-190 (1970) · Zbl 0201.01802
[49] Rabin, M. O., Decidability of second-order theories and automata on infinite trees, Trans. Am. Math. Soc., 141, 1-35 (1969) · Zbl 0221.02031
[50] Raney, G. N., Completely distributive complete lattices, Proc. Am. Math. Soc., 3, 677-680 (1952) · Zbl 0049.30304
[51] Reiterman, J., The Birkhoff theorem for finite algebras, Algebra Univers., 14, 1, 1-10 (1982) · Zbl 0484.08007
[52] Rhodes, J.; Steinberg, B., The q-Theory of Finite Semigroups, Springer Monogr. Math. (2008), Springer
[53] Schmid, J., Quasiorders and sublattices of distributive lattices, Order, 19, 11-34 (2002) · Zbl 1006.06006
[54] Selivanov, V.; Konovalov, A., Boolean algebras of regular languages, (Proceedings of the 15th International Conference on Developments in Language Theory. Proceedings of the 15th International Conference on Developments in Language Theory, DLT’11 (2011), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 386-396 · Zbl 1221.68144
[55] Stone, M. H., The theory of representations for Boolean algebras, Trans. Am. Math. Soc., 40, 37-111 (1936) · JFM 62.0033.04
[56] Stone, M. H., Topological representations of distributive lattices and Brouwerian logics, Çasopis Pȩst. Math. Fys., 67, 1-25 (1937) · JFM 63.0830.01
[57] Straubing, H., On logical descriptions of regular languages, (LATIN 2002. LATIN 2002, Lect. Notes Comput. Sci., vol. 2286 (2002), Springer: Springer Berlin), 528-538 · Zbl 1059.03034
[58] Stubbe, I., An introduction to quantaloid-enriched categories, Fuzzy Sets Syst., 256, 95-116 (2014), Special Issue on Enriched Category Theory and Related Topics (selected papers from the 33rd Linz Seminar on Fuzzy Set Theory, 2012) · Zbl 1335.18002
[59] Thatcher, J. W.; Wright, J. B., Generalized finite automata theory with an application to a decision problem of second-order logic, Math. Syst. Theory, 2, 1, 57-81 (1968) · Zbl 0157.02201
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.