Read-once projections and formal circuit verification with binary decision diagrams

DOI10.1007/3-540-60922-9_40MaRDI QIDQ4593955zbMATH OpenOpenAlexFDO

Authors Beate Bollig, Ingo Wegener

Publication date 16 November 2017

Published in STACS 96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60922-9_40

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Completeness and non-completeness results with respect to read-once projections
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• On the complexity of randomized read-once branching programs
• scientific article; zbMATH DE number 1390338
• scientific article; zbMATH DE number 1506311

Cited in

(5)

• Completeness and non-completeness results with respect to read-once projections
• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• Approximating Boolean functions by OBDDs

This page was built for publication: Read-once projections and formal circuit verification with binary decision diagrams

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