Cylindrical Algebraic Decomposition (CAD) has long been one of the most
important algorithms within Symbolic Computation, as a tool to perform
quantifier elimination in first order logic over the reals. More recently it is
finding prominence in the Satisfiability Checking community as a tool to
identify satisfying solutions of problems in nonlinear real arithmetic.
The original algorithm produces decompositions according to the signs of
polynomials, when what is usually required is a decomposition according to the
truth of a formula containing those polynomials. One approach to achieve that
coarser (but hopefully cheaper) decomposition is to reduce the polynomials
identified in the CAD to reflect a logical structure which reduces the solution
space dimension: the presence of Equational Constraints (ECs).
This paper may act as a tutorial for the use of CAD with ECs: we describe all
necessary background and the current state of the art. In particular, we
present recent work on how McCallum's theory of reduced projection may...

more |
pdf
| html
ComputerPapers:
Cylindrical Algebraic Decomposition with Equational Constraints. https://t.co/bfDQpmAmD5

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 20478

Unqiue Words: 4279

The aim of the paper is to produce new families of irreducible polynomials,
generalizing previous results in the area. One example of our general result is
that for a near-separated polynomial, i.e., polynomials of the form
$F(x,y)=f_1(x)f_2(y)-f_2(x)f_1(y)$, then $F(x,y)+r$ is always irreducible for
any constant $r$ different from zero. We also provide the biggest known family
of HIP polynomials in several variables. These are polynomials
$p(x_1,\ldots,x_n) \in K[x_1,\ldots,x_n]$ over a zero characteristic field $K$
such that $p(h_1(x_1),\ldots,h_n(x_n))$ is irreducible over $K$ for every
$n$-tuple $h_1(x_1),\ldots,h_n(x_n)$ of non constant one variable polynomials
over $K$. The results can also be applied to fields of positive characteristic,
with some modifications.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 3876

Unqiue Words: 1035

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 99,586 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible