Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Logic/Constraint Programming and Concurrency: The Hard-Won Lessons of the Fifth Generation Computer Project Read chapter Read first chapter

2016 | OriginalPaper | Chapter

The Boolean Constraint Solver of SWI-Prolog (System Description)

Author : Markus Triska

Published in: Functional and Logic Programming

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present a new constraint solver over Boolean variables, available as library(clpb) (documentation: http://​eu.​swi-prolog.​org/​man/​clpb.​html) in SWI-Prolog. Our solver distinguishes itself from other available CLP(\(\mathcal {B}\)) solvers by several unique features: First, it is written entirely in Prolog and is hence portable to different Prolog implementations. Second, it is the first freely available BDD-based CLP(\(\mathcal {B}\)) solver. Third, we show that new interface predicates allow us to solve new types of problems with CLP(\(\mathcal {B}\)) constraints. We also use our implementation experience to contrast features and state necessary requirements of attributed variable interfaces to optimally support CLP(\(\mathcal {B}\)) constraints in different Prolog systems. Finally, we also present some performance results and comparisons with SICStus Prolog.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter From Proposition to Program
next chapter Probabilistic Inference by Program Transformation in Hakaru (System Description)
Footnotes
1
The documentation of SICStus Prolog 4.3.2 contains the exact wording of current support terms of the clpb module that ships with the system: “The library module is a direct port from SICStus Prolog 3. It is not supported by SICS in any way.”.
 
3
A Prolog DCG primer is available at http://​www.​metalevel.​at/​dcg.​html.
 
4
See http://​projecteuler.​net for more information.
 
5
The code of all benchmarks is available at http://​www.​metalevel.​at/​clpb-bench.
 
6
The variant is freely available at http://​www.​metalevel.​at/​clpb-zdd.
 
Literature
1.
Benhamou, F., Touraïvane, T.: Prolog IV: langage et algorithmes. In: JFPLC, pp. 51–64 (1995)
2.
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35(8), 677–691 (1986)CrossRefMATH
3.
Burckel, S., Hoarau, S., Mesnard, F., Neumerkel, U.: cTI: Bottom-up termination inference for logic programs. In: 15. WLP, pp. 123–134 (2000)
4.
Carlsson, M.: Boolean Constraints in SICStus Prolog. SICS TR, T91, 09 (1991)
5.
Codognet, P., Diaz, D.: A simple and efficient boolean solver for constraint logic programming. J. Autom. Reason. 17(1), 97–129 (1996)MathSciNetMATH
6.
Colin, S., Mesnard, F., Rauzy, A.: Un module Prolog de mu-calcul booléen: une réalisation par BDD. In: JFPLC 1999, Huitièmes Journées Francophones de Programmation Logique et Programmation par Contraintes, pp. 23–38 (1999)
7.
Demoen, B.: Dynamic attributes, their hProlog implementation, and a first evaluation. Report CW 350, Department of Computer Science, K.U. Leuven, October 2002
8.
Diaz, D., Abreu, S., Codognet, P.: On the implementation of GNU Prolog. TPLP 12(1–2), 253–282 (2012)MathSciNetMATH
9.
Dincbas, M., Hentenryck, P.V., Simonis, H., Aggoun, A., Graf, T., Berthier, F.: The constraint logic programming language CHIP. In: FGCS, pp. 693–702 (1988)
10.
11.
Jaffar, J., Lassez, J.L.: Constraint logic programming. In: POPL, pp.111–119 (1987)
12.
Knuth, D.E.: The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams, 12th edn. Addison-Wesley Professional, Reading, Massachusetts (2009)
13.
Mantadelis, T., Rocha, R., Kimmig, A., Janssens, G.: Preprocessing boolean formulae for BDDs in a probabilistic context. In: Janhunen, T., Niemelä, I. (eds.) JELIA 2010. LNCS, vol. 6341, pp. 260–272. Springer, Heidelberg (2010)CrossRef
14.
Marques-Silva, J.: Algebraic Simplification Techniques for Propositional Satisfiability. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, p. 537. Springer, Heidelberg (2000)CrossRef
15.
Minato, S.: Zero-suppressed BDDs for set manipulation in combinatorial problems. In: Design Automation Conference (DAC), pp. 272–277 (1993)
16.
Neumerkel, U.: Teaching Prolog and CLP (tutorial). In: ICLP (1997)
17.
Neumerkel, U., Kral, S.: Declarative program development in Prolog with GUPU. In: Proceedings of the 12th International Workshop on Logic Programming Environments, WLPE, pp. 77–86 (2002)
18.
Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. In: Second DIMACS Implementation Challenge (1993)
19.
20.
Tarau, P., Luderman, B.: Boolean evaluation with a pairing and unpairing function. In: SYNASC 2012, pp. 384–390 (2012)
21.
22.
Zhang, H.: SATO: an efficient propositional prover. In: McCune, W. (ed.) CADE 1997. LNCS, vol. 1249. Springer, Heidelberg (1997)
Metadata
Title
The Boolean Constraint Solver of SWI-Prolog (System Description)
Author
Markus Triska
Copyright Year
2016
Book
Functional and Logic Programming

Print ISBN: 978-3-319-29603-6

Electronic ISBN: 978-3-319-29604-3

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-29604-3_4

Premium Partner

    Image Credits