The re-implementation POLYBORI's native wrapper is available to the user too:
sage: from polybori import * sage: declare_ring([Block('x',2),Block('y',3)],globals()) Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2) sage: r Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: [Variable(i) for i in xrange(r.ngens())] [x(0), x(1), y(0), y(1), y(2)]
For details on this interface see:
http://polybori.sourceforge.net/doc/tutorial/tutorial.html.
REFERENCES: [BD07] Michael Brickenstein, Alexander Dreyer; 'POLYBORI: A Groebner basis framework for Boolean polynomials'; http://www.itwm.fraunhofer.de/zentral/download/berichte/bericht122.pdf
Module-level Functions
) |
) |
) |
) |
) |
) |
) |
Return the currently active global ring, this is only relevant for the native POLYBORI interface.
sage: from polybori import declare_ring, get_cring, Block sage: R = declare_ring([Block('x',2),Block('y',3)],globals()) sage: Q = get_cring(); Q Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2) sage: R is Q True
) |
) |
Return a variable mapping between variables of other and ring. When other is a parent object, the mapping defines images for all variables of other. If it is an element, only variables occuring in other are mapped.
Raises NameError
if no such mapping is possible.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: R.<z,y> = QQ[] sage: sage.rings.polynomial.pbori.get_var_mapping(P,R) [z, y] sage: sage.rings.polynomial.pbori.get_var_mapping(P, z^2) [z, None]
sage: R.<z,x> = BooleanPolynomialRing(2) sage: sage.rings.polynomial.pbori.get_var_mapping(P,R) [z, x] sage: sage.rings.polynomial.pbori.get_var_mapping(P, x^2) [None, x]
) |
) |
The opposite of navigating down a ZDD using navigators is to construct new ZDDs in the same way, namely giving their else- and then-branch as well as the index value of the new node.
Input:
BooleSet
or a BoolePolynomial
BooleSet
or a BoolePolynomial
sage: from polybori import if_then_else sage: B = BooleanPolynomialRing(6,'x') sage: x0,x1,x2,x3,x4,x5 = B.gens() sage: f0 = x2*x3+x3 sage: f1 = x4 sage: if_then_else(x1, f0, f1) {{x1,x2,x3}, {x1,x3}, {x4}}
sage: if_then_else(x1.lm().index(),f0,f1) {{x1,x2,x3}, {x1,x3}, {x4}}
sage: if_then_else(x5, f0, f1) Traceback (most recent call last): ... IndexError: index of root must be less than the values of roots of the branches.
) |
) |
) |
) |
) |
) |
) |
) |
) |
) |
) |
) |
) |
Set the currently active global ring, this is only relevant for the native POLYBORI interface.
sage: from polybori import * sage: declare_ring([Block('x',2),Block('y',3)],globals()) Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2) sage: R = get_cring(); R Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: declare_ring([Block('x',2),Block('y',2)],globals()) Boolean PolynomialRing in x(0), x(1), y(0), y(1)
sage: get_cring() Boolean PolynomialRing in x(0), x(1), y(0), y(1)
sage: set_cring(R) sage: get_cring() Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
) |
) |
Return the highest index in the parameter s.
Input:
BooleSet
, BooleMonomial
, BoolePolynomial
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: from polybori import top_index sage: top_index(x.lm()) 0 sage: top_index(y*z) 1 sage: top_index(x + 1) 0
) |
Unpickle boolean polynomials
sage: T = TermOrder('deglex',2)+TermOrder('deglex',2) sage: P.<a,b,c,d> = BooleanPolynomialRing(4,order=T) sage: loads(dumps(a+b)) == a+b # indirect doctest True
) |
Unpickle boolean polynomial rings.
sage: T = TermOrder('deglex',2)+TermOrder('deglex',2) sage: P.<a,b,c,d> = BooleanPolynomialRing(4,order=T) sage: loads(dumps(P)) == P # indirect doctest True
) |
Class: BooleanMonomial
Functions: deg,
degree,
divisors,
index,
iterindex,
multiples,
reducibleBy,
set,
stableHash
) |
Return degree of this monomial.
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: M(x*y).deg() 2
sage: M(x*x*y*z).deg() 3
) |
Return degree of this monomial.
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: M(x*y).degree() 2
) |
Return a set of boolean monomials with all divisors of this monomial.
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: m.divisors() {{x,y}, {x}, {y}, {}}
) |
Return the variable index of the first variable in this monomial.
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: m.index() 0
) |
Return an iterator over the indicies of the variables in self.
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: list(M(x*z).iterindex()) [0, 2]
) |
Return a set of boolean monomials with all multiples of this monomial up the bound rhs.
Input:
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x sage: m = f.lm() sage: g = x*y*z sage: n = g.lm() sage: m.multiples(n) {{x,y,z}, {x,y}, {x,z}, {x}} sage: n.multiples(m) {{x,y,z}}
NOTE: The returned set always contains self
even if the
bound rhs is smaller than self
.
) |
Return True
if self
is reducible by rhs.
Input:
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: m.reducibleBy((x*y).lm()) True sage: m.reducibleBy((x*z).lm()) False
) |
Return a boolean set of variables in this monomials.
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: m.set() {{x,y}}
Special Functions: __add__,
__call__,
__eq__,
__ge__,
__gt__,
__init__,
__iter__,
__le__,
__len__,
__lt__,
__ne__,
__radd__,
_eval,
_repr_
) |
Addition operator. Returns a boolean polynomial.
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x = M(x); xy = M(x*y) sage: x + xy x*y + x
sage: x+0 x sage: 0+x # todo: not implemented x
sage: x+1 x + 1 sage: 1 + x # todo: not implemented x + 1
) |
Evaluate this monomial.
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: m(B(0),B(1)) 0 sage: m(x=B(1)) y
) |
Return an iterator over the variables in this monomial.
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: list(M(x*z)) # indirect doctest [x, z]
) |
Evaluate this monomial.
Input:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: m = P._monom_monoid(x*y) sage: m._eval({0:y,1:z}) y*z
) |
Return a string representing self.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: M = sage.rings.polynomial.pbori.BooleanMonomialMonoid(P) sage: M(x*y) # indirect doctest x*y
sage: R.<t,u> = BooleanPolynomialRing(2) sage: M(x*y) x*y
Class: BooleanMonomialIterator
Functions: next
) |
Special Functions: __iter__,
__next__
) |
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: for m in f: list(m.iterindex())# indirect doctest [0, 1] [2] []
) |
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: m = f.lm() sage: m.iterindex().next() 0
Class: BooleanMonomialMonoid
Functions: gen,
gens,
ngens
) |
Return the i-th generator of self.
Input:
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: M.gen(0) x sage: M.gen(2) z
sage: P = BooleanPolynomialRing(1000, 'x') sage: M = BooleanMonomialMonoid(P) sage: M.gen(50) x50
) |
Return the tuple of generators of this monoid.
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: M.gens() (x, y, z)
) |
Returns the number of variables in this monoid.
sage: from polybori import BooleanMonomialMonoid sage: P = BooleanPolynomialRing(100, 'x') sage: M = BooleanMonomialMonoid(P) sage: M.ngens() 100
Special Functions: __call__,
__init__,
_coerce_impl,
_repr_
) |
Convert elements of other objects to elements of this monoid.
Input:
None
a BooleanMonomial representing 1
is returned
- only BooleanPolynomials
with the same
parent ring as self
which have a single
monomial is converted
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x_monom = M(x); x_monom x
sage: M(x*y) x*y
sage: M(x+y) Traceback (most recent call last): ... TypeError: cannot convert to BooleanMonomialMonoid
Convert elements of self.
sage: M(x_monom) x
Convert from other BooleanPolynomialRings.
sage: R.<z,x> = BooleanPolynomialRing(2) sage: t = M(z); t z sage: t.parent() is M True
Convert BooleanMonomials over other BooleanPolynomialRings.
sage: N = BooleanMonomialMonoid(R) sage: t = M(N(x*z)); t x*z sage: t.parent() is M True
) |
Construct a boolean monomial monoid given a boolean polynomial ring.
This object provides a parent for boolean monomials.
Input:
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y> = BooleanPolynomialRing(2) sage: M = BooleanMonomialMonoid(P) sage: M MonomialMonoid of Boolean PolynomialRing in x, y
sage: M.gens() (x, y) sage: type(M.gen(0)) <type 'sage.rings.polynomial.pbori.BooleanMonomial'>
) |
Canonical conversion of elements from other objects to this monoid.
Coerce elements of self.
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x_monom = M(x); x_monom x sage: M._coerce_(x_monom) # indirect doctest x
Coerce elements from BooleanMonomialMonoids where the generators of self include the generators of the other monoid.
sage: from polybori import BooleanMonomialMonoid sage: R.<z,y> = BooleanPolynomialRing(2) sage: N = BooleanMonomialMonoid(R) sage: m = M._coerce_(N(y*z)); m y*z sage: m.parent() is M True
TESTS:
sage: from polybori import BooleanMonomialMonoid sage: R.<t,y> = BooleanPolynomialRing(2) sage: N = BooleanMonomialMonoid(R) sage: m = M._coerce_(N(y)); m Traceback (most recent call last): ... ValueError: cannot coerce monomial y to MonomialMonoid of Boolean PolynomialRing in x, y, z: name t not defined
sage: from polybori import BooleanMonomialMonoid sage: R.<t,x,y,z> = BooleanPolynomialRing(4) sage: N = BooleanMonomialMonoid(R) sage: m = M._coerce_(N(x*y*z)); m Traceback (most recent call last): ... TypeError: coercion from <type 'sage.rings.polynomial.pbori.BooleanMonomial'> to MonomialMonoid of Boolean PolynomialRing in x, y, z not implemented
) |
sage: from polybori import BooleanMonomialMonoid sage: P.<x,y> = BooleanPolynomialRing(2) sage: M = BooleanMonomialMonoid(P) sage: M # indirect doctest MonomialMonoid of Boolean PolynomialRing in x, y
Class: BooleanMonomialVariableIterator
Functions: next
) |
Special Functions: __iter__,
__next__
) |
Return an iterator over the variables of a boolean monomial.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: for m in f: list(m)# indirect doctest [x, y] [z] []
) |
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: m = f.lm() sage: iter(m).next() x
Class: BooleanPolynomial
Functions: constant,
deg,
degree,
elength,
firstTerm,
gradedPart,
hasConstantPart,
is_constant,
is_equal,
is_homogeneous,
is_one,
is_unit,
is_zero,
isOne,
isZero,
lead,
lexLead,
lexLmDeg,
lm,
lm_degree,
lmDeg,
lmDivisors,
lt,
mapEveryXToXPlusOne,
monomial_coefficient,
monomials,
navigation,
nNodes,
nvariables,
nVars,
reducibleBy,
ring,
set,
spoly,
stableHash,
subs,
total_degree,
totalDegree,
variables,
vars,
zeroesIn
) |
Return True
if this element is constant.
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: x.constant() False
sage: B(1).constant() True
) |
Return the degree of self
. This is usually equivalent
to the total degree except for weighted term orderings which
are not implemented yet.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: (x+y).degree() 1
sage: P(1).degree() 0
sage: (x*y + x + y + 1).degree() 2
) |
Return the total degree of self.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: (x+y).degree() 1
sage: P(1).degree() 0
sage: (x*y + x + y + 1).degree() 2
) |
Return elimination length as used in the SlimGB algorithm.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: x.elength() 1 sage: f = x*y + 1 sage: f.elength() 2
REFERENCES: Michael Brickenstein; SlimGB: Groebner Bases with Slim Polynomials http://www.mathematik.uni-kl.de/~zca/Reports_on_ca/35/paper_35_full.ps.gz
) |
Return the first term with respect to the lexicographical term ordering.
sage: B.<a,b,z> = BooleanPolynomialRing(3,order='lex') sage: f = b*z + a + 1 sage: f.firstTerm() a
) |
Return graded part of this boolean polynomial of degree deg.
Input:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b*c + c*d + a*b + 1 sage: f.gradedPart(2) a*b + c*d
sage: f.gradedPart(0) 1
TESTS:
sage: f.gradedPart(-1) 0
) |
Return True
if this boolean polynomial has a constant
part, i.e. if
is a term.
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b*c + c*d + a*b + 1 sage: f.hasConstantPart() True
sage: f = a*b*c + c*d + a*b sage: f.hasConstantPart() False
) |
Check if self is constant.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P(1).is_constant() True
sage: P(0).is_constant() True
sage: x.is_constant() False
sage: (x*y).is_constant() False
) |
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*z + b + 1 sage: g = b + z sage: f.is_equal(g) False
sage: f.is_equal( (f + 1) - 1 ) True
) |
Return True
if this element is a homogeneous
polynomial.
sage: P.<x, y> = BooleanPolynomialRing() sage: (x+y).is_homogeneous() True sage: P(0).is_homogeneous() True sage: (x+1).is_homogeneous() False
) |
Check if self is 1.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P(1).is_one() True
sage: P.one_element().is_one() True
sage: x.is_one() False
sage: P(0).is_one() False
) |
Check if self is invertible in the parent ring.
Note that this condition is equivalent to being 1 for boolean polynomials.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P.one_element().is_unit() True
sage: x.is_unit() False
) |
Check if self
is zero.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P(0).is_zero() True
sage: x.is_zero() False
sage: P(1).is_zero() False
) |
Return True
if this element is one.
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: x.isOne() False sage: B(0).isOne() False sage: B(1).isOne() True
) |
Return True
if this element is zero.
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: x.isZero() False sage: B(0).isZero() True sage: B(1).isZero() False
) |
Return the leading monomial of boolean polynomial, with respect to to the order of parent ring.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: (x+y+y*z).lead() x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: (x+y+y*z).lead() y*z
) |
Return the leading monomial of boolean polynomial, with respect to the lexicographical term ordering..
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: (x+y+y*z).lexLead() x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: (x+y+y*z).lexLead() x
) |
Return degree of leading monomial with respect to the lexicographical ordering.
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='lex') sage: f = x + y*z sage: f x + y*z sage: f.lexLmDeg() 1
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex') sage: f = x + y*z sage: f y*z + x sage: f.lexLmDeg() 1
) |
Return the leading monomial of boolean polynomial, with respect to the order of parent ring.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: (x+y+y*z).lm() x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: (x+y+y*z).lm() y*z
) |
Returns the total degree of the leading monomial of self.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: p = x + y*z sage: p.lm_degree() 1
sage: P.<x,y,z> = BooleanPolynomialRing(3,order='deglex') sage: p = x + y*z sage: p.lm_degree() 2
sage: P(0).lm_degree() 0
) |
Return the degree of the leading monomial with respect to the lexicographical orderings.
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='lex') sage: f = x + y*z sage: f x + y*z sage: f.lmDeg() 1
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex') sage: f = x + y*z sage: f y*z + x sage: f.lmDeg() 2
) |
Return a BooleSet
of all divisors of the leading
monomial.
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*b + z + 1 sage: f.lmDivisors() {{a,b}, {a}, {b}, {}}
) |
Return the leading term of this boolean polynomial, with respect to the order of the parent ring.
Note that for boolean polynomials this is equivalent to returning leading monomials.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: (x+y+y*z).lt() x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: (x+y+y*z).lt() y*z
) |
Map every variable x_i in this polynomial to
.
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*b + z + 1; f a*b + z + 1 sage: f.mapEveryXToXPlusOne() a*b + a + b + z + 1 sage: f(a+1,b+1,z+1) a*b + a + b + z + 1
) |
Return the coefficient of the monomial mon in
self
, where mon must have the same parent as
self
.
Input:
sage: P.<x,y> = BooleanPolynomialRing(2) sage: x.monomial_coefficient(x) 1 sage: x.monomial_coefficient(y) 0 sage: R.<x,y,z,a,b,c>=BooleanPolynomialRing(6) sage: f=(1-x)*(1+y); f x*y + x + y + 1
sage: f.monomial_coefficient(1) 1
sage: f.monomial_coefficient(0) 0
) |
Return a list of monomials appearing in self
ordered
largest to smallest.
sage: P.<a,b,c> = BooleanPolynomialRing(3,order='lex') sage: f = a + c*b sage: f.monomials() [a, b*c]
sage: P.<a,b,c> = BooleanPolynomialRing(3,order='degrevlex') sage: f = a + c*b sage: f.monomials() [c*b, a]
) |
Return the number of variables used to form this boolean polynomial.
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b*c + 1 sage: f.nvariables() 3
) |
Return the number of variables used to form this boolean polynomial.
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b*c + 1 sage: f.nVars() 3
) |
Return True
if this boolean polynomial is reducible by
the polynomial rhs.
Input:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4,order='degrevlex') sage: f = (a*b + 1)*(c + 1) sage: f.reducibleBy(d) False sage: f.reducibleBy(c) True sage: f.reducibleBy(c + 1) True
) |
Return the parent of this boolean polynomial.
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: a.ring() is B True
) |
Return a BooleSet
with all monomials apprearing in this
polynomial.
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: (a*b+z+1).set() {{a,b}, {z}, {}}
) |
Return the S-Polynomial of this boolean polynomial and the other boolean polynomial rhs.
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b*c + c*d + a*b + 1 sage: g = c*d + b sage: f.spoly(g) a*b + a*c*d + c*d + 1
) |
Fixes some given variables in a given boolean polynomial and
returns the changed boolean polynomials. The polynomial itself
is not affected. The variable,value pairs for fixing are to be
provided as dictionary of the form {variable:value}
or named parameters (see examples below).
Input:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + y*z + 1 sage: f.subs(x=1) y*z + y + z + 1 sage: f.subs(x=0) y*z + z + 1
sage: f.subs(x=y) y*z + y + z + 1
sage: f.subs({x:1},y=1) 0 sage: f.subs(y=1) x + 1 sage: f.subs(y=1,z=1) x + 1 sage: f.subs(z=1) x*y + y sage: f.subs({'x':1},y=1) 0
This method can work fully symbolic:
sage: f.subs(x=var('a'),y=var('b'),z=var('c')) # long time -- requires lots of RAM b*c + c + a*b + 1
sage: f.subs({'x':var('a'),'y':var('b'),'z':var('c')}) # long time -- requires lots of RAM b*c + c + a*b + 1
) |
Return the total degree of self.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: (x+y).total_degree() 1
sage: P(1).total_degree() 0
sage: (x*y + x + y + 1).total_degree() 2
) |
Return total degree of this boolean polynomial.
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b*c + 1 sage: f.totalDegree() 3
) |
Return a list of all variables appearing in self
.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: (x + y).variables() [x, y]
sage: (x*y + z).variables() [x, y, z]
sage: P.zero_element().variables() []
sage: P.one_element().variables() [1]
) |
Return a boolean monomial with all the variables appearing in
self
.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: (x + y).vars() x*y
sage: (x*y + z).vars() x*y*z
sage: P.zero_element().vars() 1
sage: P.one_element().vars() 1
TESTS:
sage: R = BooleanPolynomialRing(1, 'y') sage: y.vars() y sage: R Boolean PolynomialRing in y
Special Functions: __call__,
__eq__,
__ge__,
__gt__,
__init__,
__iter__,
__le__,
__len__,
__lt__,
__ne__,
__neg__,
__pow__,
__reduce__,
__rpow__,
_magma_,
_repr_,
_repr_with_changed_varnames
) |
Evaluate this boolean polynomials.
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: f(0,1,1) 0 sage: f(z,y,x) x + y*z + 1 sage: f(x=z) y*z + z + 1
sage: P.<a,b,c> = PolynomialRing(QQ) sage: f(a,b,c) a*b + c + 1 sage: f(x=a,y=b,z=1) a*b + 2
Evaluation of polynomials can be used fully symbolic:
sage: f(x=var('a'),y=var('b'),z=var('c')) # long time -- requires lots of RAM c + a*b + 1 sage: f(var('a'),var('b'),1) # long time -- requires lots of RAM a*b
) |
Return an iterator over the monomials of self
, in the order of
the parent ring.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: p = x + z + x*y + y*z + x*y*z sage: list(iter(p)) [x*y*z, x*y, x, y*z, z]
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: p = x + z + x*y + y*z + x*y*z sage: list(iter(p)) [x*y*z, x*y, y*z, x, z]
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='degrevlex') sage: p = x + z + x*y + y*z + x*y*z sage: list(iter(p)) [z*y*x, y*x, z*y, x, z]
TESTS:
sage: R = BooleanPolynomialRing(1,'y') sage: list(iter(y)) [y] sage: R Boolean PolynomialRing in y
) |
Return -self.
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*z + b + 1 sage: -f a*z + b + 1
) |
sage: P.<a,b> = BooleanPolynomialRing(2) sage: loads(dumps(a)) == a True
) |
Returns the MAGMA representation of self.
sage: R.<x,y> = BooleanPolynomialRing() sage: f = y*x + x +1 sage: f._magma_() #optional x*y + x + 1
) |
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: repr(a+b+z^2+1) # indirect doctest 'a + b + z + 1'
) |
Return string representing this boolean polynomial but change the variable names to varnames.
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: a._repr_with_changed_varnames(['x','y','z']) 'x'
TESTS:
sage: a._repr_with_changed_varnames([1,'y','z']) Traceback (most recent call last): ... TypeError: varnames has entries with wrong type.
sage: a a
Class: BooleanPolynomialIdeal
Functions: groebner_basis
) |
Return a Groebner basis of this ideal.
selection_size, maximum number of polynomials for parallel reductions
Input:
False
or an
ordering code. In practice, many
Boolean examples have very few
solutions and a very easy Groebner
basis. So, a complex walk
algorithm (which cannot be
implemented using the POLYBORI
data structures) seems
unnecessary, as such Groebner bases
can be converted quite fast by the
normal Buchberger algorithm from
one ordering into another
ordering.
(default: False
)
True
)
True
)
True
)
False
)
True
linear algebra takes
affect in this
block.(default: True)
heuristic=False
(default: True
)
True
)
invert=True
input and output get
a transformation
sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4) sage: I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) sage: I.groebner_basis() [x0*x1 + x0*x2 + x0, x0*x2*x3 + x0*x3]
Special Functions: __init__
) |
Construct an ideal in the boolean polynomial ring.
Input:
True
)
sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4) sage: I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) sage: I Ideal (x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) of Boolean PolynomialRing in x0, x1, x2, x3
Class: BooleanPolynomialIterator
Functions: next
) |
Special Functions: __iter__,
__next__
) |
sage: B.<a,b,c,d> = BooleanPolynomialRing() sage: list(B.random_element()) # indirect doctest [a*c, a*d, a, b*d, 1]
) |
sage: B.<a,b,c,d> = BooleanPolynomialRing() sage: it = iter(B.random_element()) sage: it.next() # indirect doctest a*c
Class: BooleanPolynomialRing
Functions: cover_ring,
defining_ideal,
gen,
gens,
ideal,
ngens,
random_element
) |
Return
if
is the ordered list of
variable names of this ring.
also has the same term
ordering as this ring.
sage: B.<x,y> = BooleanPolynomialRing(2) sage: R = B.cover_ring(); R Multivariate Polynomial Ring in x, y over Finite Field of size 2
sage: B.term_order() == R.term_order() True
) |
Return
where
,
the ordered list of variables/variable names of this
ring and
any element in
.
sage: B.<x,y> = BooleanPolynomialRing(2) sage: I = B.defining_ideal(); I Ideal (x^2 + x, y^2 + y) of Multivariate Polynomial Ring in x, y over Finite Field of size 2
) |
Returns the i-th generator of self.
Input:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P.gen() x sage: P.gen(2) z
TESTS:
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='dp') sage: P.gen(0) x
) |
Return the tuple of variables in this ring.
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P.gens() (x, y, z)
sage: P = BooleanPolynomialRing(10,'x') sage: P.gens() (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9)
TESTS:
sage: P.<x,y,z> = BooleanPolynomialRing(3,order='degrevlex') sage: P.gens() (x, y, z)
) |
Create an ideal in this ring.
Input:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P.ideal(x+y) Ideal (x + y) of Boolean PolynomialRing in x, y, z
sage: P.ideal(x*y, y*z) Ideal (x*y, y*z) of Boolean PolynomialRing in x, y, z
sage: P.ideal([x+y, z]) Ideal (x + y, z) of Boolean PolynomialRing in x, y, z
) |
Returns the number of variables in self.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P.ngens() 2
sage: P = BooleanPolynomialRing(1000, 'x') sage: P.ngens() 1000
) |
Return a random boolean polynomial. Generated polynomial has the given number of terms, and at most given degree.
Input:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P.random_element(degree=3, terms=4) x*y*z + x*z + y*z + z
sage: P.random_element(degree=1, terms=2) z + 1
TESTS:
sage: P.random_element(degree=4) Traceback (most recent call last): ... ValueError: Given degree should be less than or equal to number of variables (3)
sage: t = P.random_element(degree=1, terms=5) Traceback (most recent call last): ... ValueError: Cannot generate random polynomial with 5 terms and maximum degree 1 using 3 variables
sage: t = P.random_element(degree=2,terms=5,vars_set=(0,1)) Traceback (most recent call last): ... ValueError: Cannot generate random polynomial with 5 terms using 2 variables
Special Functions: __call__,
__eq__,
__ge__,
__gt__,
__init__,
__le__,
__lt__,
__ne__,
__reduce__,
_change_ordering,
_magma_,
_magma_init_,
_random_monomial_dfirst,
_random_monomial_uniform,
_random_uniform_rec,
_repr_,
_set_variable_name,
_singular_init_
) |
Convert elements of other objects to this boolean polynomial ring.
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P(5) 1
sage: P(x+y) x + y
sage: P.<x,y> = BooleanPolynomialRing(2) sage: R = BooleanPolynomialRing(1,'y') sage: p = R(y); p y sage: p.parent() Boolean PolynomialRing in y
sage: P = BooleanPolynomialRing(2,'x,y') sage: R.<z,x,y> = ZZ['z,x,y'] sage: t = x^2*y + 5*y^3 sage: p = P(t); p x*y + y sage: p.parent() Boolean PolynomialRing in x, y
TESTS:
sage: P.<x,y> = BooleanPolynomialRing(2) sage: R = BooleanPolynomialRing(1,'y') sage: p = R(x+y+x*y+1) Traceback (most recent call last): ... ValueError: cannot convert polynomial x*y + x + y + 1 to Boolean PolynomialRing in y: name x not defined
sage: P = BooleanPolynomialRing(2,'x,y') sage: R.<z,x,y> = ZZ['z,x,y'] sage: t = x^2*z+5*y^3 sage: p = P(t) Traceback (most recent call last): ... ValueError: cannot convert polynomial z*x^2 + 5*y^3 to Boolean PolynomialRing in x, y: name z not defined
) |
sage: P.<a,b> = BooleanPolynomialRing(2) sage: loads(dumps(P)) == P # indirect doctest True
) |
Change the ordering of this boolean polynomial ring. Do NOT call this method, unless you know very well what you are doing.
Input:
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex') sage: y*z > x True
Now we call the internal method and change the ordering to 'lex':
sage: B._change_ordering(0) sage: y*z > x False
However, this change is not - and should not be - picked up by the public interface.
sage: B.term_order() Degree lexicographic term order
WARNING: Do not use this method. It is provided for compatibility reasons with POLYBORI but parents are supposed to be immutable in Sage.
) |
Return a MAGMA representation of this boolean polynomial ring.
Input:
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: B._magma_() # optional requires magma Affine Algebra of rank 3 over GF(2) Lexicographical Order Variables: x, y, z Quotient relations: [ x^2 + x, y^2 + y, z^2 + z ]
) |
Return a a string which when evaluated with MAGMA returns a MAGMA representaion of this boolean polynomial ring.
Input:
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: B._magma_() # optional requires magma, indirect doctest Affine Algebra of rank 3 over GF(2) Lexicographical Order Variables: x, y, z Quotient relations: [ x^2 + x, y^2 + y, z^2 + z ]
NOTE: This method actually calls MAGMA.
) |
Choose a random monomial using variables indexed in
vars_set
up to given degree
. The degree of the
monomial,
, is chosen uniformly in the interval [0,degree]
first, then the monomial is generated by selecting a random
sample of size
from
vars_set
.
Input:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: [P._random_monomial_dfirst(3, (0,1,2)) for _ in range(10)] [x*y*z, x*y*z, x*y*z, y*z, x*z, z, z, y*z, x*y*z, 1]
) |
Choose a random monomial uniformly from set of monomials in
the variables indexed by vars_set
in self.
Input:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: [P._random_monomial_uniform([1, 3, 4], (0,1)) for _ in range(10)] [x*y, x*y, x, x, x, x*y, x, y, x*y, 1]
) |
Recursively generate a random polynomial in in this ring,
using the variables from vars_set
.
Input:
True
choose degree first, otherwise
choose the monomial uniformly
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P._random_uniform_rec(2, [1, 3, 4], (0,1), True, 2) x + y sage: P._random_uniform_rec(2, [1, 3, 4], (0,1), True, 2) 0
) |
sage: P.<x, y> = BooleanPolynomialRing(2) sage: P # indirect doctest Boolean PolynomialRing in x, y
) |
Set variable name of i-th variable to s.
This function is used by POLYBORI python functions.
Input:
sage: P.<x0,x1> = BooleanPolynomialRing(2) sage: P Boolean PolynomialRing in x0, x1
sage: P._set_variable_name(0, 't') sage: P Boolean PolynomialRing in t, x1
WARNING: Do not use this method. It is provided for compatibility reasons with POLYBORI but parents are supposed to be immutable in Sage.
) |
Return a newly created SINGULAR quotient ring matching this boolean polynomial ring.
NOTE & TODO: This method does not only return a string but actually calls SINGULAR.
sage: B.<x,y> = BooleanPolynomialRing(2) sage: B._singular_() // characteristic : 2 // number of vars : 2 // block 1 : ordering lp // : names x y // block 2 : ordering C // quotient ring from ideal _[1]=x2+x _[2]=y2+y
Class: BooleanPolynomialVector
Functions: append
Special Functions: __getitem__,
__init__,
__iter__,
__len__
) |
) |
Class: BooleanPolynomialVectorIterator
Functions: next
) |
Special Functions: __iter__,
__next__
) |
) |
Class: BooleSet
Functions: cartesianProduct,
change,
diff,
divide,
empty,
includeDivisors,
minimalElements,
navigation,
nNodes,
nSupport,
ring,
set,
stableHash,
subset0,
subset1,
union,
vars
) |
Return the cartesian product of this set and the set rhs.
The Cartesian product of two sets X and Y is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y.
sage: B = BooleanPolynomialRing(5,'x') sage: x0,x1,x2,x3,x4 = B.gens() sage: f = x1*x2+x2*x3 sage: s = f.set(); s {{x1,x2}, {x2,x3}} sage: g = x4 + 1 sage: t = g.set(); t {{x4}, {}} sage: s.cartesianProduct(t) {{x1,x2,x4}, {x1,x2}, {x2,x3,x4}, {x2,x3}}
) |
Return the set theoretic difference of this set and the set rhs.
The difference of two sets
and
is defined as:
sage: B = BooleanPolynomialRing(5,'x') sage: x0,x1,x2,x3,x4 = B.gens() sage: f = x1*x2+x2*x3 sage: s = f.set(); s {{x1,x2}, {x2,x3}} sage: g = x2*x3 + 1 sage: t = g.set(); t {{x2,x3}, {}} sage: s.diff(t) {{x1,x2}}
) |
Return True
if this set is empty.
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: BS = (a*b + c).set() sage: BS.empty() False
sage: BS = B(0).set() sage: BS.empty() True
) |
Navigators provide an interface to diagram nodes, accessing their index as well as the corresponding then- and else-branches.
You should be very careful and always keep a reference to the original object, when dealing with navigators, as navigators contain only a raw pointer as data. For the same reason, it is necessary to supply the ring as argument, when constructing a set out of a navigator.
sage: from polybori import BooleSet sage: B = BooleanPolynomialRing(5,'x') sage: x0,x1,x2,x3,x4 = B.gens() sage: f = x1*x2+x2*x3*x4+x2*x4+x3+x4+1 sage: s = f.set(); s {{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}
sage: nav = s.navigation() sage: BooleSet(nav,s.ring()) {{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}
sage: nav.value() 1
sage: nav_else = nav.elseBranch()
sage: BooleSet(nav_else,s.ring()) {{x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}
sage: nav_else.value() 2
) |
Return the number of nodes in the ZDD.
sage: B = BooleanPolynomialRing(5,'x') sage: x0,x1,x2,x3,x4 = B.gens() sage: f = x1*x2+x2*x3 sage: s = f.set(); s {{x1,x2}, {x2,x3}} sage: s.nNodes() 4
) |
Return the parent ring.
sage: B = BooleanPolynomialRing(5,'x') sage: x0,x1,x2,x3,x4 = B.gens() sage: f = x1*x2+x2*x3*x4+x2*x4+x3+x4+1 sage: f.set().ring() is B True
) |
Return self
.
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: BS = (a*b + c).set() sage: BS.set() is BS True
) |
Return the set theoretic union of this set and the set rhs.
The union of two sets
and
is defined as:
sage: B = BooleanPolynomialRing(5,'x') sage: x0,x1,x2,x3,x4 = B.gens() sage: f = x1*x2+x2*x3 sage: s = f.set(); s {{x1,x2}, {x2,x3}} sage: g = x2*x3 + 1 sage: t = g.set(); t {{x2,x3}, {}} sage: s.diff(t) {{x1,x2}}
Special Functions: __contains__,
__init__,
__iter__,
__len__,
__mod__,
__repr__,
__rmod__
) |
Create an iterator over elements of self.
sage: P.<x, y> = BooleanPolynomialRing(2) sage: f = x*y+x+y+1; s = f.set() sage: list(s) [x*y, x, y, 1]
) |
) |
sage: from polybori import BooleSet sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: BS = BooleSet(B) sage: repr(BS) # indirect doctest '{}'
Class: BooleSetIterator
Functions: next
) |
Special Functions: __iter__,
__next__
) |
) |
sage: B.<a,b,c,d> = BooleanPolynomialRing() sage: f = B.random_element() sage: f a*c + a*d + a + b*d + 1 sage: it = iter(f.set()) sage: it.next() a*c
Class: BooleVariable
Class: CCuddNavigator
Functions: constant,
elseBranch,
terminalOne,
thenBranch,
value
Special Functions: __call__
) |
Class: DD
Functions: empty,
navigation,
subset0,
subset1,
union
Special Functions: __call__
) |
Class: GroebnerStrategy
Functions: addAsYouWish,
addGenerator,
addGeneratorDelayed,
allGenerators,
allSpolysInNextDegree,
cleanTopByChainCriterion,
containsOne,
faugereStepDense,
implications,
llReduceAll,
minimalize,
minimalizeAndTailReduce,
nextSpoly,
nf,
npairs,
select,
smallSpolysInNextDegree,
someSpolysInNextDegree,
suggestPluginVariable,
symmGB_F2,
topSugar,
variableHasValue
Special Functions: __delattr__,
__getattribute__,
__getitem__,
__init__,
__len__
) |
Class: VariableBlock_base
Special Functions: __init__
Class: VariableBlockFalse
Special Functions: __call__,
__init__
) |
Class: VariableBlockTrue
Special Functions: __call__,
__init__
) |
See About this document... for information on suggesting changes.