Issue RAIRO-Theor. Inf. Appl. Volume 43, Number 1, January-March 2009 Page(s) 95 - 132 DOI 10.1051/ita:2007063 Published online 15 January 2008

RAIRO-Theor. Inf. Appl. 43, 95-132 (2009)
DOI: 10.1051/ita:2007063

Hierarchies and reducibilities on regular languages related to modulo counting

Victor L. Selivanov

A.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

What is OpenURL?