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