DocumentCode :
2671393
Title :
Representations of Elementary Functions Using Edge-Valued MDDs
Author :
Nagayama, Shinobu ; Sasao, Tsutomu
Author_Institution :
Dept. of Comput. Eng., Hiroshima City Univ., Hiroshima
fYear :
2007
fDate :
13-16 May 2007
Firstpage :
5
Lastpage :
5
Abstract :
This paper proposes a method to represent elementary functions such as trigonometric, logarithmic, square root, and reciprocal functions using edge-valued multi-valued decision diagrams (EVMDDs). We introduce a new class of integer functions, Mp-monotone increasing functions, and derive an upper bound on the number of nodes in an edge-valued binary decision diagram (EVBDD) for the Mp-monotone increasing function. The upper bound shows that EVBDDs represent Mp-monotone increasing functions more compactly than other decision diagrams when p is small. Experimental results using 16-bit precision elementary functions show that: 1) standard elementary functions can be converted into Mp-monotone increasing functions with p = 1 or p = 2, or their linear transformations. And, they can be compactly represented by EVBDDs. 2) EVMDDs represent elementary functions with, on average, only 11% of the memory size needed for binary moment diagrams (BMDs), and only 69% of the memory size needed for EVBDDs.
Keywords :
binary decision diagrams; multivalued logic; Mp-monotone; binary moment diagrams; edge-valued MDD; elementary function representations; integer functions; multivalued decision diagrams; Arithmetic; Binary decision diagrams; Boolean functions; Computer science; Data structures; Input variables; Logic functions; Polynomials; Taylor series; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Multiple-Valued Logic, 2007. ISMVL 2007. 37th International Symposium on
Conference_Location :
Oslo
ISSN :
0195-623X
Print_ISBN :
0-7695-2831-7
Type :
conf
DOI :
10.1109/ISMVL.2007.49
Filename :
4215928
Link To Document :
بازگشت