DROPS

Document

DOI: 10.4230/LIPIcs.SAT.2026.31

Dsat: A Native SAT Solver for Discrete Logic

Authors: Yaofang Zhang, Ken Zhou, and Adnan Darwiche

Published in: LIPIcs, Volume 377, 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)

Abstract

Discrete variables are common in many applications, such as probabilistic reasoning, planning and explainable AI. When symbolic reasoning techniques are brought in to bear on these applications, a standard technique for handling discrete variables is to binarize them into Boolean variables to allow the use of Boolean computational machinery such as SAT solvers. This technique can face both computational and semantical challenges though. In this work, we develop a native SAT solver for discrete logic, which is a direct extension of Boolean logic in which variables can take arbitrary values. Our proposed solver has a similar design to Boolean SAT solvers, with ingredients such as unit resolution and clause learning but ones that operate natively on discrete variables. We illustrate the merits of the developed SAT solver by comparing it empirically to CSP solvers applied to discrete CNFs, to Boolean SAT solver applied to binarized CNFs, and to some hybrid solvers.

Cite as

Yaofang Zhang, Ken Zhou, and Adnan Darwiche. Dsat: A Native SAT Solver for Discrete Logic. In 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 377, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.SAT.2026.31,
  author =	{Zhang, Yaofang and Zhou, Ken and Darwiche, Adnan},
  title =	{{Dsat: A Native SAT Solver for Discrete Logic}},
  booktitle =	{29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-431-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{377},
  editor =	{Ignatiev, Alexey and Szeider, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2026.31},
  URN =		{urn:nbn:de:0030-drops-263372},
  doi =		{10.4230/LIPIcs.SAT.2026.31},
  annote =	{Keywords: Discrete Variables, CDCL SAT Solvers, Unit Resolution, Clause Learning}
}

Search Results

Documents authored by Zhang, Yaofang

Dsat: A Native SAT Solver for Discrete Logic

Abstract

Cite as

Thanks for your feedback!

Could not send message