Relevance for SAT(ID)

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Researchers

  • Joachim Jansen
  • Bart Bogaerts

  • Jo Devriendt
  • Gerda Janssens
  • Marc Denecker

Research units

Abstract

Inductive definitions and justifications are wellstudied concepts. Solvers that support inductive definitions have been developed, but several of their computationally nice properties have never been exploited to improve these solvers. In this paper, we present a new notion called relevance. We determine a class of literals that are relevant for a given definition and partial interpretation, and show that choices on irrelevant atoms can never benefit the search for a model. We propose an early stopping criterion and a modification of existing heuristics that exploit relevance. We present a first implementation in MinisatID and experimentally evaluate our approach, and study how often existing solvers make choices on irrelevant atoms.

Details

Original languageEnglish
Title of host publicationProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, {IJCAI} 2016
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventInternational Joint Conference on Artificial Intelligence - New York Hilton Midtown, New York, United States
Duration: 9 Jul 201615 Jul 2016
Conference number: 25
http://ijcai-16.org/index.php/welcome/view/home

Conference

ConferenceInternational Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI
CountryUnited States
CityNew York
Period09/07/201615/07/2016
Internet address

ID: 6777791