Name
Abstract | ||
|---|---|---|
This paper analyzes complexities of decision diagrams for elementary functions such as polynomial, trigonometric, logarithmic, square root, and reciprocal functions. These real functions are converted into integer-valued functions by using fixed-point representation. This paper presents the numbers of nodes in decision diagrams representing the integer-valued functions. First, complexities of decision diagrams for polynomial functions are analyzed, since elementary functions can be approximated by polynomial functions. A theoretical analysis shows that binary moment diagrams (BMDs) have low complexity for polynomial functions. Second, this paper analyzes complexity of edge-valued binary decision diagrams (EVBDDs) for monotone functions, since many common elementary functions are monotone. It introduces a new class of integer functions, Mp-monotone increasing function, and derives an upper bound on the number of nodes in an EVBDD for the Mp-monotone increasing function. A theoretical analysis shows that EVBDDs have low complexity for Mp-monotone increasing functions. This paper also presents the exact number of nodes in the smallest EVBDD for the n-bit multiplier function, and a variable order for the smallest EVBDD. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/TC.2008.134 | Computers, IEEE Transactions |
Keywords | Field | DocType |
decision diagrams,graph theory,polynomials,binary moment diagram,edge-valued binary decision diagram,elementary function,fixed-point representation,graph-based representation,integer-valued function,monotone function,polynomial function,Decision Diagrams,Elementary function approximation,General,Representations,Trees | Boolean function,μ-recursive function,Discrete mathematics,Addition theorem,Polynomial,Algebra,Elementary function,Binary decision diagram,Complex-valued function,Monotone polygon,Mathematics | Journal |
Volume | Issue | ISSN |
58 | 1 | 0018-9340 |
Citations | PageRank | References |
12 | 0.64 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shinobu Nagayama | 1 | 218 | 25.30 |
| Tsutomu Sasao | 2 | 1083 | 141.62 |