Truth table invariant cylindrical algebraic decomposition by regular chains

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

doi:10.1007/978-3-319-10515-4_4

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 proceeding › Conference proceeding › peer-review

21 Citations (Scopus)

52 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 language	English
Title of host publication	Computer Algebra in Scientific Computing - 16th International Workshop, CASC 2014, Proceedings
Publisher	Springer Verlag
Pages	44-58
Number of pages	15
Volume	8660 LNCS
ISBN (Electronic)	978-3-319-10515-4
ISBN (Print)	978-3-319-10514-7
DOIs	https://doi.org/10.1007/978-3-319-10515-4_4
Publication status	Published - 2014
Externally published	Yes
Event	16th International Workshop on Computer Algebra in Scientific Computing, CASC 2014 - Warsaw, Poland Duration: 8 Sept 2014 → 12 Sept 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8660 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Workshop

Workshop	16th International Workshop on Computer Algebra in Scientific Computing, CASC 2014
Country/Territory	Poland
City	Warsaw
Period	8/09/14 → 12/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)

Access to Document

10.1007/978-3-319-10515-4_4

Post-PrintAccepted author manuscript, 1.03 MBLicence: CC BY-NC

Matthew England
- Research Centre for Computational Science and Mathematical Modelling - Associate Professor Academic, Centre Director
Person: Teaching and Research, Professional Services

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

Truth table invariant cylindrical algebraic decomposition by regular chains. / Bradford, Russell; Chen, Changbo; Davenport, James H. et al.
Computer Algebra in Scientific Computing - 16th International Workshop, CASC 2014, Proceedings. Vol. 8660 LNCS Springer Verlag, 2014. p. 44-58 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8660 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

Bradford, R, Chen, C, Davenport, JH, 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, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8660 LNCS, Springer Verlag, pp. 44-58, 16th International Workshop on Computer Algebra in Scientific Computing, CASC 2014, Warsaw, Poland, 8/09/14. https://doi.org/10.1007/978-3-319-10515-4_4

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

Bradford, Russell ; Chen, Changbo ; Davenport, James H. et al. / Truth table invariant cylindrical algebraic decomposition by regular chains. Computer Algebra in Scientific Computing - 16th International Workshop, CASC 2014, Proceedings. Vol. 8660 LNCS Springer Verlag, 2014. pp. 44-58 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d568da1dc9c442dc88d8dd377cdace12,

title = "Truth table invariant cylindrical algebraic decomposition by regular chains",

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.",

keywords = "cylindrical algebraic decomposition, equational constraint, regular chains, triangular decomposition",

author = "Russell Bradford and Changbo Chen and Davenport, {James H.} and Matthew England and {Moreno Maza}, Marc and David Wilson",

note = "The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-10515-4_4 Copyright {\textcopyright} 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. ; 16th International Workshop on Computer Algebra in Scientific Computing, CASC 2014 ; Conference date: 08-09-2014 Through 12-09-2014",

year = "2014",

doi = "10.1007/978-3-319-10515-4_4",

language = "English",

isbn = "978-3-319-10514-7",

volume = "8660 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "44--58",

booktitle = "Computer Algebra in Scientific Computing - 16th International Workshop, CASC 2014, Proceedings",

address = "Austria",

}

TY - GEN

T1 - Truth table invariant cylindrical algebraic decomposition by regular chains

AU - Bradford, Russell

AU - Chen, Changbo

AU - Davenport, James H.

AU - England, Matthew

AU - Moreno Maza, Marc

AU - Wilson, David

N1 - 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.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - cylindrical algebraic decomposition

KW - equational constraint

KW - regular chains

KW - triangular decomposition

U2 - 10.1007/978-3-319-10515-4_4

DO - 10.1007/978-3-319-10515-4_4

M3 - Conference proceeding

AN - SCOPUS:84906985421

SN - 978-3-319-10514-7

VL - 8660 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 44

EP - 58

BT - Computer Algebra in Scientific Computing - 16th International Workshop, CASC 2014, Proceedings

PB - Springer Verlag

T2 - 16th International Workshop on Computer Algebra in Scientific Computing, CASC 2014

Y2 - 8 September 2014 through 12 September 2014

ER -

Truth table invariant cylindrical algebraic decomposition by regular chains

Abstract

Publication series

Workshop

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Profiles

Matthew England

Cite this