标题： 张量分解与知识编译的结合：一种比较张量列车与OBDDs的研究 显示英文标题

标题： Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs

摘要： 知识编译图分析布尔函数表示中的易处理操作并比较它们的简洁性。 这使得可以为不同应用选择适当的表示方法。 在知识编译图中，所有表示类都是否定范式（NNF）的子集。 然而，布尔函数可能由不同于NNF子集的表示方式更好地表达。 在本研究中，我们将张量列车视为布尔函数表示，并分析其简洁性和易处理性。 我们的研究是首次使用知识编译文献中的标准来评估一种张量分解方法的表达能力。 我们的主要结果表明，张量列车比有序二进制决策图（OBDDs）更简洁，并且支持与OBDDs相同的多项式时间操作。 我们的研究通过提供张量分解与现有NNF子集之间的理论联系，拓宽了其应用范围。 显示英文摘要

摘要： 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.