Symbolic OBDD-based reachability analysis needs exponential space

DOI10.1007/978-3-642-11266-9_19zbMATH Open1274.68087OpenAlexW1578551036MaRDI QIDQ3401094FDOQ3401094

Authors: Beate Bollig 

Publication date: 28 January 2010

Published in: SOFSEM 2010: Theory and Practice of Computer Science (Search for Journal in Brave)

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

Recommendations

• Exponential space complexity for OBDD-based reachability analysis
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• A larger lower bound on the OBDD complexity of the most significant bit of multiplication
• SOFSEM 2005: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 1351076

zbMATH Keywords

computational complexitylower boundstransitive closurereachability analysisordered binary decision diagrams

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (8)

• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Mathematical Foundations of Computer Science 2003
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• SOFSEM 2006: Theory and Practice of Computer Science
• Exponential space complexity for OBDD-based reachability analysis
• Graph-Theoretic Concepts in Computer Science
• Symbolic topological sorting with OBDDs
• Symbolic graphs: Linear solutions to connectivity related problems

This page was built for publication: Symbolic OBDD-based reachability analysis needs exponential space

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