DOI

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.
Original languageEnglish
Pages (from-to)29-42
Number of pages14
JournalRAIRO - Theoretical Informatics and Applications
Volume36
Issue number1
DOIs
StatePublished - 1 Jan 2002

ID: 127141153