ROBDD as a recursively defined periodic bit-string

The paper describes bit-string interpretation of ROBDDs (Reduced Order BDDs). ROBDDs are viewed as recursively defined periodic bit-strings and BDD operations as recursively defined bitwise operations. Using the periodicity of bit-strings, we prove that the ROBDDs generated by rotating the bit-string of a ROBDD are mutually different. It implies not only the exponential BDD size but also more compact BDD representation. Also the interpretation can explain the hidden ideas of variable ordering.