Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912221859151872 |
|---|---|
| author | Onaka, Ryoma Nakamura, Kengo Nishino, Masaaki Yasuda, Norihito |
| author_facet | Onaka, Ryoma Nakamura, Kengo Nishino, Masaaki Yasuda, Norihito |
| contents | A knowledge compilation map analyzes tractable operations in Boolean function representations and compares their succinctness. This enables the selection of appropriate representations for different applications. In the knowledge compilation map, all representation classes are subsets of the negation normal form (NNF). However, Boolean functions may be better expressed by a representation that is different from that of the NNF subsets. In this study, we treat tensor trains as Boolean function representations and analyze their succinctness and tractability. Our study is the first to evaluate the expressiveness of a tensor decomposition method using criteria from knowledge compilation literature. Our main results demonstrate that tensor trains are more succinct than ordered binary decision diagrams (OBDDs) and support the same polytime operations as OBDDs. Our study broadens their application by providing a theoretical link between tensor decomposition and existing NNF subsets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_03702 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs Onaka, Ryoma Nakamura, Kengo Nishino, Masaaki Yasuda, Norihito Data Structures and Algorithms A knowledge compilation map analyzes tractable operations in Boolean function representations and compares their succinctness. This enables the selection of appropriate representations for different applications. In the knowledge compilation map, all representation classes are subsets of the negation normal form (NNF). However, Boolean functions may be better expressed by a representation that is different from that of the NNF subsets. In this study, we treat tensor trains as Boolean function representations and analyze their succinctness and tractability. Our study is the first to evaluate the expressiveness of a tensor decomposition method using criteria from knowledge compilation literature. Our main results demonstrate that tensor trains are more succinct than ordered binary decision diagrams (OBDDs) and support the same polytime operations as OBDDs. Our study broadens their application by providing a theoretical link between tensor decomposition and existing NNF subsets. |
| title | Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.03702 |