A Lower Bound on the Number of Variables to Represent Incompletely Specified Index Generation Functions
Tsutomu Sasao, Yuta Urano, Yukihiro Iguchi · 2014
Given an incompletely specified index generation function, the number of variables to represent the function can often be reduced by properly assigning don't care values. In this paper, we derive a lower bound on the number of variables necessary to represent a given incompletely specified index generation function. We also derive three properties of incompletely specified index generation functions. We confirm these properties by experiments using random index generation functions.