A Formal Study of Algebraic Constraint

We present a model for computation of algebraic constraint.
An algebraic constraint is defined to be a boolean formula of equations in which every equation is expressed by a polynomial over a field, and hence such constraint may contain negation of an equation, that is, a form f != 0 where f is some polynomial. Algebraic constraint appears in many application elds of data analysis such as study of geometries,
computer aided design, robotics and mechanics. It is well-known that we can describe negations in a form of equations by using slack variables, but traditional approaches assume the same number of slack variables as that of negations. This means the dimension of the ambient space that the targeted manifold is embedded in depends on the number of negations used in the constraint, which means the dimension is
not intrinsic.
We construct an algebraic model that enables to describe an arbitrary boolean formula including multiple negations by using only one slack variable.
Also the model provides boolean operations that commute with algebraic operations of polynomials in a natural way, in which we introduce a kind of semiring and its operations in order to make do with one slack variable. To use one slack variable means that we can always consider constraints over the ambient space of the same dimension (n + 1) where n is the number of original variables. We present our approach to construct this model and show some important properties of it.

By: Issei Yoshida

Published in: in 2007


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .