Efficient autarkies

J. Marques-Silva, A. Ignatiev, A. Morgado, V. Manquinho, I. Lynce

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

9 Citations (Scopus)

Abstract

Autarkies are partial truth assignments that satisfy all clauses having literals in the assigned variables. Autarkies provide important information in the analysis of unsatisfiable formulas. Indeed, clauses satisfied by autarkies cannot be included in minimal explanations or in minimal corrections of unsatisfiability. Computing the maximum autarky allows identifying all such clauses. In recent years, a number of alternative approaches have been proposed for computing a maximum autarky. This paper develops new models for representing autarkies, and proposes new algorithms for computing the maximum autarky. Experimental results, obtained on a large number of problem instances, show orders of magnitude performance improvements over existing approaches, and solving instances that could not otherwise be solved.

Original languageEnglish
Title of host publicationECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic
Subtitle of host publicationIncluding - Prestigious Applications of Intelligent Systems (PAIS 2014) - Proceedings
EditorsTorsten Schaub, Gerhard Friedrich, Barry O'Sullivan
Place of PublicationAmsterdam Netherlands
PublisherIOS Press
Pages603-608
Number of pages6
ISBN (Electronic)9781614994183
DOIs
Publication statusPublished - 2014
Externally publishedYes
EventEuropean Conference on Artificial Intelligence 2014 - Prague, Czech Republic
Duration: 18 Aug 201422 Aug 2014
Conference number: 21st
https://web.archive.org/web/20140322194831/http://www.ecai2014.org/

Publication series

NameFrontiers in Artificial Intelligence and Applications
PublisherIOS Press
Volume263
ISSN (Print)0922-6389
ISSN (Electronic)1879-8314

Conference

ConferenceEuropean Conference on Artificial Intelligence 2014
Abbreviated titleECAI 2014
Country/TerritoryCzech Republic
CityPrague
Period18/08/1422/08/14
Internet address

Cite this