Unambiguous computations and locally definable acceptance types
From MaRDI portal
Publication:1127545
DOI10.1016/S0304-3975(97)00005-4zbMath0902.68079MaRDI QIDQ1127545
Peter Rossmanith, Rolf Niedermeier
Publication date: 13 August 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (3)
Languages polylog-time reducible to dot-depth 1/2 ⋮ Machines that can output empty words ⋮ On the probabilistic closure of the loose unambiguous hierarchy
Cites Work
- Robust machines accept easy sets
- Robust algorithms: a different approach to oracles
- On the construction of parallel computers from various basis of Boolean functions
- The complexity of combinatorial problems with succinct input representation
- Complexity classes without machines: on complete languages for UP
- A uniform approach to define complexity classes
- Using inductive counting to simulate nondeterministic computation
- Unambiguity of circuits
- Relative complexity of checking and evaluating
- Gap-definable counting classes
- Logspace and logtime leaf languages
- Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
- The complexity of promise problems with applications to public-key cryptography
- Complexity Measures for Public-Key Cryptosystems
- Alternation
- A survey of one-way functions in complexity theory
- Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
- Locally definable acceptance types for polynomial time machines
- Promise problems and access to unambiguous computation
- On the power of parity polynomial time
- Counting classes: Thresholds, parity, mods, and fewness
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Unambiguous computations and locally definable acceptance types
