Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formula

• URL: http://arxiv.org/abs/2110.05992v1
• Date: Tue, 12 Oct 2021 13:28:50 GMT
• Title: Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formula
• Authors: Sagar Malhotra and Luciano Serafini
• Abstract summary: Weighted First-Order Model Counting (WFOMC) computes the weighted sum of the models of a first-order logic theory on a finite domain. We introduce the concept of lifted interpretations as a tool for formulating closed-forms for WFOMC. We then expand this closed-form to incorporate cardinality constraints, existential quantifiers, and counting quantifiers (a.k.a C2) without losing domain-liftability.
• Score: 4.18804572788063
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Weighted First-Order Model Counting (WFOMC) computes the weighted sum of the models of a first-order logic theory on a given finite domain. First-Order Logic theories that admit polynomial-time WFOMC w.r.t domain cardinality are called domain liftable. We introduce the concept of lifted interpretations as a tool for formulating closed-forms for WFOMC. Using lifted interpretations, we reconstruct the closed-form formula for polynomial-time FOMC in the universally quantified fragment of FO2, earlier proposed by Beame et al. We then expand this closed-form to incorporate cardinality constraints, existential quantifiers, and counting quantifiers (a.k.a C2) without losing domain-liftability. Finally, we show that the obtained closed-form motivates a natural definition of a family of weight functions strictly larger than symmetric weight functions.

Related papers

• Bridging Weighted First Order Model Counting and Graph Polynomials [6.2686964302152735]
  We use Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. We can use them to solve WFOMC with all of the existing axioms known to be tractable.
  arXiv  Detail & Related papers  (2024-07-16T16:01:25Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers. We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states. By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
  arXiv  Detail & Related papers  (2024-01-31T15:50:50Z)
• From frustration-free parent Hamiltonians to off-diagonal long-range order: Moore-Read and related states in second quantization [51.47980393607887]
  We construct a second-quantized formula for Moore-Read Pfaffian states. We prove the existence of frustration-free parent Hamiltonians without appealing to such second-quantized properties.
  arXiv  Detail & Related papers  (2023-05-16T08:43:46Z)
• Super-model ecosystem: A domain-adaptation perspective [101.76769818069072]
  This paper attempts to establish the theoretical foundation for the emerging super-model paradigm via domain adaptation. Super-model paradigms help reduce computational and data cost and carbon emission, which is critical to AI industry.
  arXiv  Detail & Related papers  (2022-08-30T09:09:43Z)
• Quantification and Aggregation over Concepts of the Ontology [0.0]
  We argue that in some KR applications, we want to quantify over sets of concepts formally represented by symbols in the vocabulary. We present an extension of first-order logic to support such abstractions, and show that it allows writing expressions of knowledge that are elaboration tolerant.
  arXiv  Detail & Related papers  (2022-02-02T07:49:23Z)
• Conformal field theory from lattice fermions [77.34726150561087]
  We provide a rigorous lattice approximation of conformal field theories given in terms of lattice fermions in 1+1-dimensions. We show how these results lead to explicit error estimates pertaining to the quantum simulation of conformal field theories.
  arXiv  Detail & Related papers  (2021-07-29T08:54:07Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Weighted Model Counting in the two variable fragment with Cardinality Constraints: A Closed Form Formula [7.766921168069532]
  Weighted First-Order Model Counting (WFOMC) computes the weighted sum of the models of a first-order theory on a given finite domain. We introduce the concept of lifted interpretations as a tool for formulating inferences for WFOMC. We then expand this closed-form to incorporate existential quantifiers and cardinality constraints without losing domain-liftability.
  arXiv  Detail & Related papers  (2020-09-25T13:50:18Z)
• Learning Concepts Described by Weight Aggregation Logic [0.0]
  We introduce an extension of first-order logic that allows to aggregate weights ofs, compare such aggregates, and use them to build more complex formulas. We show that concepts definable in FOWA1 over a weighted background structure at most polylogarithmic degree are agnostically PAC-learnable in polylogarithmic time after pseudo-linear time preprocessing.
  arXiv  Detail & Related papers  (2020-09-22T14:32:42Z)
• Exponentially Weighted l_2 Regularization Strategy in Constructing Reinforced Second-order Fuzzy Rule-based Model [72.57056258027336]
  In the conventional Takagi-Sugeno-Kang (TSK)-type fuzzy models, constant or linear functions are usually utilized as the consequent parts of the fuzzy rules. We introduce an exponential weight approach inspired by the weight function theory encountered in harmonic analysis.
  arXiv  Detail & Related papers  (2020-07-02T15:42:15Z)
• On the Approximability of Weighted Model Integration on DNF Structures [13.986963122264632]
  We show that weighted model integration on DNF structures can indeed be approximated for a class of weight functions. Our approximation algorithm is based on three subroutines, each which can be a weak (i.e., approximate), or a strong (i.e., exact) oracle.
  arXiv  Detail & Related papers  (2020-02-17T00:29:41Z)

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.