Cylindrical algebraic decompositions for boolean combinations

Russell Bradford, James H. Davenport, Matthew England, Scott McCallum, David Wilson

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

29 Citations (Scopus)

Abstract

This article makes the key observation that when using cylindrical algebraic decomposition (CAD) to solve a problem with respect to a set of polynomials, it is not always the signs of those polynomials that are of paramount importance but rather the truth values of certain quantifier free formulae involving them. This motivates our definition of a Truth Table Invariant CAD (TTICAD). We generalise the theory of equational constraints to design an algorithm which will efficiently construct a TTICAD for a wide class of problems, producing stronger results than when using equational constraints alone. The algorithm is implemented fully inMaple and we present promising results from experimentation.

Original languageEnglish
Title of host publicationISSAC 2013 - Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation
EditorsManual Kauers
Place of PublicationNew York
PublisherACM
Pages125-132
Number of pages8
ISBN (Print)9781450320597
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event38th International Symposium on Symbolic and Algebraic Computation, ISSAC 2013 - Boston, United States
Duration: 26 Jun 201329 Jun 2013

Conference

Conference38th International Symposium on Symbolic and Algebraic Computation, ISSAC 2013
CountryUnited States
CityBoston
Period26/06/1329/06/13

Keywords

  • Cylindrical algebraic decomposition
  • Equational constraint

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Cylindrical algebraic decompositions for boolean combinations'. Together they form a unique fingerprint.

  • Cite this

    Bradford, R., Davenport, J. H., England, M., McCallum, S., & Wilson, D. (2013). Cylindrical algebraic decompositions for boolean combinations. In M. Kauers (Ed.), ISSAC 2013 - Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (pp. 125-132). New York: ACM. https://doi.org/10.1145/2465506.2465516