Standard

Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. / Dantsin, Evgeny; Hirsch, Edward A.; Wolpert, Alexander.

Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Springer Nature, 2006. p. 60-68 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3998 LNCS).

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

Harvard

Dantsin, E, Hirsch, EA & Wolpert, A 2006, Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. in Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3998 LNCS, Springer Nature, pp. 60-68, 6th Italian Conference on Algorithms and Complexity, CIAC 2006, Rome, Italy, 29/05/06. https://doi.org/10.1007/11758471_9

APA

Dantsin, E., Hirsch, E. A., & Wolpert, A. (2006). Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. In Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings (pp. 60-68). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3998 LNCS). Springer Nature. https://doi.org/10.1007/11758471_9

Vancouver

Dantsin E, Hirsch EA, Wolpert A. Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. In Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Springer Nature. 2006. p. 60-68. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11758471_9

Author

Dantsin, Evgeny ; Hirsch, Edward A. ; Wolpert, Alexander. / Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings. Springer Nature, 2006. pp. 60-68 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{b0ca9886356b44ee8202e7c6eb64fc32,
title = "Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms",
abstract = "We give a deterministic algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [6]. In comparison with the randomized algorithm in [6], our deterministic algorithm is simpler and more intuitive.",
author = "Evgeny Dantsin and Hirsch, {Edward A.} and Alexander Wolpert",
year = "2006",
month = jan,
day = "1",
doi = "10.1007/11758471_9",
language = "English",
isbn = "354034375X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "60--68",
booktitle = "Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings",
address = "Germany",
note = "6th Italian Conference on Algorithms and Complexity, CIAC 2006 ; Conference date: 29-05-2006 Through 31-05-2006",

}

RIS

TY - GEN

T1 - Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms

AU - Dantsin, Evgeny

AU - Hirsch, Edward A.

AU - Wolpert, Alexander

PY - 2006/1/1

Y1 - 2006/1/1

N2 - We give a deterministic algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [6]. In comparison with the randomized algorithm in [6], our deterministic algorithm is simpler and more intuitive.

AB - We give a deterministic algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [6]. In comparison with the randomized algorithm in [6], our deterministic algorithm is simpler and more intuitive.

UR - http://www.scopus.com/inward/record.url?scp=33746088410&partnerID=8YFLogxK

U2 - 10.1007/11758471_9

DO - 10.1007/11758471_9

M3 - Conference contribution

AN - SCOPUS:33746088410

SN - 354034375X

SN - 9783540343752

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 60

EP - 68

BT - Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings

PB - Springer Nature

T2 - 6th Italian Conference on Algorithms and Complexity, CIAC 2006

Y2 - 29 May 2006 through 31 May 2006

ER -

ID: 49828074