Decidability of Querying First-Order Theories via Countermodels of Finite Width

• URL: http://arxiv.org/abs/2304.06348v3
• Date: Mon, 16 Sep 2024 17:57:11 GMT
• Title: Decidability of Querying First-Order Theories via Countermodels of Finite Width
• Authors: Thomas Feller, Tim S. Lyon, Piotr Ostropolski-Nalewaja, Sebastian Rudolph,
• Abstract summary: We propose a generic framework for establishing the decidability of a wide range of logical entailment problems (briefly called querying) We identify logics exhibiting width-finite finitely universal model sets, warranting decidable entailment for a wide range of homomorphism-closed queries. We explain how finite partitionwidth sets of rules subsume other known abstract decidable classes but - leveraging existing notions of stratification - also cover a wide range of new rulesets.
• Score: 3.712362524473752
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We propose a generic framework for establishing the decidability of a wide range of logical entailment problems (briefly called querying), based on the existence of countermodels that are structurally simple, gauged by certain types of width measures (with treewidth and cliquewidth as popular examples). As an important special case of our framework, we identify logics exhibiting width-finite finitely universal model sets, warranting decidable entailment for a wide range of homomorphism-closed queries, subsuming a diverse set of practically relevant query languages. As a particularly powerful width measure, we propose to employ Blumensath's partitionwidth, which subsumes various other commonly considered width measures and exhibits highly favorable computational and structural properties. Focusing on the formalism of existential rules as a popular showcase, we explain how finite partitionwidth sets of rules subsume other known abstract decidable classes but - leveraging existing notions of stratification - also cover a wide range of new rulesets. We expose natural limitations for fitting the class of finite unification sets into our picture and suggest several options for remedy.

Related papers

• Mapping Cardinality-based Feature Models to Weighted Automata over Featured Multiset Semirings (Extended Version) [2.2708009467351844]
  Cardinality-based feature models permit to select multiple copies of the same feature. We propose a behavioral variability modeling formalism for cardinality-based feature models.
  arXiv  Detail & Related papers  (2024-07-05T13:40:25Z)
• A Canonicalization Perspective on Invariant and Equivariant Learning [54.44572887716977]
  We introduce a canonicalization perspective that provides an essential and complete view of the design of frames. We show that there exists an inherent connection between frames and canonical forms. We design novel frames for eigenvectors that are strictly superior to existing methods.
  arXiv  Detail & Related papers  (2024-05-28T17:22:15Z)
• Explaining Modern Gated-Linear RNNs via a Unified Implicit Attention Formulation [54.50526986788175]
  Recent advances in efficient sequence modeling have led to attention-free layers, such as Mamba, RWKV, and various gated RNNs. We present a unified view of these models, formulating such layers as implicit causal self-attention layers. Our framework compares the underlying mechanisms on similar grounds for different layers and provides a direct means for applying explainability methods.
  arXiv  Detail & Related papers  (2024-05-26T09:57:45Z)
• General Policies, Subgoal Structure, and Planning Width [19.373790756767278]
  It has been observed that planning domains with atomic goals can be solved by means of a simple exploration procedure, called IW, that runs in time exponential in the problem width. Yet, there is no good explanation for why so many benchmark domains have bounded width when atomic goals are considered.
  arXiv  Detail & Related papers  (2023-11-09T16:30:22Z)
• Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework [11.778985277618354]
  We propose a unified meta-learning framework for a class of structured bandit problems where the parameter space can be factorized to item-level. The novel bandit algorithm is general to be applied to many popular problems,scalable to the huge parameter and action spaces, and robust to the specification of the generalization model.
  arXiv  Detail & Related papers  (2022-02-26T20:54:55Z)
• Polynomial Networks in Deep Classifiers [55.90321402256631]
  We cast the study of deep neural networks under a unifying framework. Our framework provides insights on the inductive biases of each model. The efficacy of the proposed models is evaluated on standard image and audio classification benchmarks.
  arXiv  Detail & Related papers  (2021-04-16T06:41:20Z)
• Closed-Form Factorization of Latent Semantics in GANs [65.42778970898534]
  A rich set of interpretable dimensions has been shown to emerge in the latent space of the Generative Adversarial Networks (GANs) trained for synthesizing images. In this work, we examine the internal representation learned by GANs to reveal the underlying variation factors in an unsupervised manner. We propose a closed-form factorization algorithm for latent semantic discovery by directly decomposing the pre-trained weights.
  arXiv  Detail & Related papers  (2020-07-13T18:05:36Z)
• Multi-view Orthonormalized Partial Least Squares: Regularizations and Deep Extensions [8.846165479467324]
  We establish a family of subspace-based learning method for multi-view learning using the least squares as the fundamental basis. We propose a unified multi-view learning framework to learn a classifier over a common latent space shared by all views.
  arXiv  Detail & Related papers  (2020-07-09T19:00:39Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Diverse Rule Sets [20.170305081348328]
  Rule-based systems are experiencing a renaissance owing to their intuitive if-then representation. We propose a novel approach of inferring diverse rule sets, by optimizing small overlap among decision rules. We then devise an efficient randomized algorithm, which samples rules that are highly discriminative and have small overlap.
  arXiv  Detail & Related papers  (2020-06-17T14:15:25Z)
• Explainable Matrix -- Visualization for Global and Local Interpretability of Random Forest Classification Ensembles [78.6363825307044]
  We propose Explainable Matrix (ExMatrix), a novel visualization method for Random Forest (RF) interpretability. It employs a simple yet powerful matrix-like visual metaphor, where rows are rules, columns are features, and cells are rules predicates. ExMatrix applicability is confirmed via different examples, showing how it can be used in practice to promote RF models interpretability.
  arXiv  Detail & Related papers  (2020-05-08T21:03:48Z)

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.