Variants of Tagged Sentential Decision Diagrams

• URL: http://arxiv.org/abs/2312.00793v1
• Date: Thu, 16 Nov 2023 12:29:25 GMT
• Title: Variants of Tagged Sentential Decision Diagrams
• Authors: Deyuan Zhong, Mingwei Zhang, Quanlong Guan, Liangda Fang, Zhaorong Lai, Yong Lai
• Abstract summary: A recently proposed canonical form of Boolean functions, namely tagged sentential decision diagrams (TSDDs), exploits both the standard and zero-suppressed trimming rules. In this paper, we present a variant of TSDDs which we call standard TSDDs (STSDDs) by reversing the order of trimming rules. We then prove the canonicity of STSDDs and present the algorithms for binary operations on TSDDs.
• Score: 6.891570850234007
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recently proposed canonical form of Boolean functions, namely tagged sentential decision diagrams (TSDDs), exploits both the standard and zero-suppressed trimming rules. The standard ones minimize the size of sentential decision diagrams (SDDs) while the zero-suppressed trimming rules have the same objective as the standard ones but for zero-suppressed sentential decision diagrams (ZSDDs). The original TSDDs, which we call zero-suppressed TSDDs (ZTSDDs), firstly fully utilize the zero-suppressed trimming rules, and then the standard ones. In this paper, we present a variant of TSDDs which we call standard TSDDs (STSDDs) by reversing the order of trimming rules. We then prove the canonicity of STSDDs and present the algorithms for binary operations on TSDDs. In addition, we offer two kinds of implementations of STSDDs and ZTSDDs and acquire three variations of the original TSDDs. Experimental evaluations demonstrate that the four versions of TSDDs have the size advantage over SDDs and ZSDDs.

Related papers

• ZeroDDI: A Zero-Shot Drug-Drug Interaction Event Prediction Method with Semantic Enhanced Learning and Dual-Modal Uniform Alignment [11.290096354280111]
  Previously unobserved/unseen DDIEs have been emerging, posing a new classification task when unseen classes have no labelled instances in the training stage. Existing computational methods are not directly applicable to ZS-DDIE, which has two primary challenges: obtaining suitable DDIE representations and handling the class imbalance issue. We propose a novel method named ZeroDDI for the ZS-DDIE task, which emphasizes the key biological semantics and distills discriminative molecular substructure-related semantics for DDIE representation learning.
  arXiv  Detail & Related papers  (2024-07-01T01:28:14Z)
• Canonical Decision Diagrams Modulo Theories [0.19285000127136376]
  Decision diagrams are powerful tools to represent propositional formulas. Some forms of DDs (e.g., OBDDs, SDDs) are canonical, that is, (under given conditions on the atom list) they univocally represent equivalence classes of formulas. We present a novel technique to leverage DDs to SMT level, which has several advantages.
  arXiv  Detail & Related papers  (2024-04-25T09:34:49Z)
• A new algorithm for Subgroup Set Discovery based on Information Gain [58.720142291102135]
  Information Gained Subgroup Discovery (IGSD) is a new SD algorithm for pattern discovery. We compare IGSD with two state-of-the-art SD algorithms: FSSD and SSD++. IGSD provides better OR values than FSSD and SSD++, stating a higher dependence between patterns and targets.
  arXiv  Detail & Related papers  (2023-07-26T21:42:34Z)
• Exploiting Asymmetry in Logic Puzzles: Using ZDDs for Symbolic Model Checking Dynamic Epistemic Logic [0.0]
  We use ZDDs to symbolically encode Kripke models used in Dynamic Epistemic Logic. We show that replacing BDDs with the right variant of ZDDs can significantly reduce memory usage. This suggests that ZDDs are a useful tool for model checking multi-agent systems.
  arXiv  Detail & Related papers  (2023-07-11T07:13:09Z)
• Decentralized SGD and Average-direction SAM are Asymptotically Equivalent [101.37242096601315]
  Decentralized gradient descent (D-SGD) allows collaborative learning on massive devices simultaneously without the control of a central server. Existing theories claim that decentralization invariably generalization.
  arXiv  Detail & Related papers  (2023-06-05T14:19:52Z)
• Delta Denoising Score [51.98288453616375]
  We introduce Delta Denoising Score (DDS), a novel scoring function for text-based image editing. It guides minimal modifications of an input image towards the content described in a target prompt.
  arXiv  Detail & Related papers  (2023-04-14T12:22:41Z)
• Belief Revision in Sentential Decision Diagrams [126.94029917018733]
  We develop a general revision algorithm for SDDs based on a syntactic characterisation of Dalal revision. Preliminary experiments performed with randomly generated knowledge bases show the advantages of directly perform revision within SDD formalism.
  arXiv  Detail & Related papers  (2022-01-20T11:01:41Z)
• ADAPT: Mitigating Idling Errors in Qubits via Adaptive Dynamical Decoupling [3.2505361717998227]
  A qubit is susceptible to idling errors, which occur when the qubit is idle and not actively undergoing any operations. Existing Dynamical Decoupling protocols have been primarily studied for individual qubits. We propose Adaptive Dynamical Decoupling (ADAPT), a software framework that estimates the efficacy of DD for each qubit combination.
  arXiv  Detail & Related papers  (2021-09-11T16:15:24Z)
• Semantics-Guided Contrastive Network for Zero-Shot Object detection [67.61512036994458]
  Zero-shot object detection (ZSD) is a new challenge in computer vision. We develop ContrastZSD, a framework that brings contrastive learning mechanism into the realm of zero-shot detection. Our method outperforms the previous state-of-the-art on both ZSD and generalized ZSD tasks.
  arXiv  Detail & Related papers  (2021-09-04T03:32:15Z)
• Variable Shift SDD: A More Succinct Sentential Decision Diagram [10.91026094237478]
  Sentential Decision Diagram (SDD) is a tractable representation of Boolean functions. We propose a more succinct variant of SDD named Variable Shift SDD (VS-SDD) We show that VS-SDDs are never larger than SDDs and there are cases in which the size of a VS-SDD is exponentially smaller than that of an SDD.
  arXiv  Detail & Related papers  (2020-04-06T09:18:19Z)
• Simple and Effective Prevention of Mode Collapse in Deep One-Class Classification [93.2334223970488]
  We propose two regularizers to prevent hypersphere collapse in deep SVDD. The first regularizer is based on injecting random noise via the standard cross-entropy loss. The second regularizer penalizes the minibatch variance when it becomes too small.
  arXiv  Detail & Related papers  (2020-01-24T03:44:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.