Unambiguous computations and locally definable acceptance types

DOI10.1016/S0304-3975(97)00005-4zbMATH Open0902.68079MaRDI QIDQ1127545FDOQ1127545

Authors: Rolf Niedermeier, Peter Rossmanith 

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 512853
• Locally definable acceptance types for polynomial time machines
• Promise problems and access to unambiguous computation
• Hierarchical Unambiguity

zbMATH Keywords

structural complexitycomputation treesunambiguous computation

Mathematics Subject Classification ID

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

Cites Work

• A uniform approach to define complexity classes
• Alternation
• Robust algorithms: a different approach to oracles
• Complexity classes without machines: on complete languages for UP
• Logspace and logtime leaf languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of combinatorial problems with succinct input representation
• Complexity Measures for Public-Key Cryptosystems
• A survey of one-way functions in complexity theory
• The complexity of promise problems with applications to public-key cryptography
• Relative complexity of checking and evaluating
• Title not available (Why is that?)
• On the construction of parallel computers from various basis of Boolean functions
• Gap-definable counting classes
• On the power of parity polynomial time
• Counting classes: Thresholds, parity, mods, and fewness
• Robust machines accept easy sets
• Using inductive counting to simulate nondeterministic computation
• Unambiguity of circuits
• Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
• Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
• Title not available (Why is that?)
• Locally definable acceptance types for polynomial time machines
• Promise problems and access to unambiguous computation

Cited In (8)

• Locally definable acceptance types for polynomial time machines
• Promise problems and access to unambiguous computation
• On the probabilistic closure of the loose unambiguous hierarchy
• On the power of unambiguity in alternating machines
• Languages polylog-time reducible to dot-depth 1/2
• Machines that can output empty words
• Fundamentals of Computation Theory
• Title not available (Why is that?)

This page was built for publication: Unambiguous computations and locally definable acceptance types

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127545)