Accession Number:

ADA618846

Title:

Edge Reduction for EVMDDs to Speed Up Analysis of Multi-State Systems

Descriptive Note:

Conference paper preprint

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Report Date:

2015-01-01

Pagination or Media Count:

7.0

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.

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware
  • Computer Systems Management and Standards

Distribution Statement:

APPROVED FOR PUBLIC RELEASE