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.
Язык оригиналаанглийский
Страницы (с-по)29-42
Число страниц14
ЖурналRAIRO - Theoretical Informatics and Applications
Том36
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2002

ID: 127141153