Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies

DOI10.1051/ita:2002003zbMath1029.03027OpenAlexW2001338954MaRDI QIDQ4800264

Victor L. Selivanov

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

zbMATH Keywords

automata theorypolynomial-time hierarchycomplexity theoryStraubing hierarchyfine hierarchyleaf-languagesBrzozowski hierarchytyped Boolean hierarchy

Mathematics Subject Classification ID

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)

On the main scientific achievements of Victor Selivanov ⋮ FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ A reducibility for the dot-depth hierarchy

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