Implementation of critical path heuristics for SAT

Jinbo Huang

doi:10.3233/978-1-61499-098-7-907

Implementation of critical path heuristics for SAT

Jinbo Huang^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

Abstract

Recent work has shown that SAT can be theoretically more powerful than heuristic search provided the heuristic used by search is implemented as a set of clauses on which unit propagation simulates the evaluation of the heuristic. The h^max heuristic has been shown to be implemented trivially by the empty set of clauses. This paper presents an implementation of h^m, a generalization of h^max.

Original language	English
Title of host publication	ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration
Publisher	IOS Press BV
Pages	907-908
Number of pages	2
ISBN (Print)	9781614990970
DOIs	https://doi.org/10.3233/978-1-61499-098-7-907
Publication status	Published - 2012
Event	20th European Conference on Artificial Intelligence, ECAI 2012 - Montpellier, France Duration: 27 Aug 2012 → 31 Aug 2012

Publication series

Name	Frontiers in Artificial Intelligence and Applications
Volume	242
ISSN (Print)	0922-6389
ISSN (Electronic)	1879-8314

Conference

Conference	20th European Conference on Artificial Intelligence, ECAI 2012
Country/Territory	France
City	Montpellier
Period	27/08/12 → 31/08/12

Access to Document

10.3233/978-1-61499-098-7-907

Cite this

Huang, J. (2012). Implementation of critical path heuristics for SAT. In ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration (pp. 907-908). (Frontiers in Artificial Intelligence and Applications; Vol. 242). IOS Press BV. https://doi.org/10.3233/978-1-61499-098-7-907

@inproceedings{f049868abaeb4e38af926ef8fdc66c88,

title = "Implementation of critical path heuristics for SAT",

abstract = "Recent work has shown that SAT can be theoretically more powerful than heuristic search provided the heuristic used by search is implemented as a set of clauses on which unit propagation simulates the evaluation of the heuristic. The hmax heuristic has been shown to be implemented trivially by the empty set of clauses. This paper presents an implementation of hm, a generalization of hmax.",

author = "Jinbo Huang",

year = "2012",

doi = "10.3233/978-1-61499-098-7-907",

language = "English",

isbn = "9781614990970",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press BV",

pages = "907--908",

booktitle = "ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration",

address = "Netherlands",

note = "20th European Conference on Artificial Intelligence, ECAI 2012 ; Conference date: 27-08-2012 Through 31-08-2012",

}

Huang, J 2012, Implementation of critical path heuristics for SAT. in ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. Frontiers in Artificial Intelligence and Applications, vol. 242, IOS Press BV, pp. 907-908, 20th European Conference on Artificial Intelligence, ECAI 2012, Montpellier, France, 27/08/12. https://doi.org/10.3233/978-1-61499-098-7-907

Implementation of critical path heuristics for SAT. / Huang, Jinbo.
ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. IOS Press BV, 2012. p. 907-908 (Frontiers in Artificial Intelligence and Applications; Vol. 242).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

TY - GEN

T1 - Implementation of critical path heuristics for SAT

AU - Huang, Jinbo

PY - 2012

Y1 - 2012

N2 - Recent work has shown that SAT can be theoretically more powerful than heuristic search provided the heuristic used by search is implemented as a set of clauses on which unit propagation simulates the evaluation of the heuristic. The hmax heuristic has been shown to be implemented trivially by the empty set of clauses. This paper presents an implementation of hm, a generalization of hmax.

AB - Recent work has shown that SAT can be theoretically more powerful than heuristic search provided the heuristic used by search is implemented as a set of clauses on which unit propagation simulates the evaluation of the heuristic. The hmax heuristic has been shown to be implemented trivially by the empty set of clauses. This paper presents an implementation of hm, a generalization of hmax.

UR - https://www.scopus.com/pages/publications/84878803348

U2 - 10.3233/978-1-61499-098-7-907

DO - 10.3233/978-1-61499-098-7-907

M3 - Conference Paper

AN - SCOPUS:84878803348

SN - 9781614990970

T3 - Frontiers in Artificial Intelligence and Applications

SP - 907

EP - 908

BT - ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration

PB - IOS Press BV

T2 - 20th European Conference on Artificial Intelligence, ECAI 2012

Y2 - 27 August 2012 through 31 August 2012

ER -

Huang J. Implementation of critical path heuristics for SAT. In ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. IOS Press BV. 2012. p. 907-908. (Frontiers in Artificial Intelligence and Applications). doi: 10.3233/978-1-61499-098-7-907

Implementation of critical path heuristics for SAT

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this