Geodesic
Decidability of Hierarchies of Regular Aperiodic Languages
Algebra i logika, Tome 41 (2002) no. 5, pp. 610-631.

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

A new, logical approach is propounded to resolve the decidability problem for the hierarchies of Straubing and Brzozowski based on preservation theorems in model theory, a theorem of Higman, and the Rabin tree theorem. We thus manage to obtain purely logical, short proofs of some known decidability facts, which definitely may be of methodological interest. The given approach also applies in some other similar situations, for instance, to the hierarchies of formulas modulo a theory of linear orderings with finitely many unary predicates.
Keywords: decidability, Straubing hierarchy, Brzozowski hierarchy, preservation theorem, regular aperiodic language. 
@article{AL_2002_41_5_a5,
     author = {V. L. Selivanov},
     title = {Decidability of {Hierarchies} of {Regular} {Aperiodic} {Languages}},
     journal = {Algebra i logika},
     pages = {610--631},
     publisher = {mathdoc},
     volume = {41},
     number = {5},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2002_41_5_a5/}
}
TY  - JOUR
AU  - V. L. Selivanov
TI  - Decidability of Hierarchies of Regular Aperiodic Languages
JO  - Algebra i logika
PY  - 2002
SP  - 610
EP  - 631
VL  - 41
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2002_41_5_a5/
LA  - ru
ID  - AL_2002_41_5_a5
ER  - 
%0 Journal Article
%A V. L. Selivanov
%T Decidability of Hierarchies of Regular Aperiodic Languages
%J Algebra i logika
%D 2002
%P 610-631
%V 41
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2002_41_5_a5/
%G ru
%F AL_2002_41_5_a5
V. L. Selivanov. Decidability of Hierarchies of Regular Aperiodic Languages. Algebra i logika, Tome 41 (2002) no. 5, pp. 610-631. http://geodesic.mathdoc.fr/item/AL_2002_41_5_a5/

[1] J. E. Pin, Varieties of formal languages, Plenum, London, 1986 | MR | Zbl

[2] J. E. Pin, “Logic on words”, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 54 (1994), 145–165 | MR | Zbl

[3] D. Perrin, J. E. Pin, “First order logic and star-free sets”, J. Comput. Syst. Sci., 32 (1986), 393–406 | DOI | MR | Zbl

[4] W. Thomas, “Classifying regular events in symbolic logic”, J. Comput. Syst. Sci., 25 (1982), 360–376 | DOI | MR | Zbl

[5] A. I. Maltsev, Algebraicheskie sistemy, Nauka, M., 1970 | MR

[6] A. Robinson, Vvedenie v teoriyu modelei i metamatematiku algebry, Nauka, M., 1967 | MR | Zbl

[7] C. Choffrut, J. Karumäki, “Combinatorics of words”, Handbook of Formal Languages, v. 1, eds. G. Rozenberg, A. Salomaa, Springer, Berlin, 1996, 329–438 | MR

[8] R. McNaughton, S. Papert, Counter-free automata, MIT Press, Cambridge–Massachusets, 1971 | MR

[9] Dzh. Shenfild, Matematicheskaya logika, Nauka, M., 1975 | MR

[10] J. Addison, “The method of alternating chains”, The theory of models, North-Holland, Amsterdam, 1965, 1–16 | MR

[11] V. L. Selivanov, “Fine hierarchies and Boolean terms”, J. Symb. Log., 60:1 (1995), 289–317 | DOI | MR | Zbl

[12] V. L. Selivanov, “Tonkaya ierarkhiya formul”, Algebra i logika, 30:5 (1991), 568–583 | MR

[13] M. O. Rabin, “Decidability of second order theories and automata on infinite trees”, Trans. Am. Math. Soc., 141 (1969), 1–35 | DOI | MR | Zbl

[14] J. Stern, “Characterizations of some classes of regular events”, Theor. Comput. Sci., 35 (1985), 17–42 | DOI | MR | Zbl

[15] H. Schmitz, K. Wagner, The Boolean hierarchy over level 1/2 of the Straubing-Therien hierarchy, Technical Report 201, Inst. Inform., Univ. Wurzburg, 1998; http://www.informatik.uni-wuerzburg.de

[16] V. L. Selivanov, A logical approach to decidability of hierarchies of regular starfree languages, preprint No 68 of A. P. Ershov, Inst. Inform. Syst., 2000

[17] C. Glasser, H. Schmitz, “The Boolean structure of dot-depth one”, J. Autom. Lang. Comb., 6:4 (2001), 437–452 | MR | Zbl

[18] V. L. Selivanov, “Tonkaya ierarkhiya i opredelimye indeksnye mnozhestva”, Algebra i logika, 30:6 (1991), 705–725 | MR | Zbl

[19] V. L. Selivanov, “Computing degrees of definable classes of sentences”, Proceed. Intern. Conf. Algebra, part 3, Contemp. Math., 131, 1992, 657–666 | MR | Zbl