Truth table invariant cylindrical algebraic decomposition by regular chains

Russell Bradford, Changbo Chen, James H. Davenport, Matthew England, Marc Moreno Maza, David Wilson

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

18 Citations (Scopus)
8 Downloads (Pure)

Abstract

A new algorithm to compute cylindrical algebraic decompositions (CADs) is presented, building on two recent advances. Firstly, the output is truth table invariant (a TTICAD) meaning given formulae have constant truth value on each cell of the decomposition. Secondly, the computation uses regular chains theory to first build a cylindrical decomposition of complex space (CCD) incrementally by polynomial. Significant modification of the regular chains technology was used to achieve the more sophisticated invariance criteria. Experimental results on an implementation in the RegularChains Library for Maple verify that combining these advances gives an algorithm superior to its individual components and competitive with the state of the art.

Original languageEnglish
Title of host publicationComputer Algebra in Scientific Computing - 16th International Workshop, CASC 2014, Proceedings
PublisherSpringer Verlag
Pages44-58
Number of pages15
Volume8660 LNCS
ISBN (Electronic)978-3-319-10515-4
ISBN (Print)978-3-319-10514-7
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event16th International Workshop on Computer Algebra in Scientific Computing, CASC 2014 - Warsaw, Poland
Duration: 8 Sep 201412 Sep 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8660 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference16th International Workshop on Computer Algebra in Scientific Computing, CASC 2014
CountryPoland
CityWarsaw
Period8/09/1412/09/14

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-10515-4_4


Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

Keywords

  • cylindrical algebraic decomposition
  • equational constraint
  • regular chains
  • triangular decomposition

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Truth table invariant cylindrical algebraic decomposition by regular chains'. Together they form a unique fingerprint.

  • Cite this

    Bradford, R., Chen, C., Davenport, J. H., England, M., Moreno Maza, M., & Wilson, D. (2014). Truth table invariant cylindrical algebraic decomposition by regular chains. In Computer Algebra in Scientific Computing - 16th International Workshop, CASC 2014, Proceedings (Vol. 8660 LNCS, pp. 44-58). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8660 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-10515-4_4