On balanced versus unbalanced computation trees

DOI10.1007/BF01192696zbMath0853.68097MaRDI QIDQ4887490

Heribert Vollmer, Ulrich Hertrampf, Klaus W. Wagner

Publication date: 5 August 1996

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

leaf languagesnondeterministic polynomial-time machinesPP computations

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

A characterization of the leaf language classes ⋮ Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies ⋮ Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Leaf languages and string compression ⋮ Unnamed Item ⋮ Dot operators ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Nondeterministic \(NC^1\) computation ⋮ LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY ⋮ SELF-SPECIFYING MACHINES ⋮ A reducibility for the dot-depth hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A uniform approach to define complexity classes
• Complete sets and the polynomial-time hierarchy
• Logspace and logtime leaf languages
• Complexity classes and sparse oracles
• Alternation
• Computational Complexity of Probabilistic Turing Machines

This page was built for publication: On balanced versus unbalanced computation trees