Solving Epistemic Logic Programs using Generate-and-Test with Propagation

Jorge Fandinno, Lute Lillo
10/29/2024
cs.AIcs.LO

No official code found. Best implementation: potassco/eclingo (14 stars, MIT, last commit 2024-12-14).

Abstract

This paper introduces a general framework for generate-and-test-based solvers for epistemic logic programs that can be instantiated with different generator and tester programs, and we prove sufficient conditions on those programs for the correctness of the solvers built using this framework. It also introduces a new generator program that incorporates the propagation of epistemic consequences and shows that this can exponentially reduce the number of candidates that need to be tested while only incurring a linear overhead. We implement a new solver based on these theoretical findings and experimentally show that it outperforms existing solvers by achieving a ~3.3x speed-up and solving 91% more instances on well-known benchmarks.

View on arXivView PDF

Code Implementations(1)

potassco/eclingoCommunity100%
MIT

🧠 A solver for epistemic logic programs.

145PythonJun 25, 20191 years agoMIT

Similar Papers

Learn from Failure: Fine-Tuning LLMs with Trial-and-Error Data for Intuitionistic Propositional Logic Proving

81% match1 repo22024

Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science

79% match2026

ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis

79% match1 repo22026

Language Models can be Logical Solvers

79% match2023

Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning

79% match2 repos4072023

Pearce's Characterisation in an Epistemic Domain

79% match2025

Cite this paper

@article{fandinno2024solving,
  title  = {Solving Epistemic Logic Programs using Generate-and-Test with Propagation},
  author = {Jorge Fandinno and Lute Lillo},
  year   = {2024},
  eprint = {2410.22130},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2410.22130v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2410.22130.svg)](https://codeofpaper.com/paper/2410.22130)

Discussion