A characterization of the leaf language classes

DOI10.1016/S0020-0190(97)00111-7zbMath1337.68110MaRDI QIDQ287160

Riccardo Silvestri, Bernd Borchert

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitytheory of computation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Dot operators ⋮ THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Succinctness as a source of complexity in logical formalisms

Cites Work

• On the theory of the PTIME degrees of the recursive sets
• Complexity classes without machines: on complete languages for UP
• On the relative complexity of hard problems for complexity classes without complete problems
• A uniform approach to define complexity classes
• Logspace and logtime leaf languages
• Complexity classes and sparse oracles
• Sublattices of the polynomial time degrees
• On the Structure of Polynomial Time Reducibility
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• On balanced versus unbalanced computation trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A characterization of the leaf language classes