Currently displaying 1 – 6 of 6

Showing per page

Order by Relevance | Title | Year of publication

Wadge degrees of ω -languages of deterministic Turing machines

Victor Selivanov — 2003

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 ξ = ω 1 CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].

Wadge Degrees of -Languages of Deterministic Turing Machines

Victor Selivanov — 2010

RAIRO - Theoretical Informatics and Applications

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

Hierarchies and reducibilities on regular languages related to modulo counting

Victor L. Selivanov — 2009

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Relating automata-theoretic hierarchies to complexity-theoretic hierarchies

Victor L. Selivanov — 2002

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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.

Hierarchies and reducibilities on regular languages related to modulo counting

Victor L. Selivanov — 2008

RAIRO - Theoretical Informatics and Applications

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

Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies

Victor L. Selivanov — 2010

RAIRO - Theoretical Informatics and Applications

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.

Page 1

Download Results (CSV)