Edge Reduction for EVMDDs to Speed Up Analysis of Multi-State Systems
Abstract
This paper proposes a new reduction rule for edge-valued multi-valued decision diagrams (EVMDDs), which improves the speed of analysis of multi-state systems (MSSs). Existing reduction rules for decision diagrams remove redundant nodes, while the proposed rule removes redundant edges in EVMDDs. Since the time to do an analysis in an MSS depends on the number of edges in the EVMDD, the proposed rule is faster especially when used with edge minimization algorithms based on variable grouping. Experimental results show that the proposed rule reduces the number of edges by up to 30%, and this results in an analysis time that is reduced by up to 30%.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2015
- Accession Number
- ADA618846
Entities
People
- Jon T. Butler
- Mitchell A. Thornton
- Shinobu Nagayama
- Theodore W. Manikas
- Tsutomu Sasao
Organizations
- Naval Postgraduate School