Hierarchies and reducibilities on regular languages related to modulo counting
A.P. Ershov Institute of Informatics Systems,
Siberian Division of the Russian Academy of Sciences; email@example.com
Accepted: 27 November 2007
We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an application, we characterize the regular languages whose balanced leaf-language classes are contained in the polynomial hierarchy. For any discussed reducibility we try to give motivations and open questions, in a hope to convince the reader that the study of these reducibilities is interesting for automata theory and computational complexity.
Mathematics Subject Classification: 03D05 / 03C13 / 68Q15
Key words: Regular language / quasi-aperiodic regular language / quantifier-alternation hierarchy / difference hierarchy / polylogtime reducibility / quantifier-free reducibility / forbidden pattern.
© EDP Sciences, 2008