Page 1

Displaying 1 – 4 of 4

Showing per page

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.

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

Currently displaying 1 – 4 of 4

Page 1