001/*
002 * $Id: WordReduction.java 4149 2012-09-01 09:01:54Z kredel $
003 */
004
005package edu.jas.gb;
006
007import java.util.List;
008
009import java.io.Serializable;
010
011import edu.jas.poly.Word;
012import edu.jas.poly.GenWordPolynomial;
013import edu.jas.structure.RingElem;
014
015
016/**
017 * Polynomial WordReduction interface.
018 * Defines S-Polynomial, normalform, module criterion
019 * and irreducible set.
020 * @param <C> coefficient type
021 * @author Heinz Kredel
022 */
023
024public interface WordReduction<C extends RingElem<C>> 
025                 extends Serializable {
026
027
028    /**
029     * S-Polynomials of non-commutative polynomials.
030     * @param Ap word polynomial.
031     * @param Bp word polynomial.
032     * @return list of all spol(Ap,Bp) the S-polynomials of Ap and Bp.
033     */
034    public List<GenWordPolynomial<C>> SPolynomials(GenWordPolynomial<C> Ap, 
035                                                   GenWordPolynomial<C> Bp);
036
037
038    /**
039     * S-Polynomials of non-commutative polynomials.
040     * @param a leading base coefficient of B.
041     * @param l1 word.
042     * @param A word polynomial.
043     * @param r1 word.
044     * @param b leading base coefficient of A.
045     * @param l2 word.
046     * @param B word polynomial.
047     * @param r2 word.
048     * @return list of all spol(Ap,Bp) the S-polynomials of Ap and Bp.
049     */
050    public GenWordPolynomial<C> SPolynomial(C a, Word l1, GenWordPolynomial<C> A, Word r1,
051                                            C b, Word l2, GenWordPolynomial<C> B, Word r2);
052
053
054    /**
055     * Is top reducible.
056     * Condition is lt(B) | lt(A) for some B in F.
057     * @param A polynomial.
058     * @param P polynomial list.
059     * @return true if A is top reducible with respect to P.
060     */
061    public boolean isTopReducible(List<GenWordPolynomial<C>> P, 
062                                  GenWordPolynomial<C> A);
063
064
065    /**
066     * Is reducible.
067     * @param A polynomial.
068     * @param P polynomial list.
069     * @return true if A is reducible with respect to P.
070     */
071    public boolean isReducible(List<GenWordPolynomial<C>> P, 
072                               GenWordPolynomial<C> A);
073
074
075    /**
076     * Is in Normalform.
077     * @param A polynomial.
078     * @param P polynomial list.
079     * @return true if A is in normalform with respect to P.
080     */
081    public boolean isNormalform(List<GenWordPolynomial<C>> P, 
082                                GenWordPolynomial<C> A);
083
084
085    /**
086     * Is in Normalform.
087     * @param Pp polynomial list.
088     * @return true if each A in Pp is in normalform with respect to Pp\{A}.
089     */
090    public boolean isNormalform( List<GenWordPolynomial<C>> Pp );
091
092
093    /**
094     * Normalform.
095     * @param A polynomial.
096     * @param P polynomial list.
097     * @return nf(A) with respect to P.
098     */
099    public GenWordPolynomial<C> normalform(List<GenWordPolynomial<C>> P, 
100                                           GenWordPolynomial<C> A);
101
102
103    /**
104     * Normalform Set.
105     * @param Ap polynomial list.
106     * @param Pp polynomial list.
107     * @return list of nf(a) with respect to Pp for all a in Ap.
108     */
109    public List<GenWordPolynomial<C>> normalform(List<GenWordPolynomial<C>> Pp, 
110                                                 List<GenWordPolynomial<C>> Ap);
111
112
113    /**
114     * Normalform with left and right recording.
115     * @param lrow left recording matrix, is modified.
116     * @param rrow right recording matrix, is modified.
117     * @param Pp a polynomial list for reduction.
118     * @param Ap a polynomial.
119     * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
120     */
121    public GenWordPolynomial<C> 
122           normalform(List<GenWordPolynomial<C>> lrow, List<GenWordPolynomial<C>> rrow,
123                      List<GenWordPolynomial<C>> Pp, GenWordPolynomial<C> Ap);
124
125
126    /**
127     * Irreducible set.
128     * @param Pp polynomial list.
129     * @return a list P of polynomials which are in normalform wrt. P and with ideal(Pp) = ideal(P).
130     */
131    public List<GenWordPolynomial<C>> irreducibleSet(List<GenWordPolynomial<C>> Pp);
132
133
134    /**
135     * Is reduction of normal form.
136     * @param lrow left recording matrix.
137     * @param rrow right recording matrix.
138     * @param Pp a polynomial list for reduction.
139     * @param Ap a polynomial.
140     * @param Np nf(Pp,Ap), a normal form of Ap wrt. Pp.
141     * @return true, if Np + sum( row[i]*Pp[i] ) == Ap, else false.
142     */
143    public boolean isReductionNF(List<GenWordPolynomial<C>> lrow, List<GenWordPolynomial<C>> rrow, 
144                                 List<GenWordPolynomial<C>> Pp, 
145                                 GenWordPolynomial<C> Ap, GenWordPolynomial<C> Np);
146
147}