EDP Sciences Journals List
Home Document
Subscriber Authentication Point
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?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.