Edge-Shifted Decision Diagrams for Muptiple-Valued Logic
Abstract
Symbolic data structures for multi-valued logics are useful in a number
of applications, from model-checking to circuit design and switch-level
circuit verification. Such data structures are referred to as
decision diagrams, and are typically considered effective
if they are small, i.e., common co-factors of a function are shared,
and canonical, i.e., given a variable ordering, there is a unique
decision diagram representing this function.
In this paper we propose and evaluate a decision diagram variety,
called Edge-Shifted Decision Diagrams (ESDDs). These
diagrams are multi-valued, support structure sharing, and enjoy
canonicity.
We further list sufficient conditions to ensure canonicity of
decision diagrams with unary edge transformers.