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 show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.
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...
We show that some natural refinements of the Straubing and Brzozowski
hierarchies correspond ( the so called leaf-languages) step by step to
similar refinements of the polynomial-time hierarchy. This extends a result of
Burtschik and Vollmer on relationship between the Straubing and the
polynomial hierarchies. In particular, this applies to the Boolean hierarchy
and the plus-hierarchy.
Download Results (CSV)