TY - JOUR

T1 - Hierarchies and reducibilities on regular languages related to modulo counting

AU - Selivanov, Victor L.

PY - 2009/1/1

Y1 - 2009/1/1

N2 - 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. © 2008 EDP Sciences.

AB - 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. © 2008 EDP Sciences.

KW - Difference hierarchy

KW - Forbidden pattern

KW - Polylogtime reducibility

KW - Quantifier-alternation hierarchy

KW - Quantifier-free reducibility

KW - Quasi-aperiodic regular language

KW - Regular language

UR - http://www.scopus.com/inward/record.url?scp=57249115800&partnerID=8YFLogxK

U2 - 10.1051/ita:2007063

DO - 10.1051/ita:2007063

M3 - Article

AN - SCOPUS:57249115800

VL - 43

SP - 95

EP - 132

JO - RAIRO - Theoretical Informatics and Applications

JF - RAIRO - Theoretical Informatics and Applications

SN - 0988-3754

IS - 1

ER -