Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
DOI10.1051/ita:2002003zbMath1029.03027OpenAlexW2001338954MaRDI QIDQ4800264
Publication date: 15 July 2003
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2002__36_1_29_0
automata theorypolynomial-time hierarchycomplexity theoryStraubing hierarchyfine hierarchyleaf-languagesBrzozowski hierarchytyped Boolean hierarchy
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Hierarchies of computability and definability (03D55)
Related Items (5)
Cites Work
- On the acceptance power of regular languages
- First-order logic and star-free sets
- Classifying regular events in symbolic logic
- A uniform approach to define complexity classes
- The dot-depth hierarchy of star-free languages is infinite
- Polynomial closure and unambiguous product
- Logspace and logtime leaf languages
- The difference and truth-table hierarchies for NP
- A Downward Collapse within the Polynomial Hierarchy
- RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
- On Existentially First-Order Definable Languages and Their Relation to NP
- Fine hierarchies and Boolean terms
- On balanced versus unbalanced computation trees
- LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies