Hierarchical Unambiguity
<|reference_start|>Hierarchical Unambiguity: We develop techniques to investigate relativized hierarchical unambiguous computation. We apply our techniques to generalize known constructs involving relativized unambiguity based complexity classes (UP and \mathcal{UP}) to new constructs involving arbitrary higher levels of the relativized unambiguous polynomial hierarchy (UPH). Our techniques are developed on constraints imposed by hierarchical arrangement of unambiguous nondeterministic polynomial-time Turing machines, and so they differ substantially, in applicability and in nature, from standard methods (such as the switching lemma [Hastad, Computational Limitations of Small-Depth Circuits, MIT Press, 1987]), which play roles in carrying out similar generalizations.   Aside from achieving these generalizations, we resolve a question posed by Cai, Hemachandra, and Vyskoc [J. Cai, L. Hemachandra, and J. Vyskoc, Promises and fault-tolerant database access, In K. Ambos-Spies, S. Homer, and U. Schoening, editors, Complexity Theory, pages 101-146. Cambridge University Press, 1993] on an issue related to nonadaptive Turing access to UP and adaptive smart Turing access to \mathcal{UP}.<|reference_end|>
@article{spakowski2007hierarchical,
    title={Hierarchical Unambiguity},
    author={Holger Spakowski and Rahul Tripathi},
    journal={arXiv preprint arXiv:cs/0702047},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0702047},
    primaryClass={cs.CC}
}