Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
Novosibirsk Pedagogical University,
28 Vilyniskaya Str., Novosibirsk 630126, Russia; email@example.com.
Accepted: 14 June 2002
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.
Mathematics Subject Classification: 03D05 / 03D15 / 03D55
© EDP Sciences, 2002