Geodesic
Boolean algebras of regular languages
Algebra i logika, Tome 52 (2013) no. 6, pp. 676-711.

Voir la notice de l'article provenant de la source Math-Net.Ru

Some of the Boolean algebras of regular languages of finite and infinite words are characterized up to isomorphism. It is shown that classes of regular languages related to such characterizations are decidable.
Keywords: Boolean algebra, Frechet ideal, regular language, aperiodic language, quasiaperiodic language, $d$-quasiaperiodic language, $\omega$-regular language, $\omega$-aperiodic language. 
@article{AL_2013_52_6_a2,
     author = {A. S. Konovalov and V. L. Selivanov},
     title = {Boolean algebras of regular languages},
     journal = {Algebra i logika},
     pages = {676--711},
     publisher = {mathdoc},
     volume = {52},
     number = {6},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2013_52_6_a2/}
}
TY  - JOUR
AU  - A. S. Konovalov
AU  - V. L. Selivanov
TI  - Boolean algebras of regular languages
JO  - Algebra i logika
PY  - 2013
SP  - 676
EP  - 711
VL  - 52
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2013_52_6_a2/
LA  - ru
ID  - AL_2013_52_6_a2
ER  - 
%0 Journal Article
%A A. S. Konovalov
%A V. L. Selivanov
%T Boolean algebras of regular languages
%J Algebra i logika
%D 2013
%P 676-711
%V 52
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2013_52_6_a2/
%G ru
%F AL_2013_52_6_a2
A. S. Konovalov; V. L. Selivanov. Boolean algebras of regular languages. Algebra i logika, Tome 52 (2013) no. 6, pp. 676-711. http://geodesic.mathdoc.fr/item/AL_2013_52_6_a2/

[1] W. Hanf, “The boolean algebra of logic”, Bull. Am. Math. Soc., 81:4 (1975), 456–502 | MR

[2] S. Lempp, M. Peretyatkin, R. Solomon, “The Lindenbaum algebra of the theory of the class of all finite models”, J. Math. Log., 2:2 (2002), 145–225 | DOI | MR | Zbl

[3] V. L. Selivanov, “Universalnye bulevy algebry i ikh primeneniya”, Tez. dokl. Mezhd. konf. po algebre, Novosibirsk, 1991, 127

[4] V. L. Selivanov, Hierarchies, numerations, index sets, Handwritten notes, 1992

[5] V. L. Selivanov, “Positive structures”, Computability and models, perspectives East and West, eds. S. B. Cooper, S. S. Goncharov, Kluwer Academic/ Plenum Publishers, New York, 2003, 321–350 | DOI | MR

[6] V. Selivanov, A. Konovalov, “Boolean algebras of regular languages”, Developments in language theory, Proc. 15th int. conf. DLT 2011 (Milan, Italy, July 19–22, 2011), Lect. Notes Comput. Sci., 6795, eds. G. Mauri et al., Springer-Verlag, Berlin, 2011, 386–396 | DOI | MR | Zbl

[7] C. Marini, G. Simi, A. Sorbi, M. Sorrentino, “A note on algebras of languages”, Theor. Comput. Sci., 412:46 (2011), 6531–6536 | DOI | MR | Zbl

[8] N. Pippenger, “Regular languages and Stone duality”, Theory Comput. Syst., 30:2 (1997), 121–134 | DOI | MR | Zbl

[9] M. Gehrke, S. Grigorieff, J.-E. Pin, “Duality and equational theory of regular languages”, Automata, languages and programming, Proc. 35th int. colloq. ICALP 2008 (Reykjavik, Iceland, July 7–11, 2008), Part II, Lect. Notes Comput. Sci., 5126, eds. L. Aceto et al., Springer-Verlag, Berlin, 2008, 246–257 | DOI | MR | Zbl

[10] S. S. Goncharov, Schetnye bulevy algebry i razreshimost, Sibirskaya shkola algebry i logiki, Nauchnaya kniga (NII MIOO NGU), Novosibirsk, 1996 | MR | Zbl

[11] A. Szilard, S. Yu, K. Zhang, J. Shallit, “Characterizing regular languages with polynomial densities”, Proc. MFCS, Lect. Notes Comput. Sci., 629, 1992, 494–503 | DOI | MR

[12] S. Yu, “Regular languages”, Handbook of formal languages, v. 1, eds. G. Rozenberg, A. Salomaa, Springer-Verlag, Berlin, 1997, 41–110 | MR

[13] J.-E. Pin, Unpublished manuscript on regular languages

[14] V. Selivanov, A. Konovalov, “Boolean algebras of regular $\omega$-languages”, Language and automata theory and applications, Proc. 7th int. conf. LATA 2013 (Bilbao, Spain, April 2–5, 2013), Lect. Notes Comput. Sci., 7810, eds. A.-H. Dediu et al., Springer-Verlag, Berlin, 2013, 504–515 | DOI | MR | Zbl

[15] R. Sikorskii, Bulevy algebry, Mir, M., 1969 | MR

[16] J. Ketonen, “The structure of countable Boolean algebras”, Ann. Math. (2), 108 (1978), 41–89 | DOI | MR | Zbl

[17] Yu. L. Ershov, “Distributivnye reshetki s otnositelnymi dopolneniyami”, Algebra i logika, 18:6 (1979), 680–722 | MR

[18] H. Straubing, Finite automata, formal logic and circuit complexity, Prog. Theor. Comput. Sci., Birkhäuser, Basel, 1994 | MR | Zbl

[19] D. Perrin, J.-E. Pin, Infinite words. Automata, semigroups, logic and games, Pure Appl. Math. (Amsterdam), 141, Elsevier/ Academic Press, Amsterdam, 2004 | Zbl

[20] W. Thomas, “Languages, automata and logic”, Handbook of formal languages, v. 3, eds. G. Rozenberg, A. Salomaa, Springer-Verlag, Berlin, 1997, 133–191 | MR

[21] R. McNaughton, S. Papert, Counter-free automata, Res. Monogr., 65, The M.I.T. Press, Cambridge, Massachusetts–London, England, 1971 | MR | Zbl

[22] V. L. Selivanov, “Hierarchies and reducibilities on regular languages related to modulo counting”, Theor. Inform. Appl., 43:1 (2009), 95–132 | DOI | MR | Zbl

[23] V. Diekert, P. Gastin, “First-order definable languages”, Logic and automata. History and perspectives, Dedicated to Wolfgang Thomas on the occasion of his sixtieth birthday, Texts Log. Games, 2, eds. J. Flum et al., Amsterdam Univ. Press, Amsterdam, 2008, 261–306 | MR | Zbl

[24] Z. Wu, “Quasi-star-free languages on infinite words”, Acta Cybern., 17:1 (2005), 107–121 | MR | Zbl

[25] V. L. Selivanov, “Fine hierarchy of regular aperiodic $\omega$-languages”, Int. J. Found. Comput. Sci., 19:3 (2008), 649–675 | DOI | MR | Zbl

[26] C. Choffrut, J. Karhumäki, “Combinatorics of words”, Handbook of formal languages, v. 1, eds. G. Rozenberg, A. Salomaa, Springer-Verlag, Berlin, 1997, 329–438 | DOI | MR

[27] R. C. Lyndon, M. P. Schützenberger, “The equation $a^M=b^Nc^P$ in a free group”, Mich. Math. J., 9 (1962), 289–298 | DOI | MR | Zbl

[28] K. Wagner, “On $\omega$-regular sets”, Inf. Control, 43 (1979), 123–177 | DOI | MR | Zbl