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}