Testing Computability by Width Two OBDDs

DOI10.1007/978-3-642-03685-9_51MaRDI QIDQ3638913zbMATH OpenOpenAlexFDO

Authors Dana Ron, Gilad Tsur

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_51

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Testing computability by width-two OBDDs
• On testing computability by small width OBDDs
• Testing computability by width-2 OBDDs where the variable order is unknown
• Lower Bounds for Testing Computability by Small Width OBDDs
• Computing the width of non-deterministic automata
• scientific article; zbMATH DE number 1500659
• Width hierarchy for \(k\)-OBDD of small width
• Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• scientific article; zbMATH DE number 1498463

Cited in

(11)

• On testing computability by small width OBDDs
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Fundamentals of Computation Theory
• Second-order finite automata
• Functions that have read‐twice constant width branching programs are not necessarily testable
• Lower Bounds for Testing Computability by Small Width OBDDs
• Functions that have read-once branching programs of quadratic size are not necessarily testable
• Property testing lower bounds via communication complexity
• Testing Membership in Languages that Have Small Width Branching Programs
• Testing computability by width-2 OBDDs where the variable order is unknown
• Testing computability by width-two OBDDs

This page was built for publication: Testing Computability by Width Two OBDDs

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