A Dynamic Programming Based Method for Optimum Linear Decomposition of Index Generation Functions

Shinobu Nagayama, Tsutomu Sasao, Jon T. Butler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

The problem addressed in this paper is minimization of the number of linear functions in a linear decomposition. This paper proposes an exact minimization method based on dynamic programming for index generation functions. The proposed method searches for an optimum solution while recursively dividing an index set of a given index generation function. To use partial solutions efficiently in solution search, the proposed method represents partitions of an index set compactly and uniquely by zero-suppressed binary decision diagrams (ZDDs). Existing methods based on a branch-and-bound approach search for a solution sequentially in a depth-first manner. On the other hand, the proposed method searches for multiple partial solutions in parallel in a breadth-first manner. Thus, once a solution is found, we can terminate the search process. This is because the depth of searches corresponds to the number of linear functions. Experimental results using benchmark index generation functions show the effectiveness of the proposed method.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 49th International Symposium on Multiple-Valued Logic, ISMVL 2019
PublisherIEEE Computer Society
Pages144-149
Number of pages6
ISBN (Electronic)9781728100913
DOIs
Publication statusPublished - 1 May 2019
Event49th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2019 - Fredericton, Canada
Duration: 21 May 201923 May 2019

Publication series

NameProceedings of The International Symposium on Multiple-Valued Logic
Volume2019-May
ISSN (Print)0195-623X

Conference

Conference49th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2019
CountryCanada
CityFredericton
Period21/05/1923/05/19

Fingerprint

Dynamic programming
Dynamic Programming
Decomposition
Decompose
Search Methods
Linear Function
Partial
Decision Diagrams
Breadth
Binary decision diagrams
Branch-and-bound
Terminate
Partition
Binary
Benchmark
Zero
Experimental Results

Keywords

  • Index generation functions
  • dynamic programming method
  • functional decomposition
  • linear decomposition
  • logic design
  • zero-suppressed binary decision diagrams

Cite this

Nagayama, S., Sasao, T., & Butler, J. T. (2019). A Dynamic Programming Based Method for Optimum Linear Decomposition of Index Generation Functions. In Proceedings - 2019 IEEE 49th International Symposium on Multiple-Valued Logic, ISMVL 2019 (pp. 144-149). [8758778] (Proceedings of The International Symposium on Multiple-Valued Logic; Vol. 2019-May). IEEE Computer Society. https://doi.org/10.1109/ISMVL.2019.00033
Nagayama, Shinobu ; Sasao, Tsutomu ; Butler, Jon T. / A Dynamic Programming Based Method for Optimum Linear Decomposition of Index Generation Functions. Proceedings - 2019 IEEE 49th International Symposium on Multiple-Valued Logic, ISMVL 2019. IEEE Computer Society, 2019. pp. 144-149 (Proceedings of The International Symposium on Multiple-Valued Logic).
@inproceedings{55521b70cf104a50934fd0cea12fb856,
title = "A Dynamic Programming Based Method for Optimum Linear Decomposition of Index Generation Functions",
abstract = "The problem addressed in this paper is minimization of the number of linear functions in a linear decomposition. This paper proposes an exact minimization method based on dynamic programming for index generation functions. The proposed method searches for an optimum solution while recursively dividing an index set of a given index generation function. To use partial solutions efficiently in solution search, the proposed method represents partitions of an index set compactly and uniquely by zero-suppressed binary decision diagrams (ZDDs). Existing methods based on a branch-and-bound approach search for a solution sequentially in a depth-first manner. On the other hand, the proposed method searches for multiple partial solutions in parallel in a breadth-first manner. Thus, once a solution is found, we can terminate the search process. This is because the depth of searches corresponds to the number of linear functions. Experimental results using benchmark index generation functions show the effectiveness of the proposed method.",
keywords = "Index generation functions, dynamic programming method, functional decomposition, linear decomposition, logic design, zero-suppressed binary decision diagrams",
author = "Shinobu Nagayama and Tsutomu Sasao and Butler, {Jon T.}",
year = "2019",
month = "5",
day = "1",
doi = "10.1109/ISMVL.2019.00033",
language = "English",
series = "Proceedings of The International Symposium on Multiple-Valued Logic",
publisher = "IEEE Computer Society",
pages = "144--149",
booktitle = "Proceedings - 2019 IEEE 49th International Symposium on Multiple-Valued Logic, ISMVL 2019",

}

Nagayama, S, Sasao, T & Butler, JT 2019, A Dynamic Programming Based Method for Optimum Linear Decomposition of Index Generation Functions. in Proceedings - 2019 IEEE 49th International Symposium on Multiple-Valued Logic, ISMVL 2019., 8758778, Proceedings of The International Symposium on Multiple-Valued Logic, vol. 2019-May, IEEE Computer Society, pp. 144-149, 49th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2019, Fredericton, Canada, 21/05/19. https://doi.org/10.1109/ISMVL.2019.00033

A Dynamic Programming Based Method for Optimum Linear Decomposition of Index Generation Functions. / Nagayama, Shinobu; Sasao, Tsutomu; Butler, Jon T.

Proceedings - 2019 IEEE 49th International Symposium on Multiple-Valued Logic, ISMVL 2019. IEEE Computer Society, 2019. p. 144-149 8758778 (Proceedings of The International Symposium on Multiple-Valued Logic; Vol. 2019-May).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - A Dynamic Programming Based Method for Optimum Linear Decomposition of Index Generation Functions

AU - Nagayama, Shinobu

AU - Sasao, Tsutomu

AU - Butler, Jon T.

PY - 2019/5/1

Y1 - 2019/5/1

N2 - The problem addressed in this paper is minimization of the number of linear functions in a linear decomposition. This paper proposes an exact minimization method based on dynamic programming for index generation functions. The proposed method searches for an optimum solution while recursively dividing an index set of a given index generation function. To use partial solutions efficiently in solution search, the proposed method represents partitions of an index set compactly and uniquely by zero-suppressed binary decision diagrams (ZDDs). Existing methods based on a branch-and-bound approach search for a solution sequentially in a depth-first manner. On the other hand, the proposed method searches for multiple partial solutions in parallel in a breadth-first manner. Thus, once a solution is found, we can terminate the search process. This is because the depth of searches corresponds to the number of linear functions. Experimental results using benchmark index generation functions show the effectiveness of the proposed method.

AB - The problem addressed in this paper is minimization of the number of linear functions in a linear decomposition. This paper proposes an exact minimization method based on dynamic programming for index generation functions. The proposed method searches for an optimum solution while recursively dividing an index set of a given index generation function. To use partial solutions efficiently in solution search, the proposed method represents partitions of an index set compactly and uniquely by zero-suppressed binary decision diagrams (ZDDs). Existing methods based on a branch-and-bound approach search for a solution sequentially in a depth-first manner. On the other hand, the proposed method searches for multiple partial solutions in parallel in a breadth-first manner. Thus, once a solution is found, we can terminate the search process. This is because the depth of searches corresponds to the number of linear functions. Experimental results using benchmark index generation functions show the effectiveness of the proposed method.

KW - Index generation functions

KW - dynamic programming method

KW - functional decomposition

KW - linear decomposition

KW - logic design

KW - zero-suppressed binary decision diagrams

UR - http://www.scopus.com/inward/record.url?scp=85069198027&partnerID=8YFLogxK

U2 - 10.1109/ISMVL.2019.00033

DO - 10.1109/ISMVL.2019.00033

M3 - Conference contribution

AN - SCOPUS:85069198027

T3 - Proceedings of The International Symposium on Multiple-Valued Logic

SP - 144

EP - 149

BT - Proceedings - 2019 IEEE 49th International Symposium on Multiple-Valued Logic, ISMVL 2019

PB - IEEE Computer Society

ER -

Nagayama S, Sasao T, Butler JT. A Dynamic Programming Based Method for Optimum Linear Decomposition of Index Generation Functions. In Proceedings - 2019 IEEE 49th International Symposium on Multiple-Valued Logic, ISMVL 2019. IEEE Computer Society. 2019. p. 144-149. 8758778. (Proceedings of The International Symposium on Multiple-Valued Logic). https://doi.org/10.1109/ISMVL.2019.00033