Document RAIRO-Theor. Inf. Appl. (2008)
DOI: 10.1051/ita:2007063
Hierarchies and reducibilities on regular languages related to modulo counting
Victor L. SelivanovA.P. Ershov Institute of Informatics Systems, Siberian Division of the Russian Academy of Sciences; vseliv@nspu.ru
(Received March 26, 2006. Accepted November 27, 2007. Published online 15 January 2008.)
Abstract
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