zbMATH — the first resource for mathematics

Decidability of hierarchies of regular aperiodic languages. (Russian, English) Zbl 1019.03028
Algebra Logika 41, No. 5, 610-631 (2002); translation in Algebra Logic 41, No. 5, 337-348 (2002).
For each hierarchy of regular languages, the following natural question can be asked: Given a class of such a hierarchy and a finite automaton uniformly effectively determined, is it true that the language defined by this automaton belongs to this class? The author proposes a logical approach to the study of such problems and proves it to be fruitful. Using this approach, he proves decidability for some classes of such problems.
03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
03D55 Hierarchies of computability and definability
03B25 Decidability of theories and sets of sentences
Full Text: Link EuDML