HIERARCHIES AND REDUCTIBILITIES ON REGULAR LANGUAGES RELATED TO MODULO COUNTING

We discuss some known and introduce some new hierar-chies and reducibilities on regular languages, with the emphasis on thequantifier-alternation and difference hierarchies of the quasi-aperiodiclanguages. The non-collapse of these hierarchies and decidability ofsome levels are established. Complete sets in the levels of the hier-archies under the polylogtime and some quantifier-free reducibilitiesare found. Some facts about the corresponding degree structures areestablished. As an application, we characterize the regular languageswhose balanced leaf-language classes are contained in the polynomialhierarchy. For any discussed reducibility we try to give motivationsand open questions, in a hope to convince the reader that the studyof these reducibilities is interesting for automata theory and computa-tional complexity