Knowledge compilation is a method of transforming knowledge into a compressed and tractable form for permitting more efficient operations. For Boolean functions, numerous representations have been proposed that enhance succinctness and tractability. In this paper, we introduce a new representation named structured Decomposable And-Sum Circuit (st-DASC), which employs AND and SUM nodes with signed edges, in place of the standard AND and OR nodes with unsigned edges. Notably, incorporating negative signs permits polytime logical negation. By following a knowledge compilation map, we show that st-DASCs are more succinct than Sentential Decision Diagrams (SDDs) while maintaining support for every operation on the knowledge compilation map that SDD supports. Furthermore, st-DASCs are even more succinct than structured d-DNNFs (st-d-DNNFs), which are more succinct than SDDs although they support fewer operations than SDDs. Accordingly, st-DASCs break the traditional trade-off between succinctness and tractability over SDDs and st-d-DNNFs.

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.

Network reliability, that is, the probability of con-necting specified nodes under link failures, is a key metric of network infrastructure. Because network reliability evaluation is a computationally heavy task, past research has relied on unre-alistically simple failure models such as the independent failure model, wherein each link fails stochastically and independently, ignoring large-scale failures such as disasters, or the deterministic-correlated failure model, wherein all links within a disaster area always fail. However, actual networks follow the probabilistic-correlated (PC) failure model, wherein links in a disaster area fail stochastically with respect to each disaster. This paper proposes an efficient method to accurately compute network reliability under the PC model. Following a conventional method for the independent model, the proposed method uses binary decision diagrams (BDDs) to efficiently handle an exponential number of failure states. Additionally, it employs a probabilistic inference technique to support probabilistic correlation, which is represented as another BDD for integration with the conventional method. The computational complexity was theoretically analyzed, and its performance was experimentally verified; it can compute the network reliability within 1 h for a large network with nearly 200 links and 100 potential disasters.