Modelling digital circuits problems with set constraints

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

13 Citations (Scopus)

Abstract

A number of diagnostic and optimisation problems in Electronics Computer Aided Design have usually been handled either by specific tools or by mapping them into a general problem solver (e.g. a propositional Boolean SAT tool). This approach, however, requires models with substantial duplication of digital circuits. In Constraint Logic Programming, the use of extra values in the digital signals (other than the usual 0/1) was proposed to reflect their dependency on some faulty gate. In this paper we present an extension of this modelling approach, using set variables to denote dependency of the signals on sets of faults, to model different circuits problems. We then show the importance of propagating constraints on sets cardinality, by comparing Cardinal, a set constraint solver that we implemented, with a simpler version that propagates these constraints similarly to Conjunto, a widely available set constraint solver. Results show speed ups of Cardinal of about two orders of magnitude, on a set of diagnostic problems.

Original languageEnglish
Title of host publicationComputational Logic - CL 2000
Subtitle of host publicationFirst International Conference London, UK, July 24–28, 2000 Proceedings
EditorsJohn Lloyd, Veronica Dahl, Ulrich Furbach, Manfred Kerber, Kung-Kiu Lau, Catuscia Palamidessi, Luís Moniz Pereira, Yehoshua Sagiv, Peter J. Stuckey
PublisherSpringer-Verlag
Pages414-428
Number of pages15
ISBN (Electronic)3540677976, 9783540677970
DOIs
Publication statusPublished - 2000
Event1st International Conference on Computational Logic, CL 2000 - London, United Kingdom
Duration: 24 Jul 200028 Jul 2000

Publication series

NameLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
Volume1861
ISSN (Print)0302-9743

Conference

Conference1st International Conference on Computational Logic, CL 2000
CountryUnited Kingdom
CityLondon
Period24/07/0028/07/00

Keywords

  • Test Pattern
  • Digital Circuit
  • Constraint Solver
  • General Problem Solver
  • Automatic Test Pattern Generation

Fingerprint

Dive into the research topics of 'Modelling digital circuits problems with set constraints'. Together they form a unique fingerprint.

Cite this