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/