On the hierarchy of nondeterministic branching k-programs

DOI10.1007/BFB0036199MaRDI QIDQ5055950OpenAlexFDO

Authors Elizaveta Antonovna Okol'Nishnikova

Publication date 9 December 2022

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0036199

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Recommendations

• Comparing the sizes of nondeterministic branching read-k-times programs
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• A note on read-$k$ times branching programs
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
• scientific article; zbMATH DE number 1775455

Cites work

• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• scientific article; zbMATH DE number 4218008 (Why is no real title available?)
• scientific article; zbMATH DE number 3919835 (Why is no real title available?)
• A lower bound for read-once-only branching programs
• A note on read-$k$ times branching programs
• On lower bounds for read-\(k\)-times branching programs

Cited in

(8)

• scientific article; zbMATH DE number 1361505 (Why is no real title available?)
• scientific article; zbMATH DE number 1962822 (Why is no real title available?)
• Worst Case Branching and Other Measures of Nondeterminism
• The power of nondeterminism in polynomial-size bounded-width branching programs
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
• An improved hierarchy result for partitioned BDDs
• scientific article; zbMATH DE number 919281 (Why is no real title available?)
• scientific article; zbMATH DE number 4047115 (Why is no real title available?)

This page was built for publication: On the hierarchy of nondeterministic branching k-programs

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