Exponential space complexity for OBDD-based reachability analysis
type: Item
instance of: scholarly article
title: Exponential space complexity for OBDD-based reachability analysis
zbMATH Open document ID: 1379.68147
author: Beate Bollig
published in: Information Processing Letters
publication date: 2017-11-03T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6802633
zbMATH Keywords: computational complexity
zbMATH Keywords: lower bounds
zbMATH Keywords: ordered binary decision diagrams
zbMATH Keywords: reachability analysis
zbMATH Keywords: transitive closure
MaRDI profile type: Publication
full work available at URL: j.ipl.2010.07.022
OpenAlex ID: W2007609688
cites work: Graph-Based Algorithms for Boolean Function Manipulation
cites work: Q4471346
cites work: Symbolic graphs: Linear solutions to connectivity related problems
cites work: Q3352967
cites work: Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
cites work: SOFSEM 2004: Theory and Practice of Computer Science
cites work: SOFSEM 2005: Theory and Practice of Computer Science
cites work: Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
cites work: Reduction of OBDDs in linear time
cites work: Branching Programs and Binary Decision Diagrams
cites work: Symbolic topological sorting with OBDDs
DOI: 10.1016/J.IPL.2010.07.022
Recommended article: Symbolic OBDD-Based Reachability Analysis Needs Exponential Space
Recommended article: Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
Recommended article: Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
Recommended article: Q2754143
Recommended article: Q4972729
Recommended article: Space Complexity of Reachability Testing in Labelled Graphs
Recommended article: Space complexity of reachability testing in labelled graphs
Recommended article: The reachability problem for branching vector addition systems requires doubly-exponential space
Recommended article: On the quantifier-free dynamic complexity of reachability
Recommended article: On the Quantifier-Free Dynamic Complexity of Reachability
description: scientific article; zbMATH DE number 6802633