Exponential space complexity for OBDD-based reachability analysis

DOI10.1016/J.IPL.2010.07.022MaRDI QIDQ1675755zbMATH OpenOpenAlexFDO

Authors Beate Bollig

Publication date 3 November 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.07.022

zbMATH Keywords

computational complexitylower boundstransitive closurereachability analysisordered binary decision diagrams

Mathematics Subject Classification ID

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

Recommendations

• Symbolic OBDD-based reachability analysis needs exponential space
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• scientific article; zbMATH DE number 1670823
• The parameterized space complexity of model-checking bounded variable first-order logic
• Space Complexity of Reachability Testing in Labelled Graphs
• Space complexity of reachability testing in labelled graphs
• The reachability problem for branching vector addition systems requires doubly-exponential space
• On the quantifier-free dynamic complexity of reachability
• On the Quantifier-Free Dynamic Complexity of Reachability

Cites work

• scientific article; zbMATH DE number 4204283 (Why is no real title available?)
• scientific article; zbMATH DE number 2079387 (Why is no real title available?)
• Branching Programs and Binary Decision Diagrams
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Graph-Based Algorithms for Boolean Function Manipulation
• Reduction of OBDDs in linear time
• SOFSEM 2004: Theory and Practice of Computer Science
• SOFSEM 2005: Theory and Practice of Computer Science
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• Symbolic graphs: Linear solutions to connectivity related problems
• Symbolic topological sorting with OBDDs

Cited in

(7)

• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• On efficient implicit OBDD-based algorithms for maximal matchings
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• Symbolic OBDD-based reachability analysis needs exponential space
• Priority functions for the approximation of the metric TSP

This page was built for publication: Exponential space complexity for OBDD-based reachability analysis

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