On the hierarchy of nondeterministic branching k-programs

DOI10.1007/BFB0036199OpenAlexW1575676006MaRDI QIDQ5055950FDOQ5055950

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

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

Mathematics Subject Classification ID

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

Cites Work

• A lower bound for read-once-only branching programs
• On lower bounds for read-\(k\)-times branching programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on read-$k$ times branching programs
• Title not available (Why is that?)

Cited In (8)

• Title not available (Why is that?)
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
• Worst Case Branching and Other Measures of Nondeterminism
• Title not available (Why is that?)
• An improved hierarchy result for partitioned BDDs
• The power of nondeterminism in polynomial-size bounded-width branching programs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)