An efficient solver for ASP(Q)
- URL: http://arxiv.org/abs/2305.10021v1
- Date: Wed, 17 May 2023 07:59:53 GMT
- Title: An efficient solver for ASP(Q)
- Authors: Wolfgang Faber, Giuseppe Mazzotta, and Francesco Ricca
- Abstract summary: ASP(Q) extends Answer Set Programming (ASP) to allow for declarative and modular modeling of problems from the hierarchy.
We present a new implementation that builds on the ideas of qasp and features both a more efficient encoding procedure and new optimized encodings of ASP(Q) programs in QBF.
- Score: 4.198045959496482
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Answer Set Programming with Quantifiers ASP(Q) extends Answer Set Programming
(ASP) to allow for declarative and modular modeling of problems from the entire
polynomial hierarchy. The first implementation of ASP(Q), called qasp, was
based on a translation to Quantified Boolean Formulae (QBF) with the aim of
exploiting the well-developed and mature QBF-solving technology. However, the
implementation of the QBF encoding employed in qasp is very general and might
produce formulas that are hard to evaluate for existing QBF solvers because of
the large number of symbols and sub-clauses. In this paper, we present a new
implementation that builds on the ideas of qasp and features both a more
efficient encoding procedure and new optimized encodings of ASP(Q) programs in
QBF. The new encodings produce smaller formulas (in terms of the number of
quantifiers, variables, and clauses) and result in a more efficient evaluation
process. An algorithm selection strategy automatically combines several
QBF-solving back-ends to further increase performance. An experimental
analysis, conducted on known benchmarks, shows that the new system outperforms
qasp.
Related papers
- Benchmarking Uncertainty Quantification Methods for Large Language Models with LM-Polygraph [85.51252685938564]
Uncertainty quantification (UQ) is becoming increasingly recognized as a critical component of applications that rely on machine learning (ML)
As with other ML models, large language models (LLMs) are prone to make incorrect predictions, hallucinate'' by fabricating claims, or simply generate low-quality output for a given input.
We introduce a novel benchmark that implements a collection of state-of-the-art UQ baselines, and provides an environment for controllable and consistent evaluation of novel techniques.
arXiv Detail & Related papers (2024-06-21T20:06:31Z) - Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
This work focuses on learning-based solutions for efficiently solving the Quadratic Assignment Problem (QAPs)
Current research on QAPs suffer from limited scale and inefficiency.
We propose the first solution of its kind for QAP in the learn-to-improve category.
arXiv Detail & Related papers (2024-06-14T10:15:03Z) - UniOQA: A Unified Framework for Knowledge Graph Question Answering with Large Language Models [4.627548680442906]
OwnThink is the most extensive Chinese open-domain knowledge graph introduced in recent times.
We introduce UniOQA, a unified framework that integrates two parallel approaches to question answering.
UniOQA notably advances SpCQL Logical Accuracy to 21.2% and Execution Accuracy to 54.9%, achieving the new state-of-the-art results on this benchmark.
arXiv Detail & Related papers (2024-06-04T08:36:39Z) - Recursive Visual Programming [53.76415744371285]
We propose Recursive Visual Programming (RVP), which simplifies generated routines, provides more efficient problem solving, and can manage more complex data structures.
We show RVP's efficacy through extensive experiments on benchmarks including VSR, COVR, GQA, and NextQA.
arXiv Detail & Related papers (2023-12-04T17:27:24Z) - SQUARE: Automatic Question Answering Evaluation using Multiple Positive
and Negative References [73.67707138779245]
We propose a new evaluation metric: SQuArE (Sentence-level QUestion AnsweRing Evaluation)
We evaluate SQuArE on both sentence-level extractive (Answer Selection) and generative (GenQA) QA systems.
arXiv Detail & Related papers (2023-09-21T16:51:30Z) - Sequential Query Encoding For Complex Query Answering on Knowledge
Graphs [31.40820604209387]
We propose sequential query encoding (SQE) as an alternative to encode queries for knowledge graph (KG) reasoning.
SQE first uses a search-based algorithm to linearize the computational graph to a sequence of tokens and then uses a sequence encoder to compute its vector representation.
Despite its simplicity, SQE demonstrates state-of-the-art neural query encoding performance on FB15k, FB15k-237, and NELL.
arXiv Detail & Related papers (2023-02-25T16:33:53Z) - Efficient Multiple Constraint Acquisition [1.3706331473063877]
Constraint acquisition systems such as QuAcq and MultiAcq can assist non-expert users to model their problems as constraint networks.
We present a technique that boosts the performance of constraint acquisition by reducing the number of queries significantly.
We then turn our attention to query generation which is a significant but rather overlooked part of the acquisition process.
arXiv Detail & Related papers (2021-09-13T12:42:16Z) - Planning with Incomplete Information in Quantified Answer Set
Programming [1.3501640559999886]
We present a general approach to planning with incomplete information in Answer Set Programming (ASP)
We represent planning problems using a simple formalism where logic programs describe the transition function between states.
We present a translation-based QASP solver that converts quantified logic programs into QBFs and then executes a QBF solver.
arXiv Detail & Related papers (2021-08-13T21:24:47Z) - Transformer-based Machine Learning for Fast SAT Solvers and Logic
Synthesis [63.53283025435107]
CNF-based SAT and MaxSAT solvers are central to logic synthesis and verification systems.
In this work, we propose a one-shot model derived from the Transformer architecture to solve the MaxSAT problem.
arXiv Detail & Related papers (2021-07-15T04:47:35Z) - Generating Diverse and Consistent QA pairs from Contexts with
Information-Maximizing Hierarchical Conditional VAEs [62.71505254770827]
We propose a conditional variational autoencoder (HCVAE) for generating QA pairs given unstructured texts as contexts.
Our model obtains impressive performance gains over all baselines on both tasks, using only a fraction of data for training.
arXiv Detail & Related papers (2020-05-28T08:26:06Z) - Multi-layer Optimizations for End-to-End Data Analytics [71.05611866288196]
We introduce Iterative Functional Aggregate Queries (IFAQ), a framework that realizes an alternative approach.
IFAQ treats the feature extraction query and the learning task as one program given in the IFAQ's domain-specific language.
We show that a Scala implementation of IFAQ can outperform mlpack, Scikit, and specialization by several orders of magnitude for linear regression and regression tree models over several relational datasets.
arXiv Detail & Related papers (2020-01-10T16:14:44Z)
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.