We describe Wadge degrees of -languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is where is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
We describe Wadge degrees of -languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is where is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
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 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.
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...
Page 1