Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints

• URL: http://arxiv.org/abs/2002.06072v1
• Date: Fri, 14 Feb 2020 15:28:15 GMT
• Title: Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints
• Abstract summary: We introduce and investigate the expressive description logic (DL) ALCSCC++, in which the global and local cardinality constraints can be mixed. On the one hand, we prove that this does not increase the complexity of satisfiability checking and other standard inference problems. On the other hand, the satisfiability problem becomes undecidable if inverse roles are added to the languages.
• Score: 6.961253535504978
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce and investigate the expressive description logic (DL) ALCSCC++, in which the global and local cardinality constraints introduced in previous papers can be mixed. On the one hand, we prove that this does not increase the complexity of satisfiability checking and other standard inference problems. On the other hand, the satisfiability problem becomes undecidable if inverse roles are added to the languages. In addition, even without inverse roles, conjunctive query entailment in this DL turns out to be undecidable. We prove that decidability of querying can be regained if global and local constraints are not mixed and the global constraints are appropriately restricted. The latter result is based on a locally-acyclic model construction, and it reduces query entailment to ABox consistency in the restricted setting, i.e., to ABox consistency w.r.t. restricted cardinality constraints in ALCSCC, for which we can show an ExpTime upper bound.

Related papers

• Foundations of Global Consistency Checking with Noisy LLM Oracles [1.9954282121641704]
  We show that verifying global consistency requires exponentially many oracle queries in the worst case.<n>We propose an adaptive divide-and-conquer algorithm that identifies minimal inconsistent subsets.<n> Experiments with both synthetic and real oracles show that our method efficiently detects and localizes inconsistencies.
  arXiv  Detail & Related papers  (2026-01-20T05:02:35Z)
• Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning [52.03884701766989]
  offline reinforcement learning (RL) algorithms typically impose constraints on action selection.<n>We propose a new neighborhood constraint that restricts action selection in the Bellman target to the union of neighborhoods of dataset actions.<n>We develop a simple yet effective algorithm, Adaptive Neighborhood-constrained Q learning (ANQ), to perform Q learning with target actions satisfying this constraint.
  arXiv  Detail & Related papers  (2025-11-04T13:42:05Z)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  Chain-of-Thought (CoT) prompting enhances the reasoning of large language models (LLMs) by decomposing problems into sequential steps. We propose Syzygy of Thoughts (SoT)-a novel framework that extends CoT by introducing auxiliary, interrelated reasoning paths. SoT captures deeper logical dependencies, enabling more robust and structured problem-solving.
  arXiv  Detail & Related papers  (2025-04-13T13:35:41Z)
• Probabilistic and Causal Satisfiability: the Impact of Marginalization [3.44747819522562]
  We focus on satisfiability problems expressed in probabilistic and causal languages. We show that linear languages (allowing addition and marginalization) yield NPPP-, PSPACE-, and NEXP-complete satisfiability problems. We also consider constrained models that are restricted to a given Bayesian network, a Directed Acyclic Graph structure, or a small size.
  arXiv  Detail & Related papers  (2024-05-12T20:25:36Z)
• On the generalization of learned constraints for ASP solving in temporal domains [2.094218274474807]
  A key factor in the performance of today's ASP solvers is conflict-driven constraint learning. We study conditions under which learned dynamic constraints can be generalized. We empirically evaluate the impact of adding the generalized constraints to an ASP solver.
  arXiv  Detail & Related papers  (2024-01-29T12:49:09Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP), derives global solutions to CCSPs.
  arXiv  Detail & Related papers  (2023-09-02T15:20:36Z)
• Generalizing Level Ranking Constraints for Monotone and Convex Aggregates [0.0]
  In answer set programming (ASP), answer sets capture solutions to search problems of interest. One viable implementation strategy is provided by translation-based ASP. We take level ranking constraints into reconsideration, aiming at their generalizations to cover aggregate-based extensions of ASP.
  arXiv  Detail & Related papers  (2023-08-30T09:04:39Z)
• Coupling Global Context and Local Contents for Weakly-Supervised Semantic Segmentation [54.419401869108846]
  We propose a single-stage WeaklySupervised Semantic (WSSS) model with only the image-level class label supervisions. A flexible context aggregation module is proposed to capture the global object context in different granular spaces. A semantically consistent feature fusion module is proposed in a bottom-up parameter-learnable fashion to aggregate the fine-grained local contents.
  arXiv  Detail & Related papers  (2023-04-18T15:29:23Z)
• Feasible and Desirable Counterfactual Generation by Preserving Human Defined Constraints [6.123324869194193]
  We present a human-in-the-loop approach to generate counterfactual (CF) explanations that preserve global and local feasibility constraints. Our approach efficiently employs this knowledge to generate CF explanation by rejecting gradient steps that violate these constraints. We demonstrate that incorporating causal constraints during CF generation results in significantly better explanations in terms of feasibility and desirability for participants.
  arXiv  Detail & Related papers  (2022-10-12T08:04:37Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  We introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. We compare FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis.
  arXiv  Detail & Related papers  (2021-02-17T19:55:42Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Hierarchical Verification for Adversarial Robustness [89.30150585592648]
  We introduce a new framework for the exact point-wise $ell_p$ robustness verification problem. LayerCert exploits the layer-wise geometric structure of deep feed-forward networks with rectified linear activations (ReLU networks) We show that LayerCert provably reduces the number and size of the convex programs that one needs to solve compared to GeoCert.
  arXiv  Detail & Related papers  (2020-07-23T07:03:05Z)
• An ASP semantics for Constraints involving Conditional Aggregates [9.289905977910378]
  We elaborate upon the formal foundations of hybrid Answer Set Programming (ASP) We extend its underlying logical framework with aggregate functions over constraint values and variables. We put some emphasis on logic programs with linear constraints and show how common ASP aggregates can be regarded as particular cases of so-called conditional linear constraints.
  arXiv  Detail & Related papers  (2020-02-17T12:25:01Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  We design and analyze CascadeBAI, an algorithm for finding the best set of $K$ items. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes.
  arXiv  Detail & Related papers  (2020-01-23T16:47:52Z)
• The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs [10.042878093985458]
  Ontology-mediated querying and querying in the presence of constraints are two key database problems. We study the limits of efficient query evaluation in the context of guarded and frontier-guarded TGDs and on UCQs as the actual queries.
  arXiv  Detail & Related papers  (2019-12-28T11:08:33Z)

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.