Changeset 83be980 in git

Timestamp:

Jul 2, 2012, 7:26:50 AM (12 years ago)

Author:

Christian Eder

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

1bc7d4ac8a4fd3280459ab78ca65bd4e60dd2c93

Parents:

cffd3e2f630fbc7b0e35afee97d6fa948cfd0b3e

git-author:

Christian Eder <ederc@mathematik.uni-kl.de>2012-07-02 07:26:50+02:00

git-committer:

Christian Eder <ederc@mathematik.uni-kl.de>2012-07-05 16:12:50+02:00

Message:

adds signature-based algorithm files from master, does not build right now:
fixes kstd1.cc for compilation

Location:

kernel

Files:

• kstd1.cc (modified) (2 diffs)
• kstd1.h (modified) (1 diff)
• kstd2.cc (modified) (4 diffs)
• kutil.cc (modified) (13 diffs)
• kutil.h (modified) (16 diffs)

kernel/kstd1.cc

@@ -1098 +1098 @@
 }
 
+
+void initSba(ideal F,kStrategy strat)
+{
+  int i;
+  //idhdl h;
+ /* setting global variables ------------------- */
+  strat->enterS = enterSSba;
+    strat->red2 = redHoney;
+  if (strat->honey)
+    strat->red2 = redHoney;
+  else if (currRing->pLexOrder && !strat->homog)
+    strat->red2 = redLazy;
+  else
+  {
+    strat->LazyPass *=4;
+    strat->red2 = redHomog;
+  }
+#ifdef HAVE_RINGS  //TODO Oliver
+  if (rField_is_Ring(currRing))
+  {
+    strat->red2 = redRing;
+  }
+#endif
+  if (currRing->pLexOrder && strat->honey)
+    strat->initEcart = initEcartNormal;
+  else
+    strat->initEcart = initEcartBBA;
+  if (strat->honey)
+    strat->initEcartPair = initEcartPairMora;
+  else
+    strat->initEcartPair = initEcartPairBba;
+  //strat->kIdeal = NULL;
+  //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
+  //else              strat->kIdeal->rtyp=MODUL_CMD;
+  //strat->kIdeal->data=(void *)strat->Shdl;
+  if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
+  {
+    //interred  machen   Aenderung
+    strat->pOrigFDeg  = currRing->pFDeg;
+    strat->pOrigLDeg  = currRing->pLDeg;
+    //h=ggetid("ecart");
+    //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
+    //{
+    //  ecartWeights=iv2array(IDINTVEC(h));
+    //}
+    //else
+    {
+      ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
+      /*uses automatic computation of the ecartWeights to set them*/
+      kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights, currRing);
+    }
+    pRestoreDegProcs(currRing, totaldegreeWecart, maxdegreeWecart);
+    if (TEST_OPT_PROT)
+    {
+      for(i=1; i<=(currRing->N); i++)
+        Print(" %d",ecartWeights[i]);
+      PrintLn();
+      mflush();
+    }
+  }
+  // for sig-safe reductions in signature-based
+  // standard basis computations
+  strat->red          = redSig;
+  //strat->incremental  = TRUE;
+  strat->currIdx      = 1;
+}
+
 void initMora(ideal F,kStrategy strat)
 {
@@ -1795 +1862 @@
       else
         r=bba(F,Q,NULL,hilb,strat);
+    }
+  }
+#ifdef KDEBUG
+  idTest(r);
+#endif
+  if (toReset)
+  {
+    kModW = NULL;
+    pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
+  }
+  currRing->pLexOrder = b;
+//Print("%d reductions canceled \n",strat->cel);
+  HCord=strat->HCord;
+  delete(strat);
+  if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
+  return r;
+}
+
+ideal kSba(ideal F, ideal Q, tHomog h,intvec ** w, int incremental, int arri, intvec *hilb,int syzComp,
+          int newIdeal, intvec *vw)
+{
+  if(idIs0(F))
+    return idInit(1,F->rank);
+
+  ideal r;
+  BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
+  BOOLEAN delete_w=(w==NULL);
+  kStrategy strat=new skStrategy;
+  if (incremental!=0)
+  {
+    strat->incremental = TRUE;
+  }
+  else
+  {
+    strat->incremental = FALSE;
+  }
+  if (arri!=0)
+  {
+    strat->rewCrit1 = arriRewDummy;
+    strat->rewCrit2 = arriRewCriterion;
+  }
+  else
+  {
+    strat->rewCrit1 = faugereRewCriterion;
+    strat->rewCrit2 = faugereRewCriterion;
+  }
+
+  if(!TEST_OPT_RETURN_SB)
+    strat->syzComp = syzComp;
+  if (TEST_OPT_SB_1)
+    strat->newIdeal = newIdeal;
+  if (rField_has_simple_inverse(currRing))
+    strat->LazyPass=20;
+  else
+    strat->LazyPass=2;
+  strat->LazyDegree = 1;
+  strat->enterOnePair=enterOnePairNormal;
+  strat->chainCrit=chainCritNormal;
+  strat->ak = id_RankFreeModule(F,currRing);
+  strat->kModW=kModW=NULL;
+  strat->kHomW=kHomW=NULL;
+  if (vw != NULL)
+  {
+    currRing->pLexOrder=FALSE;
+    strat->kHomW=kHomW=vw;
+    strat->pOrigFDeg = currRing->pFDeg;
+    strat->pOrigLDeg = currRing->pLDeg;
+    pSetDegProcs(currRing,kHomModDeg);
+    toReset = TRUE;
+  }
+  if (h==testHomog)
+  {
+    if (strat->ak == 0)
+    {
+      h = (tHomog)idHomIdeal(F,Q);
+      w=NULL;
+    }
+    else if (!TEST_OPT_DEGBOUND)
+    {
+      h = (tHomog)idHomModule(F,Q,w);
+    }
+  }
+  currRing->pLexOrder=b;
+  if (h==isHomog)
+  {
+    if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
+    {
+      strat->kModW = kModW = *w;
+      if (vw == NULL)
+      {
+        strat->pOrigFDeg = currRing->pFDeg;
+        strat->pOrigLDeg = currRing->pLDeg;
+        pSetDegProcs(currRing,kModDeg);
+        toReset = TRUE;
+      }
+    }
+    currRing->pLexOrder = TRUE;
+    if (hilb==NULL) strat->LazyPass*=2;
+  }
+  strat->homog=h;
+#ifdef KDEBUG
+  idTest(F);
+  idTest(Q);
+
+#if MYTEST
+  if (TEST_OPT_DEBUG)
+  {
+    PrintS("// kSTD: currRing: ");
+    rWrite(currRing);
+  }
+#endif
+
+#endif
+#ifdef HAVE_PLURAL
+  if (rIsPluralRing(currRing))
+  {
+    const BOOLEAN bIsSCA  = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
+    strat->no_prod_crit   = ! bIsSCA;
+    if (w!=NULL)
+      r = nc_GB(F, Q, *w, hilb, strat, currRing);
+    else
+      r = nc_GB(F, Q, NULL, hilb, strat, currRing);
+  }
+  else
+#endif
+#ifdef HAVE_RINGS
+  if (rField_is_Ring(currRing))
+    r=bba(F,Q,NULL,hilb,strat);
+  else
+#endif
+  {
+    if (currRing->OrdSgn==-1)
+    {
+      if (w!=NULL)
+        r=mora(F,Q,*w,hilb,strat);
+      else
+        r=mora(F,Q,NULL,hilb,strat);
+    }
+    else
+    {
+      if (w!=NULL)
+        r=sba(F,Q,*w,hilb,strat);
+      else
+                if (arri == 2)
+                {
+                        r=ssg(F,Q,NULL,hilb,strat);
+                }
+                if (arri == 3)
+                {
+                        r=ssgnoninc(F,Q,NULL,hilb,strat);
+                }
+                if (arri == 4)
+                {
+                        r=ssgincschreyer(F,Q,NULL,hilb,strat);
+                }
+                else
+                {
+                        r=sba(F,Q,NULL,hilb,strat);
+                }
     }
   }

kernel/kstd1.h

@@ -29 +29 @@
 /// NOTE: this is just a wrapper which sets currRing for the actual kNF call
 poly kNF (ideal F, ideal Q, poly p,int syzComp, int lazyReduce, const ring _currRing);
+ideal kSba(ideal F,ideal Q, tHomog h, intvec ** mw, int incremental=0, int arri=0, intvec *hilb=NULL,
+          int syzComp=0,int newIdeal=0, intvec *vw=NULL);
 
 ideal kStd(ideal F, ideal Q, tHomog h, intvec ** mw,intvec *hilb=NULL,

kernel/kstd2.cc

@@ -34 +34 @@
 #define PLURAL_INTERNAL_DECLARATIONS 1
 #endif
+
+#define DEBUGF50  0
+#define DEBUGF51  0
+
+#ifdef DEBUGF5
+#undef DEBUGF5
+//#define DEBUGF5 1
+#endif
+
+#define F5C       1
+#if F5C
+  #define F5CTAILRED 0
+#endif
+
 #include <kernel/kutil.h>
 #include <misc/options.h>
@@ -478 +492 @@
         h->Clear();
         return -1;
+      }
+    }
+  }
+}
+
+/*2
+*  reduction procedure for signature-based standard
+*  basis algorithms:
+*  all reductions have to be sig-safe!
+*
+*  2 is returned if and only if the pair is rejected by the rewritten criterion
+*  at exactly this point of the computations. This is the last possible point
+*  such a check can be done => checks with the biggest set of available
+*  signatures
+*/
+int redSig (LObject* h,kStrategy strat)
+{
+  if (strat->tl<0) return 1;
+  //if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
+  //printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
+  assume(h->FDeg == h->pFDeg());
+//#if 1
+#ifdef DEBUGF5
+  Print("------- IN REDSIG -------\n");
+  Print("p: ");
+  pWrite(pHead(h->p));
+  Print("p1: ");
+  pWrite(pHead(h->p1));
+  Print("p2: ");
+  pWrite(pHead(h->p2));
+  Print("---------------------------\n");
+#endif
+  poly h_p;
+  int i,j,at,pass, ii;
+  int start=0;
+  int sigSafe;
+  unsigned long not_sev;
+  long reddeg,d;
+
+  pass = j = 0;
+  d = reddeg = h->GetpFDeg();
+  h->SetShortExpVector();
+  int li;
+  h_p = h->GetLmTailRing();
+  not_sev = ~ h->sev;
+  loop
+  {
+    j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h, start);
+    if (j < 0)
+    {
+      return 1;
+    }
+
+    li = strat->T[j].pLength;
+    ii = j;
+    /*
+     * the polynomial to reduce with (up to the moment) is;
+     * pi with length li
+     */
+    i = j;
+#if 1
+    if (TEST_OPT_LENGTH)
+    loop
+    {
+      /*- search the shortest possible with respect to length -*/
+      i++;
+      if (i > strat->tl)
+        break;
+      if (li<=1)
+        break;
+      if ((strat->T[i].pLength < li)
+         &&
+          p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
+                               h_p, not_sev, strat->tailRing))
+      {
+        /*
+         * the polynomial to reduce with is now;
+         */
+        li = strat->T[i].pLength;
+        ii = i;
+      }
+    }
+    start = ii+1;
+#endif
+
+    /*
+     * end of search: have to reduce with pi
+     */
+#ifdef KDEBUG
+    if (TEST_OPT_DEBUG)
+    {
+      PrintS("red:");
+      h->wrp();
+      PrintS(" with ");
+      strat->T[ii].wrp();
+    }
+#endif
+    assume(strat->fromT == FALSE);
+//#if 1
+#ifdef DEBUGF5
+    Print("BEFORE REDUCTION WITH %d:\n",ii);
+    Print("--------------------------------\n");
+    pWrite(h->sig);
+    pWrite(strat->T[ii].sig);
+    pWrite(h->GetLmCurrRing());
+    pWrite(pHead(h->p1));
+    pWrite(pHead(h->p2));
+    pWrite(pHead(strat->T[ii].p));
+    Print("--------------------------------\n");
+    printf("INDEX OF REDUCER T: %d\n",ii);
+#endif
+    sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
+    // if reduction has taken place, i.e. the reduction was sig-safe
+    // otherwise start is already at the next position and the loop
+    // searching reducers in T goes on from index start
+//#if 1
+#ifdef DEBUGF5
+    Print("SigSAFE: %d\n",sigSafe);
+#endif
+    if (sigSafe != 3)
+    {
+      // start the next search for reducers in T from the beginning
+      start = 0;
+#ifdef KDEBUG
+      if (TEST_OPT_DEBUG)
+      {
+        PrintS("\nto ");
+        h->wrp();
+        PrintLn();
+      }
+#endif
+
+      h_p = h->GetLmTailRing();
+      if (h_p == NULL)
+      {
+        if (h->lcm!=NULL) pLmFree(h->lcm);
+#ifdef KDEBUG
+        h->lcm=NULL;
+#endif
+        return 0;
+      }
+      h->SetShortExpVector();
+      not_sev = ~ h->sev;
+      /*
+      * try to reduce the s-polynomial h
+      *test first whether h should go to the lazyset L
+      *-if the degree jumps
+      *-if the number of pre-defined reductions jumps
+      */
+      pass++;
+      if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
+      {
+        h->SetLmCurrRing();
+        at = strat->posInL(strat->L,strat->Ll,h,strat);
+        if (at <= strat->Ll)
+        {
+          int dummy=strat->sl;
+          if (kFindDivisibleByInS(strat, &dummy, h) < 0)
+          {
+            return 1;
+          }
+          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
+#ifdef KDEBUG
+          if (TEST_OPT_DEBUG)
+            Print(" lazy: -> L%d\n",at);
+#endif
+          h->Clear();
+          return -1;
+        }
       }
     }
@@ -1294 +1477 @@
   idTest(strat->Shdl);
 
+  return (strat->Shdl);
+}
+ideal ssgincschreyer (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
+{
+        int 
+                time_interred = 0, time_prepare = 0, time_reduction_search = 0, time_reduction = 0,
+                time_add_r = 0, time_filter_b = 0, time_add_b1_testings = 0, time_add_b1_insertion = 0,
+                time_add_b2 = 0;
+
+        time_from_last_call();
+        int current_input_idx = 0;
+        while (F->m[current_input_idx] == NULL && current_input_idx < IDELEMS(F))
+        {
+                ++current_input_idx;
+        }
+        ideal I0 = idInit(1);
+        if (current_input_idx >= IDELEMS(F))
+        {
+                return I0;
+        }
+        I0->m[0] = pCopy(F->m[current_input_idx]);
+        int zero_reductions = 0;
+        LabeledPoly::GvwLess gvw_less;
+  poly pEins = pOne();
+        for (current_input_idx +=1; current_input_idx < IDELEMS(F); ++current_input_idx)
+        {
+                if (!F->m[current_input_idx]) continue;
+                idDelDiv(I0);
+                idSkipZeroes(I0);
+#ifndef SSG_NO_INTERRED
+                std::sort(I0->m, I0->m+IDELEMS(I0), LmCompareForNonZeroPolys());
+                
+                ideal I0_tail_reduced = idInit(IDELEMS(I0));
+                //tail reducton
+                for(int n0 = IDELEMS(I0) - 1; n0 > 0; --n0)
+                {
+                        poly p_old = NULL;
+                        std::swap(p_old,I0->m[n0]);
+                        poly p_new = kNF(I0, Q, p_old);
+                        pDelete(&p_old);
+                        I0_tail_reduced->m[n0] = p_new;
+                }
+                std::swap(I0_tail_reduced->m[0], I0->m[0]);
+                idDelete(&I0);
+                I0 = I0_tail_reduced;
+#endif
+                time_interred += time_from_last_call();
+                LPolysByGvw R;
+                LPolysMuledBySig B;
+    //LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx]);
+    LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx], 
+    current_input_idx);
+                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
+                {
+                        R.push_back(LabeledPoly::CreateZeroSig(I0->m[n0]));
+                }
+                const LPolysByGvw::iterator first_zero_sig = R.begin();
+    /*
+                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
+                {
+      for (int m0 = n0-1; m0>=0; --m0)
+      {
+                          R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0], n0, I0->m[m0], m0));
+      }
+                }
+    */
+                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
+                {
+      //R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0]));
+                        R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0],current_input_idx+1,F->m[current_input_idx]));
+                }
+                                /*
+        printf("\nR-init = \n");
+                                for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
+                                {
+                                        printf("p = ");pWrite((*ir)->p_);
+                                        printf("s = ");pWrite((*ir)->s_monom_);
+                                }
+        */
+    LabeledPolyMuled bnew;
+    bnew.Init();
+    bnew.FillBy(pEins, *p);
+    LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
+    /*
+    const LPolysByGvw::iterator p_insert_pos =
+      R.insert(known_gvw_greater_p, p);
+    */
+    bool rejected = false;
+                SigMuledMinimumFinder b_min_finder(B);
+    /*
+    for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
+    {
+      if ((*ir2)->sig_divides(bnew))
+      {
+        rejected = true;
+        break;
+      }
+    }
+    */
+    if (!rejected)
+    {
+      B.push_back(bnew);
+      b_min_finder.UpdateBy(B.size() - 1);
+      bnew.Init();
+      //time_add_b1_insertion += time_from_last_call();
+    }
+    bnew.Release();
+                time_prepare += time_from_last_call();
+    // first test in B
+                        if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
+                        {
+                                break;
+                        }else{
+                                p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
+                                B.erase_and_move_from_back(b_min_finder.minimum_idx_);
+                        }
+                while(1)
+                {
+                        bool reduced_to_zero = false;
+                        LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
+#if 1
+      /*
+                        if (n ==  IDELEMS(F) - 1)
+                        {
+      */
+        /*
+        printf("\nR = \n");
+                                for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
+                                {
+                                        printf("p = ");pWrite((*ir)->p_);
+                                        printf("s = ");pWrite((*ir)->s_monom_);
+                                }
+                                printf("B = \n");
+                                for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
+                                {
+                                        printf("smuled = ");pWrite((*ib).smuled_monom_);
+          //printf("s = ");pWrite((*ib)->not_muled_.s_monom_);
+                                }
+        */
+                        /*
+      }
+      */
+#endif
+                        while(1)
+                        {
+        //printf("p to reduce = ");pWrite (p->p_);
+                                bool was_reduced = false;
+                                LPolysByGvw::iterator ir = --R.end();
+                                while(1)
+                                {
+                                        was_reduced = p->can_reduce_by(*ir);
+                                        if (was_reduced)
+                                        {
+                                                time_reduction_search += time_from_last_call();
+                                                p->reduce_by(*ir);
+                                                time_reduction += time_from_last_call();
+                                                break;
+                                        }
+                                        if (ir == known_gvw_greater_p) break;
+                                        --ir;
+                                }
+                                if (!was_reduced && ir != R.begin())
+                                {
+                                        --ir;
+                                        while(1)
+                                        {
+                                                if (!gvw_less(p, *ir))
+                                                {
+                                                        ++ir;
+                                                        break;
+                                                }
+                                                was_reduced = p->can_reduce_by(*ir);
+                                                if (was_reduced)
+                                                {
+                                                        time_reduction_search += time_from_last_call();
+                                                        p->reduce_by(*ir);
+                                                        time_reduction += time_from_last_call();
+                                                        break;
+                                                }
+                                                if (ir == R.begin()) break;
+                                                --ir;
+                                        }
+                                        known_gvw_greater_p = ir;
+                                }
+                                if (!was_reduced) break;
+                                reduced_to_zero = p->p_ == NULL;
+                                if (reduced_to_zero)
+                                {
+                                        ++zero_reductions;
+                                        known_gvw_greater_p = R.begin();
+                                        break;
+                                }
+                        }
+                        time_reduction_search += time_from_last_call();
+                        const LPolysByGvw::iterator p_insert_pos =
+                                R.insert(known_gvw_greater_p, p);
+                        time_add_r += time_from_last_call();
+                        SigMuledMinimumFinder b_min_finder(B);
+                        for(int i=0;i<B.size();)
+                        {
+                                LabeledPolyMuled& b = B[i];
+                                if (p->sig_divides(b) && gvw_less(p,b.not_muled_))
+                                {
+                                        b.Release();
+                                        B.erase_and_move_from_back(i);
+                                }else
+                                {
+                                        b_min_finder.UpdateBy(i);
+                                        ++i;
+                                }
+                        }
+                        time_filter_b += time_from_last_call();
+                        if (!reduced_to_zero)
+                        {
+                                LabeledPolyMuled bnew;
+                                bnew.Init();
+                                for(LPolysByGvw::const_iterator ir = --R.end();ir != p_insert_pos;--ir)
+                                {
+                                        bnew.FillBy((*ir)->p_, *p);
+                                        bool rejected = false;
+                                        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
+                                        {
+                                                if ((*ir2)->sig_divides(bnew))
+                                                {
+                                                        rejected = true;
+                                                        break;
+                                                }
+                                        }
+                                        time_add_b1_testings += time_from_last_call();
+                                        if (!rejected)
+                                        {
+                                                B.push_back(bnew);
+                                                b_min_finder.UpdateBy(B.size() - 1);
+                                                bnew.Init();
+                                                time_add_b1_insertion += time_from_last_call();
+                                        }
+                                }
+                                for(LPolysByGvw::const_iterator ir = R.begin();ir != p_insert_pos;++ir)
+                                {
+                                        if (!gvw_less(*ir, p)) break;
+                                        if ((*ir)->p_ == NULL) continue;
+                                        bool rejected = false;
+                                        bnew.FillBy(p->p_, *(*ir));
+                                        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != ir;++ir2)
+                                        {
+                                                if ((*ir2)->sig_divides(bnew))
+                                                {
+                                                        rejected = true;
+                                                        break;
+                                                }
+                                        }
+                                        if (!rejected)
+                                        {
+                                                B.push_back(bnew);
+                                                b_min_finder.UpdateBy(B.size() - 1);
+                                                bnew.Init();
+                                        }
+                                }
+                                bnew.Release();
+                                time_add_b2 += time_from_last_call();
+                        }
+      /*
+                                printf("B = \n");
+                                for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
+                                {
+                                        printf("smuled = ");pWrite((*ib).smuled_monom_);
+          //printf("s = ");pWrite((*ib).not_muled_.s_monom_);
+                                }
+        */
+                        if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
+                        {
+                                break;
+                        }else{
+                                p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
+                                B.erase_and_move_from_back(b_min_finder.minimum_idx_);
+                        }
+                }
+                idDelete(&I0);
+                I0 = idInit(R.size());
+                int i0_idx = 0;
+                for(LPolysByGvw::iterator ir = R.begin();ir != R.end();++ir,++i0_idx)
+                {
+                        std::swap(I0->m[i0_idx], (*ir)->p_);
+                        delete (*ir);
+                        
+                }
+                R.clear();
+        }
+
+        printf("time time_interred = %d\n", time_interred);
+        printf("time time_prepare = %d\n", time_prepare);
+        printf("time time_reduction_search = %d\n", time_reduction_search);
+        printf("time time_reduction = %d\n", time_reduction);
+        printf("time time_add_r = %d\n", time_add_r);
+        printf("time time_filter_b = %d\n", time_filter_b);
+        printf("time time_add_b1_testings = %d\n", time_add_b1_testings);
+        printf("time time_add_b1_insertion = %d\n", time_add_b1_insertion);
+        printf("time time_add_b2 = %d\n", time_add_b2);
+
+        printf("ZERO REDUCTIONS: %d\n", zero_reductions);
+
+        return I0;
+}
+ideal ssgnoninc (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
+{
+  int 
+    time_interred = 0, time_prepare = 0, time_reduction_search = 0, time_reduction = 0,
+                  time_add_r = 0, time_filter_b = 0, time_add_b1_testings = 0, time_add_b1_insertion = 0,
+                  time_add_b2 = 0;
+
+  time_from_last_call();
+  int current_input_idx = 0;
+  while (F->m[current_input_idx] == NULL && current_input_idx < IDELEMS(F))
+  {
+    ++current_input_idx;
+  }
+  ideal I0 = idInit(1);
+  if (current_input_idx >= IDELEMS(F))
+  {
+    return I0;
+  }
+  I0->m[0] = pCopy(F->m[current_input_idx]);
+  int zero_reductions = 0;
+  LabeledPoly::GvwLess gvw_less;
+  poly pEins = pOne();
+  // made these global for non-incremental computation
+  // -------------------------------------------------
+  LPolysByGvw R;
+  LPolysMuledBySig B;
+  SigMuledMinimumFinder b_min_finder(B);
+  LabeledPoly* p;
+  LPolysByGvw::iterator first_zero_sig_temp = R.begin();
+  bool set_first_zero_sig                   = true;
+  // -------------------------------------------------
+  for (current_input_idx +=1; current_input_idx < IDELEMS(F); ++current_input_idx)
+  {
+    if (!F->m[current_input_idx]) continue;
+    idDelDiv(I0);
+    idSkipZeroes(I0);
+#ifndef SSG_NO_INTERRED
+    std::sort(I0->m, I0->m+IDELEMS(I0), LmCompareForNonZeroPolys());
+
+    ideal I0_tail_reduced = idInit(IDELEMS(I0));
+    //tail reducton
+    for(int n0 = IDELEMS(I0) - 1; n0 > 0; --n0)
+    {
+      poly p_old = NULL;
+      std::swap(p_old,I0->m[n0]);
+      poly p_new = kNF(I0, Q, p_old);
+      pDelete(&p_old);
+      I0_tail_reduced->m[n0] = p_new;
+    }
+    std::swap(I0_tail_reduced->m[0], I0->m[0]);
+    idDelete(&I0);
+    I0 = I0_tail_reduced;
+#endif
+    time_interred += time_from_last_call();
+    //LPolysByGvw R;
+    //LPolysMuledBySig B;
+    //LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx]);
+    p = LabeledPoly::CreateOneSig(F->m[current_input_idx], 
+        current_input_idx);
+    for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
+    {
+      R.push_back(LabeledPoly::CreateZeroSig(I0->m[n0]));
+    }
+    //const LPolysByGvw::iterator first_zero_sig = R.begin();
+    if (set_first_zero_sig)
+    {
+      first_zero_sig_temp = R.begin();
+      set_first_zero_sig  = false;
+    }
+    /*
+       for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
+       {
+       for (int m0 = n0-1; m0>=0; --m0)
+       {
+       R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0], n0, I0->m[m0], m0));
+       }
+       }
+       */
+    for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
+    {
+      //R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0]));
+      R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0],current_input_idx+1,F->m[current_input_idx]));
+    }
+    /*
+       printf("\nR-init = \n");
+       for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
+       {
+       printf("p = ");pWrite((*ir)->p_);
+       printf("s = ");pWrite((*ir)->s_monom_);
+       }
+       */
+    LabeledPolyMuled bnew;
+    bnew.Init();
+    bnew.FillBy(pEins, *p);
+    LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig_temp;
+    /*
+       const LPolysByGvw::iterator p_insert_pos =
+       R.insert(known_gvw_greater_p, p);
+       */
+    bool rejected = false;
+    //SigMuledMinimumFinder b_min_finder(B);
+    //SigMuledMinimumFinder b_min_finder(B);
+    /*
+       for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
+       {
+       if ((*ir2)->sig_divides(bnew))
+       {
+       rejected = true;
+       break;
+       }
+       }
+       */
+    if (!rejected)
+    {
+      B.push_back(bnew);
+      b_min_finder.UpdateBy(B.size() - 1);
+      bnew.Init();
+      //time_add_b1_insertion += time_from_last_call();
+    }
+    bnew.Release();
+  }
+  const LPolysByGvw::iterator first_zero_sig = first_zero_sig_temp;
+  //SigMuledMinimumFinder b_min_finder(B);
+  /*
+  printf("B = \n");
+  for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
+  {
+    printf("smuled = ");pWrite((*ib).smuled_monom_);
+    //printf("s = ");pWrite((ib)->not_muled_.s_monom_);
+  }
+  */
+  time_prepare += time_from_last_call();
+  // first test in B
+  if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
+  {
+    return I0;
+    //break;
+  }else{
+    p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
+    B.erase_and_move_from_back(b_min_finder.minimum_idx_);
+  }
+  while(1)
+  {
+    bool reduced_to_zero = false;
+    LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
+#if 1
+    /*
+       if (n ==  IDELEMS(F) - 1)
+       {
+       */
+    /*
+       printf("\nR = \n");
+       for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
+       {
+       printf("p = ");pWrite((*ir)->p_);
+       printf("s = ");pWrite((*ir)->s_monom_);
+       }
+       printf("B = \n");
+       for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
+       {
+       printf("smuled = ");pWrite((*ib).smuled_monom_);
+    //printf("s = ");pWrite((*ib)->not_muled_.s_monom_);
+    }
+    */
+    /*
+       }
+       */
+#endif
+    while(1)
+    {
+      //printf("p to reduce = ");pWrite (p->p_);
+      bool was_reduced = false;
+      LPolysByGvw::iterator ir = --R.end();
+      while(1)
+      {
+        was_reduced = p->can_reduce_by(*ir);
+        if (was_reduced)
+        {
+          time_reduction_search += time_from_last_call();
+          p->reduce_by(*ir);
+          time_reduction += time_from_last_call();
+          break;
+        }
+        if (ir == known_gvw_greater_p) break;
+        --ir;
+      }
+      if (!was_reduced && ir != R.begin())
+      {
+        --ir;
+        while(1)
+        {
+          if (!gvw_less(p, *ir))
+          {
+            ++ir;
+            break;
+          }
+          was_reduced = p->can_reduce_by(*ir);
+          if (was_reduced)
+          {
+            time_reduction_search += time_from_last_call();
+            p->reduce_by(*ir);
+            time_reduction += time_from_last_call();
+            break;
+          }
+          if (ir == R.begin()) break;
+          --ir;
+        }
+        known_gvw_greater_p = ir;
+      }
+      if (!was_reduced) break;
+      reduced_to_zero = p->p_ == NULL;
+      if (reduced_to_zero)
+      {
+        ++zero_reductions;
+        known_gvw_greater_p = R.begin();
+        break;
+      }
+    }
+    time_reduction_search += time_from_last_call();
+    const LPolysByGvw::iterator p_insert_pos =
+      R.insert(known_gvw_greater_p, p);
+    time_add_r += time_from_last_call();
+    SigMuledMinimumFinder b_min_finder(B);
+    for(int i=0;i<B.size();)
+    {
+      LabeledPolyMuled& b = B[i];
+      if (p->sig_divides(b) && gvw_less(p,b.not_muled_))
+      {
+        b.Release();
+        B.erase_and_move_from_back(i);
+      }else
+      {
+        b_min_finder.UpdateBy(i);
+        ++i;
+      }
+    }
+    time_filter_b += time_from_last_call();
+    if (!reduced_to_zero)
+    {
+      LabeledPolyMuled bnew;
+      bnew.Init();
+       /*
+        printf("\nR = \n");
+       for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
+       {
+       printf("p = ");pWrite((*ir)->p_);
+       printf("s = ");pWrite((*ir)->s_monom_);
+       }
+       */
+      for(LPolysByGvw::const_iterator ir = --R.end();ir != p_insert_pos;--ir)
+      {
+        //printf ("pNew = "); pWrite(p->p_);
+        bnew.FillBy((*ir)->p_, *p);
+        bool rejected = false;
+        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
+        {
+          if ((*ir2)->sig_divides(bnew))
+          {
+            rejected = true;
+            break;
+          }
+        }
+        time_add_b1_testings += time_from_last_call();
+        if (!rejected)
+        {
+          B.push_back(bnew);
+          b_min_finder.UpdateBy(B.size() - 1);
+          bnew.Init();
+          time_add_b1_insertion += time_from_last_call();
+        }
+      }
+      for(LPolysByGvw::const_iterator ir = R.begin();ir != p_insert_pos;++ir)
+      {
+        if (!gvw_less(*ir, p)) break;
+        if ((*ir)->p_ == NULL) continue;
+        bool rejected = false;
+        bnew.FillBy(p->p_, *(*ir));
+        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != ir;++ir2)
+        {
+          if ((*ir2)->sig_divides(bnew))
+          {
+            rejected = true;
+            break;
+          }
+        }
+        if (!rejected)
+        {
+          B.push_back(bnew);
+          b_min_finder.UpdateBy(B.size() - 1);
+          bnew.Init();
+        }
+      }
+      bnew.Release();
+      time_add_b2 += time_from_last_call();
+    }
+    /*
+       printf("B = \n");
+       for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
+       {
+       printf("smuled = ");pWrite((*ib).smuled_monom_);
+    //printf("s = ");pWrite((*ib).not_muled_.s_monom_);
+    }
+    */
+    if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
+    {
+      break;
+    }else{
+      p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
+      B.erase_and_move_from_back(b_min_finder.minimum_idx_);
+    }
+  }
+  idDelete(&I0);
+  I0 = idInit(R.size());
+  int i0_idx = 0;
+  for(LPolysByGvw::iterator ir = R.begin();ir != R.end();++ir,++i0_idx)
+  {
+    std::swap(I0->m[i0_idx], (*ir)->p_);
+    delete (*ir);
+
+  }
+  R.clear();
+
+  printf("time time_interred = %d\n", time_interred);
+  printf("time time_prepare = %d\n", time_prepare);
+  printf("time time_reduction_search = %d\n", time_reduction_search);
+  printf("time time_reduction = %d\n", time_reduction);
+  printf("time time_add_r = %d\n", time_add_r);
+  printf("time time_filter_b = %d\n", time_filter_b);
+  printf("time time_add_b1_testings = %d\n", time_add_b1_testings);
+  printf("time time_add_b1_insertion = %d\n", time_add_b1_insertion);
+  printf("time time_add_b2 = %d\n", time_add_b2);
+
+  printf("ZERO REDUCTIONS: %d\n", zero_reductions);
+
+  return I0;
+}
+ideal ssg (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
+{
+        int 
+                time_interred = 0, time_prepare = 0, time_reduction_search = 0, time_reduction = 0,
+                time_add_r = 0, time_filter_b = 0, time_add_b1_testings = 0, time_add_b1_insertion = 0,
+                time_add_b2 = 0;
+
+        time_from_last_call();
+        int current_input_idx = 0;
+        while (F->m[current_input_idx] == NULL && current_input_idx < IDELEMS(F))
+        {
+                ++current_input_idx;
+        }
+        ideal I0 = idInit(1);
+        if (current_input_idx >= IDELEMS(F))
+        {
+                return I0;
+        }
+        I0->m[0] = pCopy(F->m[current_input_idx]);
+        int zero_reductions = 0;
+        LabeledPoly::GvwLess gvw_less;
+        for (current_input_idx +=1; current_input_idx < IDELEMS(F); ++current_input_idx)
+        {
+                if (!F->m[current_input_idx]) continue;
+                idDelDiv(I0);
+                idSkipZeroes(I0);
+#ifndef SSG_NO_INTERRED
+                std::sort(I0->m, I0->m+IDELEMS(I0), LmCompareForNonZeroPolys());
+                
+                ideal I0_tail_reduced = idInit(IDELEMS(I0));
+                //tail reducton
+                for(int n0 = IDELEMS(I0) - 1; n0 > 0; --n0)
+                {
+                        poly p_old = NULL;
+                        std::swap(p_old,I0->m[n0]);
+                        poly p_new = kNF(I0, Q, p_old);
+                        pDelete(&p_old);
+                        I0_tail_reduced->m[n0] = p_new;
+                }
+                std::swap(I0_tail_reduced->m[0], I0->m[0]);
+                idDelete(&I0);
+                I0 = I0_tail_reduced;
+#endif
+                time_interred += time_from_last_call();
+                LPolysByGvw R;
+                LPolysMuledBySig B;
+                LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx]);
+                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
+                {
+                        R.push_back(LabeledPoly::CreateZeroSig(I0->m[n0]));
+                }
+                const LPolysByGvw::iterator first_zero_sig = R.begin();
+                for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
+                {
+                        R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0]));
+                }
+    /*
+                                printf("\nR-init = \n");
+                                for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
+                                {
+                                        printf("p = ");pWrite((*ir)->p_);
+                                        printf("s = ");pWrite((*ir)->s_monom_);
+                                }
+    */
+                time_prepare += time_from_last_call();
+                while(1)
+                {
+                        bool reduced_to_zero = false;
+                        LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
+#if 1
+      /*
+                        if (n ==  IDELEMS(F) - 1)
+                        {
+      */
+                                /*
+        printf("\nR = \n");
+                                for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
+                                {
+                                        printf("p = ");pWrite((*ir)->p_);
+                                        printf("s = ");pWrite((*ir)->s_monom_);
+                                }
+                                printf("B = \n");
+                                for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
+                                {
+                                        printf("smuled = ");pWrite((*ib).smuled_monom_);
+          //printf("s = ");pWrite((*ib)->not_muled_.s_monom_);
+                                }
+        */
+                        /*
+      }
+      */
+#endif
+                        while(1)
+                        {
+                                bool was_reduced = false;
+                                LPolysByGvw::iterator ir = --R.end();
+        //printf("p to reduce = ");pWrite (p->p_);
+                                while(1)
+                                {
+                                        was_reduced = p->can_reduce_by(*ir);
+                                        if (was_reduced)
+                                        {
+                                                time_reduction_search += time_from_last_call();
+                                                p->reduce_by(*ir);
+                                                time_reduction += time_from_last_call();
+                                                break;
+                                        }
+                                        if (ir == known_gvw_greater_p) break;
+                                        --ir;
+                                }
+                                if (!was_reduced && ir != R.begin())
+                                {
+                                        --ir;
+                                        while(1)
+                                        {
+                                                if (!gvw_less(p, *ir))
+                                                {
+                                                        ++ir;
+                                                        break;
+                                                }
+                                                was_reduced = p->can_reduce_by(*ir);
+                                                if (was_reduced)
+                                                {
+                                                        time_reduction_search += time_from_last_call();
+                                                        p->reduce_by(*ir);
+                                                        time_reduction += time_from_last_call();
+                                                        break;
+                                                }
+                                                if (ir == R.begin()) break;
+                                                --ir;
+                                        }
+                                        known_gvw_greater_p = ir;
+                                }
+                                if (!was_reduced) break;
+                                reduced_to_zero = p->p_ == NULL;
+                                if (reduced_to_zero)
+                                {
+                                        ++zero_reductions;
+                                        known_gvw_greater_p = R.begin();
+                                        break;
+                                }
+                        }
+                        time_reduction_search += time_from_last_call();
+                        const LPolysByGvw::iterator p_insert_pos =
+                                R.insert(known_gvw_greater_p, p);
+                        time_add_r += time_from_last_call();
+                        SigMuledMinimumFinder b_min_finder(B);
+                        for(int i=0;i<B.size();)
+                        {
+                                LabeledPolyMuled& b = B[i];
+                                if (p->sig_divides(b) && gvw_less(p,b.not_muled_))
+                                {
+                                        b.Release();
+                                        B.erase_and_move_from_back(i);
+                                }else
+                                {
+                                        b_min_finder.UpdateBy(i);
+                                        ++i;
+                                }
+                        }
+                        time_filter_b += time_from_last_call();
+                        if (!reduced_to_zero)
+                        {
+                                LabeledPolyMuled bnew;
+                                bnew.Init();
+                                for(LPolysByGvw::const_iterator ir = --R.end();ir != p_insert_pos;--ir)
+                                {
+                                        bnew.FillBy((*ir)->p_, *p);
+                                        bool rejected = false;
+                                        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
+                                        {
+                                                if ((*ir2)->sig_divides(bnew))
+                                                {
+                                                        rejected = true;
+                                                        break;
+                                                }
+                                        }
+                                        time_add_b1_testings += time_from_last_call();
+                                        if (!rejected)
+                                        {
+                                                B.push_back(bnew);
+                                                b_min_finder.UpdateBy(B.size() - 1);
+                                                bnew.Init();
+                                                time_add_b1_insertion += time_from_last_call();
+                                        }
+                                }
+                                for(LPolysByGvw::const_iterator ir = R.begin();ir != p_insert_pos;++ir)
+                                {
+                                        if (!gvw_less(*ir, p)) break;
+                                        if ((*ir)->p_ == NULL) continue;
+                                        bool rejected = false;
+                                        bnew.FillBy(p->p_, *(*ir));
+                                        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != ir;++ir2)
+                                        {
+                                                if ((*ir2)->sig_divides(bnew))
+                                                {
+                                                        rejected = true;
+                                                        break;
+                                                }
+                                        }
+                                        if (!rejected)
+                                        {
+                                                B.push_back(bnew);
+                                                b_min_finder.UpdateBy(B.size() - 1);
+                                                bnew.Init();
+                                        }
+                                }
+                                bnew.Release();
+                                time_add_b2 += time_from_last_call();
+                        }
+                                /*
+        printf("B = \n");
+                                for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
+                                {
+                                        printf("smuled = ");pWrite((*ib).smuled_monom_);
+          //printf("s = ");pWrite((*ib).not_muled_.s_monom_);
+                                }
+        */
+                        if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
+                        {
+                                break;
+                        }else{
+                                p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
+                                B.erase_and_move_from_back(b_min_finder.minimum_idx_);
+                        }
+      
+                }
+                idDelete(&I0);
+                I0 = idInit(R.size());
+                int i0_idx = 0;
+                for(LPolysByGvw::iterator ir = R.begin();ir != R.end();++ir,++i0_idx)
+                {
+                        std::swap(I0->m[i0_idx], (*ir)->p_);
+                        delete (*ir);
+                        
+                }
+                R.clear();
+        }
+
+        printf("time time_interred = %d\n", time_interred);
+        printf("time time_prepare = %d\n", time_prepare);
+        printf("time time_reduction_search = %d\n", time_reduction_search);
+        printf("time time_reduction = %d\n", time_reduction);
+        printf("time time_add_r = %d\n", time_add_r);
+        printf("time time_filter_b = %d\n", time_filter_b);
+        printf("time time_add_b1_testings = %d\n", time_add_b1_testings);
+        printf("time time_add_b1_insertion = %d\n", time_add_b1_insertion);
+        printf("time time_add_b2 = %d\n", time_add_b2);
+
+        printf("ZERO REDUCTIONS: %d\n", zero_reductions);
+
+        return I0;
+}
+ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
+{
+  // ring order stuff:
+  // in sba we have (until now) two possibilities:
+  // 1. an incremental computation w.r.t. (C,monomial order)
+  // 2. a (possibly non-incremental) computation w.r.t. the 
+  //    induced Schreyer order.
+  // The corresponding orders are computed in sbaRing(), depending
+  // on the flag strat->incremental
+  ideal F = F0;
+  ring sRing, currRingOld;
+  currRingOld  = currRing; 
+  if (strat->incremental)
+  {
+    sRing = sbaRing(strat);
+    if (sRing!=currRingOld)
+    {
+      rChangeCurrRing (sRing);
+      F = idrMoveR (F0, currRingOld);
+    }
+  }
+#if 0
+  printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
+  rWrite (currRing);
+  printf("\n");
+#endif
+#ifdef KDEBUG
+  bba_count++;
+  int loop_count = 0;
+#endif /* KDEBUG */
+  om_Opts.MinTrack = 5;
+  int   srmax,lrmax, red_result = 1;
+  int   olddeg,reduc;
+  int hilbeledeg=1,hilbcount=0,minimcnt=0;
+  LObject L;
+  BOOLEAN withT     = FALSE;
+  BOOLEAN newrules  = FALSE;
+  strat->max_lower_index = 0;
+
+  //initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
+  initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
+  initSbaPos(strat);
+  //initBuchMoraPos(strat);
+  initHilbCrit(F,Q,&hilb,strat);
+  initSba(F,strat);
+  /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
+  /*Shdl=*/initSbaBuchMora(F, Q,strat);
+  if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
+  srmax = strat->sl;
+  reduc = olddeg = lrmax = 0;
+
+#ifndef NO_BUCKETS
+  if (!TEST_OPT_NOT_BUCKETS)
+    strat->use_buckets = 1;
+#endif
+
+  // redtailBBa against T for inhomogenous input
+  if (!TEST_OPT_OLDSTD)
+    withT = ! strat->homog;
+
+  // strat->posInT = posInT_pLength;
+  kTest_TS(strat);
+
+#ifdef KDEBUG
+#if MYTEST
+  if (TEST_OPT_DEBUG)
+  {
+    PrintS("bba start GB: currRing: ");
+    // rWrite(currRing);PrintLn();
+    rDebugPrint(currRing);
+    PrintLn();
+  }
+#endif /* MYTEST */
+#endif /* KDEBUG */
+
+#ifdef HAVE_TAIL_RING
+  if(!idIs0(F) &&(!rField_is_Ring()))  // create strong gcd poly computes with tailring and S[i] ->to be fixed
+    kStratInitChangeTailRing(strat);
+#endif
+  if (BVERBOSE(23))
+  {
+    if (test_PosInT!=NULL) strat->posInT=test_PosInT;
+    if (test_PosInL!=NULL) strat->posInL=test_PosInL;
+    kDebugPrint(strat);
+  }
+
+
+#ifdef KDEBUG
+  //kDebugPrint(strat);
+#endif
+  /* compute------------------------------------------------------- */
+  arriAgain:
+  while (strat->Ll >= 0)
+  {
+    if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
+    #ifdef KDEBUG
+      loop_count++;
+      if (TEST_OPT_DEBUG) messageSets(strat);
+    #endif
+    if (strat->Ll== 0) strat->interpt=TRUE;
+    if (TEST_OPT_DEGBOUND
+        && ((strat->honey && (strat->L[strat->Ll].ecart+pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
+            || ((!strat->honey) && (pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
+    {
+      /*
+       *stops computation if
+       * 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
+       *a predefined number Kstd1_deg
+       */
+      while ((strat->Ll >= 0)
+        && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
+        && ((strat->honey && (strat->L[strat->Ll].ecart+pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
+            || ((!strat->honey) && (pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
+        )
+        deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
+      if (strat->Ll<0) break;
+      else strat->noClearS=TRUE;
+    }
+    if (strat->incremental && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
+    {
+      strat->currIdx  = pGetComp(strat->L[strat->Ll].sig);
+#if F5C
+      // 1. interreduction of the current standard basis
+      // 2. generation of new principal syzygy rules for syzCriterion
+      f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax, 
+            lrmax, reduc, Q, w, hilb );
+#endif
+      // initialize new syzygy rules for the next iteration step  
+      initSyzRules(strat);
+    }
+    /*********************************************************************
+     * interrreduction step is done, we can go on with the next iteration
+     * step of the signature-based algorithm
+     ********************************************************************/
+    /* picks the last element from the lazyset L */
+    strat->P = strat->L[strat->Ll];
+    strat->Ll--;
+//#if 1
+#ifdef DEBUGF5
+    Print("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
+    Print("-------------------------------------------------\n");
+    pWrite(strat->P.sig);
+    pWrite(pHead(strat->P.p));
+    pWrite(pHead(strat->P.p1));
+    pWrite(pHead(strat->P.p2));
+    Print("-------------------------------------------------\n");
+#endif
+    if (pNext(strat->P.p) == strat->tail)
+    {
+      // deletes the short spoly
+#ifdef HAVE_RINGS
+      if (rField_is_Ring(currRing))
+        pLmDelete(strat->P.p);
+      else
+#endif
+        pLmFree(strat->P.p);
+
+      // TODO: needs some masking
+      // TODO: masking needs to vanish once the signature
+      //       sutff is completely implemented
+      strat->P.p = NULL;
+      poly m1 = NULL, m2 = NULL;
+
+      // check that spoly creation is ok
+      while (strat->tailRing != currRing &&
+             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
+      {
+        assume(m1 == NULL && m2 == NULL);
+        // if not, change to a ring where exponents are at least
+        // large enough
+        if (!kStratChangeTailRing(strat))
+        {
+          WerrorS("OVERFLOW...");
+          break;
+        }
+      }
+      // create the real one
+      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
+                    strat->tailRing, m1, m2, strat->R);
+
+    }
+    else if (strat->P.p1 == NULL)
+    {
+      if (strat->minim > 0)
+        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
+      // for input polys, prepare reduction
+      strat->P.PrepareRed(strat->use_buckets);
+    }
+
+    if (strat->P.p == NULL && strat->P.t_p == NULL)
+    {
+      red_result = 0;
+    }
+    else
+    {
+      if (TEST_OPT_PROT)
+        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
+                &olddeg,&reduc,strat, red_result);
+
+//#if 1
+#ifdef DEBUGF5
+      Print("Poly before red: ");
+      pWrite(strat->P.p);
+#endif
+      /* reduction of the element choosen from L */
+      if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat, strat->P.checked+1))
+        red_result = strat->red(&strat->P,strat);
+      else
+      {
+        if (strat->P.lcm!=NULL)
+          pLmFree(strat->P.lcm);
+        red_result = 2;
+      }
+      if (errorreported)  break;
+    }
+
+    if (strat->overflow)
+    {
+        if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
+    }
+    if (strat->incremental)
+    {
+      for (int jj = 0; jj<strat->tl+1; jj++)
+      {
+        if (pGetComp(strat->T[jj].sig) == strat->currIdx)
+        {
+          strat->T[jj].is_sigsafe = FALSE;
+        }
+      }
+    }
+    else
+    {
+      for (int jj = 0; jj<strat->tl+1; jj++)
+      {
+        strat->T[jj].is_sigsafe = FALSE;
+      }
+    }
+
+    // reduction to non-zero new poly
+    if (red_result == 1)
+    {
+      // get the polynomial (canonicalize bucket, make sure P.p is set)
+      strat->P.GetP(strat->lmBin);
+      
+      // sig-safe computations may lead to wrong FDeg computation, thus we need 
+      // to recompute it to make sure everything is alright
+      (strat->P).FDeg = (strat->P).pFDeg();
+      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
+      // but now, for entering S, T, we reset it
+      // in the inhomogeneous case: FDeg == pFDeg
+      if (strat->homog) strat->initEcart(&(strat->P));
+
+      /* statistic */
+      if (TEST_OPT_PROT) PrintS("s");
+
+      //int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
+      // in F5E we know that the last reduced element is already the
+      // the one with highest signature
+      int pos = strat->sl+1;
+
+#ifdef KDEBUG
+#if MYTEST
+      PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
+#endif /* MYTEST */
+#endif /* KDEBUG */
+
+      // reduce the tail and normalize poly
+      // in the ring case we cannot expect LC(f) = 1,
+      // therefore we call pContent instead of pNorm
+      /*
+      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
+      {
+        strat->P.pCleardenom();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+        {
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
+          strat->P.pCleardenom();
+        }
+      }
+      else
+      {
+        strat->P.pNorm();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
+      }
+      */
+#ifdef KDEBUG
+      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
+#if MYTEST
+//#if 1
+      PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
+#endif /* MYTEST */
+#endif /* KDEBUG */
+
+      // min_std stuff
+      if ((strat->P.p1==NULL) && (strat->minim>0))
+      {
+        if (strat->minim==1)
+        {
+          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
+          p_Delete(&strat->P.p2, currRing, strat->tailRing);
+        }
+        else
+        {
+          strat->M->m[minimcnt]=strat->P.p2;
+          strat->P.p2=NULL;
+        }
+        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
+          pNext(strat->M->m[minimcnt])
+            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
+                                           strat->tailRing, currRing,
+                                           currRing->PolyBin);
+        minimcnt++;
+      }
+
+      // enter into S, L, and T
+      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
+      if(!strat->incremental)
+      {
+        BOOLEAN overwrite = TRUE;
+        for (int tk=0; tk<strat->sl+1; tk++)
+        {
+          if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
+          {
+            //printf("TK %d / %d\n",tk,strat->sl);
+            overwrite = FALSE;
+            break;
+          }
+        }
+        //printf("OVERWRITE %d\n",overwrite);
+        if (overwrite)
+        {
+          int cmp = pGetComp(strat->P.sig);
+          int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
+          pGetExpV (strat->P.p,vv);
+          pSetExpV (strat->P.sig, vv);
+          pSetComp (strat->P.sig,cmp);
+
+          strat->P.sevSig = pGetShortExpVector (strat->P.sig);
+          for(int ps=0;ps<strat->sl+1;ps++)
+          {
+            int i = strat->syzl;
+
+            strat->newt = TRUE;
+            if (strat->syzl == strat->syzmax)
+            {
+              pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
+              strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
+                  (strat->syzmax)*sizeof(unsigned long),
+                  ((strat->syzmax)+setmaxTinc)
+                  *sizeof(unsigned long));
+              strat->syzmax += setmaxTinc;
+            }
+            strat->syz[i] = pCopy(strat->P.sig);
+            // add LM(F->m[i]) to the signature to get a Schreyer order
+            // without changing the underlying polynomial ring at all
+            p_ExpVectorAdd (strat->syz[i],strat->S[ps],currRing);  
+            // since p_Add_q() destroys all input
+            // data we need to recreate help 
+            // each time
+            // ----------------------------------------------------------
+            // in the Schreyer order we always know that the multiplied 
+            // module monomial strat->P.sig gives the leading monomial of
+            // the corresponding principal syzygy
+            // => we do not need to compute the "real" syzygy completely
+            poly help = pCopy(strat->sig[ps]);
+            p_ExpVectorAdd (help,strat->P.p,currRing);  
+            strat->syz[i] = p_Add_q(strat->syz[i],help,currRing);
+            //printf("%d. SYZ  ",i+1);
+            //pWrite(strat->syz[i]);
+            strat->sevSyz[i] = p_GetShortExpVector(strat->syz[i],currRing);
+            strat->syzl++;
+          }
+        }
+      }
+        enterT(strat->P, strat);
+        strat->T[strat->tl].is_sigsafe = FALSE;
+#ifdef HAVE_RINGS
+      if (rField_is_Ring(currRing))
+        superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
+      else
+#endif
+        enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
+      // posInS only depends on the leading term
+      strat->enterS(strat->P, pos, strat, strat->tl);
+//#if 1
+#if DEBUGF50
+    printf("---------------------------\n");
+    Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
+    Print("LEAD POLY:  "); pWrite(pHead(strat->S[strat->sl]));
+    Print("SIGNATURE:  "); pWrite(strat->sig[strat->sl]);
+#endif
+      /*
+      if (newrules)
+      {
+        newrules  = FALSE;
+      }
+      */
+#if 0
+      int pl=pLength(strat->P.p);
+      if (pl==1)
+      {
+        //if (TEST_OPT_PROT)
+        //PrintS("<1>");
+      }
+      else if (pl==2)
+      {
+        //if (TEST_OPT_PROT)
+        //PrintS("<2>");
+      }
+#endif
+      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
+//      Print("[%d]",hilbeledeg);
+      if (strat->P.lcm!=NULL)
+#ifdef HAVE_RINGS
+        pLmDelete(strat->P.lcm);
+#else
+        pLmFree(strat->P.lcm);
+#endif
+      if (strat->sl>srmax) srmax = strat->sl;
+    }
+    else
+    {
+      // adds signature of the zero reduction to
+      // strat->syz. This is the leading term of
+      // syzygy and can be used in syzCriterion()
+      // the signature is added if and only if the
+      // pair was not detected by the rewritten criterion in strat->red = redSig
+      if (red_result!=2) {
+        zeroreductions++;
+        enterSyz(strat->P,strat);
+//#if 1
+#ifdef DEBUGF5
+        Print("ADDING STUFF TO SYZ :  ");
+        pWrite(strat->P.p);
+        pWrite(strat->P.sig);
+#endif
+      }
+      if (strat->P.p1 == NULL && strat->minim > 0)
+      {
+        p_Delete(&strat->P.p2, currRing, strat->tailRing);
+      }
+    }
+
+#ifdef KDEBUG
+    memset(&(strat->P), 0, sizeof(strat->P));
+#endif /* KDEBUG */
+    kTest_TS(strat);
+  }
+#ifdef KDEBUG
+#if MYTEST
+  PrintS("bba finish GB: currRing: "); rWrite(currRing);
+#endif /* MYTEST */
+  if (TEST_OPT_DEBUG) messageSets(strat);
+#endif /* KDEBUG */
+
+  if (TEST_OPT_SB_1)
+  {
+    int k=1;
+    int j;
+    while(k<=strat->sl)
+    {
+      j=0;
+      loop
+      {
+        if (j>=k) break;
+        clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
+        j++;
+      }
+      k++;
+    }
+  }
+
+  /* complete reduction of the standard basis--------- */
+  if (TEST_OPT_REDSB)
+  {
+    completeReduce(strat);
+#ifdef HAVE_TAIL_RING
+    if (strat->completeReduce_retry)
+    {
+      // completeReduce needed larger exponents, retry
+      // to reduce with S (instead of T)
+      // and in currRing (instead of strat->tailRing)
+      cleanT(strat);strat->tailRing=currRing;
+      int i;
+      for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
+      completeReduce(strat);
+    }
+#endif
+  }
+  else if (TEST_OPT_PROT) PrintLn();
+
+  exitSba(strat);
+  if (TEST_OPT_WEIGHTM)
+  {
+    pRestoreDegProcs(pFDegOld, pLDegOld);
+    if (ecartWeights)
+    {
+      omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
+      ecartWeights=NULL;
+    }
+  }
+  if (TEST_OPT_PROT) messageStat(srmax,lrmax,hilbcount,strat);
+  if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
+
+#ifdef KDEBUG
+#if MYTEST
+  PrintS("bba_end: currRing: "); rWrite(currRing);
+#endif /* MYTEST */
+#endif /* KDEBUG */
+  // using F5C it is possible that there is some data stored in the last
+  // entries of strat->Shdl which are dirty, i.e. not correct, but also not NULL
+  // => we need to delete them before return the ideal
+#if F5C
+  for(int i=strat->sl+1;i<IDELEMS(strat->Shdl);i++)
+  {
+    //pDelete (&strat->Shdl->m[i]);
+    strat->Shdl->m[i] = NULL;
+  }
+#endif
+  if (strat->incremental && sRing!=currRingOld)
+  {
+    rChangeCurrRing (currRingOld);
+    F0          = idrMoveR (F, sRing);
+    strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing);
+    rDelete (sRing);
+  }
+  idTest(strat->Shdl);
+
+#ifdef DEBUGF5
+  printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
+  int oo = 0;
+  while (oo<IDELEMS(strat->Shdl))
+  {
+    printf(" %d.   ",oo+1);
+    pWrite(pHead(strat->Shdl->m[oo]));
+    oo++;
+  }
+#endif
+  printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
+  zeroreductions  = 0;
   return (strat->Shdl);
 }
@@ -1447 +3063 @@
   return res;
 }
+
+#if F5C
+/*********************************************************************
+* interrreduction step of the signature-based algorithm:
+* 1. all strat->S are interpreted as new critical pairs
+* 2. those pairs need to be completely reduced by the usual (non sig-
+*    safe) reduction process (including tail reductions)
+* 3. strat->S and strat->T are completely new computed in these steps
+********************************************************************/
+void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg, 
+          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
+          intvec *w,intvec *hilb )
+{
+  int Ll_old, red_result = 1;
+  BOOLEAN withT = FALSE;
+  int pos  = 0;
+  hilbeledeg=1;
+  hilbcount=0;
+  minimcnt=0;
+  srmax = 0; // strat->sl is 0 at this point
+  reduc = olddeg = lrmax = 0;
+  // we cannot use strat->T anymore
+  //cleanT(strat);
+  //strat->tl = -1;
+  Ll_old    = strat->Ll;
+  while (strat->tl >= 0)
+  {
+    if(!strat->T[strat->tl].is_redundant)
+    {
+      LObject h;
+      h.p = strat->T[strat->tl].p;
+      h.tailRing = strat->T[strat->tl].tailRing;
+      h.t_p = strat->T[strat->tl].t_p;
+      if (h.p!=NULL)
+      {
+        if (pOrdSgn==-1)
+        {
+          cancelunit(&h);  
+          deleteHC(&h, strat);
+        }
+        if (h.p!=NULL)
+        {
+          if (TEST_OPT_INTSTRATEGY)
+          {
+            //pContent(h.p);
+            h.pCleardenom(); // also does a pContent
+          }
+          else
+          {
+            h.pNorm();
+          }
+          strat->initEcart(&h);
+          pos = strat->Ll+1;
+          h.sev = pGetShortExpVector(h.p);
+          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
+        }
+      }
+    }
+    strat->tl--;
+  }
+  strat->sl = -1;
+#if 0
+//#ifdef HAVE_TAIL_RING
+  if(!rField_is_Ring())  // create strong gcd poly computes with tailring and S[i] ->to be fixed
+    kStratInitChangeTailRing(strat);
+#endif
+  //enterpairs(pOne(),0,0,-1,strat,strat->tl);
+  //strat->sl = -1;
+  /* picks the last element from the lazyset L */
+  while (strat->Ll>Ll_old)
+  {
+    strat->P = strat->L[strat->Ll];
+    strat->Ll--;
+//#if 1
+#ifdef DEBUGF5
+    Print("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
+    Print("-------------------------------------------------\n");
+    pWrite(pHead(strat->P.p));
+    pWrite(pHead(strat->P.p1));
+    pWrite(pHead(strat->P.p2));
+    printf("%d\n",strat->tl);
+    Print("-------------------------------------------------\n");
+#endif
+    if (pNext(strat->P.p) == strat->tail)
+    {
+      // deletes the short spoly
+#ifdef HAVE_RINGS
+      if (rField_is_Ring(currRing))
+        pLmDelete(strat->P.p);
+      else
+#endif
+        pLmFree(strat->P.p);
+
+      // TODO: needs some masking
+      // TODO: masking needs to vanish once the signature
+      //       sutff is completely implemented
+      strat->P.p = NULL;
+      poly m1 = NULL, m2 = NULL;
+
+      // check that spoly creation is ok
+      while (strat->tailRing != currRing &&
+          !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
+      {
+        assume(m1 == NULL && m2 == NULL);
+        // if not, change to a ring where exponents are at least
+        // large enough
+        if (!kStratChangeTailRing(strat))
+        {
+          WerrorS("OVERFLOW...");
+          break;
+        }
+      }
+      // create the real one
+      ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
+          strat->tailRing, m1, m2, strat->R);
+    }
+    else if (strat->P.p1 == NULL)
+    {
+      if (strat->minim > 0)
+        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
+      // for input polys, prepare reduction
+      strat->P.PrepareRed(strat->use_buckets);
+    }
+
+    if (strat->P.p == NULL && strat->P.t_p == NULL)
+    {
+      red_result = 0;
+    }
+    else
+    {
+      if (TEST_OPT_PROT)
+        message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
+            &olddeg,&reduc,strat, red_result);
+
+#ifdef DEBUGF5
+      Print("Poly before red: ");
+      pWrite(strat->P.p);
+#endif
+      /* complete reduction of the element choosen from L */
+      red_result = strat->red2(&strat->P,strat);
+      if (errorreported)  break;
+    }
+
+    if (strat->overflow)
+    {
+      if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
+    }
+
+    // reduction to non-zero new poly
+    if (red_result == 1)
+    {
+      // get the polynomial (canonicalize bucket, make sure P.p is set)
+      strat->P.GetP(strat->lmBin);
+      // in the homogeneous case FDeg >= pFDeg (sugar/honey)
+      // but now, for entering S, T, we reset it
+      // in the inhomogeneous case: FDeg == pFDeg
+      if (strat->homog) strat->initEcart(&(strat->P));
+
+      /* statistic */
+      if (TEST_OPT_PROT) PrintS("s");
+
+      int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
+
+#ifdef KDEBUG
+#if MYTEST
+      PrintS("New S: "); pDebugPrint(strat->P.p); PrintLn();
+#endif /* MYTEST */
+#endif /* KDEBUG */
+
+      // reduce the tail and normalize poly
+      // in the ring case we cannot expect LC(f) = 1,
+      // therefore we call pContent instead of pNorm
+#if F5CTAILRED
+      if ((TEST_OPT_INTSTRATEGY) || (rField_is_Ring(currRing)))
+      {
+        strat->P.pCleardenom();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+        {
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
+          strat->P.pCleardenom();
+        }
+      }
+      else
+      {
+        strat->P.pNorm();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
+      }
+#endif
+#ifdef KDEBUG
+      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
+#if MYTEST
+//#if 1
+      PrintS("New (reduced) S: "); pDebugPrint(strat->P.p); PrintLn();
+#endif /* MYTEST */
+#endif /* KDEBUG */
+
+      // min_std stuff
+      if ((strat->P.p1==NULL) && (strat->minim>0))
+      {
+        if (strat->minim==1)
+        {
+          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
+          p_Delete(&strat->P.p2, currRing, strat->tailRing);
+        }
+        else
+        {
+          strat->M->m[minimcnt]=strat->P.p2;
+          strat->P.p2=NULL;
+        }
+        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
+          pNext(strat->M->m[minimcnt])
+            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
+                strat->tailRing, currRing,
+                currRing->PolyBin);
+        minimcnt++;
+      }
+
+      // enter into S, L, and T
+      // here we need to recompute new signatures, but those are trivial ones
+      //if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
+      enterT(strat->P, strat);
+      // posInS only depends on the leading term
+      strat->enterS(strat->P, pos, strat, strat->tl);
+//#if 1
+#ifdef DEBUGF5
+      Print("ELEMENT ADDED TO GCURR DURING INTERRED: ");
+      pWrite(pHead(strat->S[strat->sl]));
+      pWrite(strat->sig[strat->sl]);
+#endif
+      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
+      //      Print("[%d]",hilbeledeg);
+      if (strat->P.lcm!=NULL)
+#ifdef HAVE_RINGS
+        pLmDelete(strat->P.lcm);
+#else
+      pLmFree(strat->P.lcm);
+#endif
+      if (strat->sl>srmax) srmax = strat->sl;
+    }
+    else
+    {
+      // adds signature of the zero reduction to
+      // strat->syz. This is the leading term of
+      // syzygy and can be used in syzCriterion()
+      // the signature is added if and only if the
+      // pair was not detected by the rewritten criterion in strat->red = redSig
+      if (strat->P.p1 == NULL && strat->minim > 0)
+      {
+        p_Delete(&strat->P.p2, currRing, strat->tailRing);
+      }
+    }
+
+#ifdef KDEBUG
+    memset(&(strat->P), 0, sizeof(strat->P));
+#endif /* KDEBUG */
+  }
+  int cc = 0;
+  while (cc<strat->tl+1)
+  {
+    strat->T[cc].sig        = pOne();
+    p_SetComp(strat->T[cc].sig,cc+1,currRing);
+    strat->T[cc].sevSig     = pGetShortExpVector(strat->T[cc].sig);
+    strat->sig[cc]          = strat->T[cc].sig;
+    strat->sevSig[cc]       = strat->T[cc].sevSig;
+    strat->T[cc].is_sigsafe = TRUE;  
+    cc++;
+  }
+  strat->max_lower_index = strat->tl;
+  // set current signature index of upcoming iteration step
+  // NOTE:  this needs to be set here, as otherwise initSyzRules cannot compute
+  //        the corresponding syzygy rules correctly
+  strat->currIdx = cc+1;
+  for (int cd=strat->Ll; cd>=0; cd--)
+  {
+    p_SetComp(strat->L[cd].sig,cc+1,currRing);
+    cc++;
+  }
+//#if 1
+#if DEBUGF5
+  Print("------------------- STRAT S ---------------------\n");
+  cc = 0;
+  while (cc<strat->tl+1)
+  {
+    pWrite(pHead(strat->S[cc]));
+    pWrite(strat->sig[cc]);
+    printf("- - - - - -\n");
+    cc++;
+  }
+  Print("-------------------------------------------------\n");
+  Print("------------------- STRAT T ---------------------\n");
+  cc = 0;
+  while (cc<strat->tl+1)
+  {
+    pWrite(pHead(strat->T[cc].p));
+    pWrite(strat->T[cc].sig);
+    printf("- - - - - -\n");
+    cc++;
+  }
+  Print("-------------------------------------------------\n");
+  Print("------------------- STRAT L ---------------------\n");
+  cc = 0;
+  while (cc<strat->Ll+1)
+  {
+    pWrite(pHead(strat->L[cc].p));
+    pWrite(pHead(strat->L[cc].p1));
+    pWrite(pHead(strat->L[cc].p2));
+    pWrite(strat->L[cc].sig);
+    printf("- - - - - -\n");
+    cc++;
+  }
+  Print("-------------------------------------------------\n");
+  printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
+#endif
+
+}
+#endif
 
 /* shiftgb stuff */

kernel/kutil.cc

@@ -29 +29 @@
 #undef KDEBUG
 #define KDEBUG 2
+#endif
+
+#ifdef DEBUGF5
+#undef DEBUGF5
+//#define DEBUGF5 1
 #endif
 
@@ -72 +77 @@
 #endif
 
+#ifdef DEBUGF5
+#undef DEBUGF5
+#define DEBUGF5 2
+#endif
+
 denominator_list DENOMINATOR_LIST=NULL;
 
@@ -916 +926 @@
     strat->sevS[j] = strat->sevS[j+1];
     strat->S_2_R[j] = strat->S_2_R[j+1];
+  }
+#endif
+  if (strat->lenS!=NULL)
+  {
+#ifdef ENTER_USE_MEMMOVE
+    memmove(&(strat->lenS[i]),&(strat->lenS[i+1]),(strat->sl - i)*sizeof(int));
+#else
+    for (j=i; j<strat->sl; j++) strat->lenS[j] = strat->lenS[j+1];
+#endif
+  }
+  if (strat->lenSw!=NULL)
+  {
+#ifdef ENTER_USE_MEMMOVE
+    memmove(&(strat->lenSw[i]),&(strat->lenSw[i+1]),(strat->sl - i)*sizeof(wlen_type));
+#else
+    for (j=i; j<strat->sl; j++) strat->lenSw[j] = strat->lenSw[j+1];
+#endif
+  }
+  if (strat->fromQ!=NULL)
+  {
+#ifdef ENTER_USE_MEMMOVE
+    memmove(&(strat->fromQ[i]),&(strat->fromQ[i+1]),(strat->sl - i)*sizeof(int));
+#else
+    for (j=i; j<strat->sl; j++)
+    {
+      strat->fromQ[j] = strat->fromQ[j+1];
+    }
+#endif
+  }
+  strat->S[strat->sl] = NULL;
+  strat->sl--;
+}
+
+
+/*2
+*cancels the i-th polynomial in the standardbase s
+*/
+void deleteInSSba (int i,kStrategy strat)
+{
+#ifdef ENTER_USE_MEMMOVE
+  memmove(&(strat->S[i]), &(strat->S[i+1]), (strat->sl - i)*sizeof(poly));
+  memmove(&(strat->sig[i]), &(strat->sig[i+1]), (strat->sl - i)*sizeof(poly));
+  memmove(&(strat->ecartS[i]),&(strat->ecartS[i+1]),(strat->sl - i)*sizeof(int));
+  memmove(&(strat->sevS[i]),&(strat->sevS[i+1]),(strat->sl - i)*sizeof(unsigned long));
+  memmove(&(strat->sevSig[i]),&(strat->sevSig[i+1]),(strat->sl - i)*sizeof(unsigned long));
+  memmove(&(strat->S_2_R[i]),&(strat->S_2_R[i+1]),(strat->sl - i)*sizeof(int));
+  memmove(&(strat->fromS[i]),&(strat->fromS[i+1]),(strat->sl - i)*sizeof(int));
+#else
+  int j;
+  for (j=i; j<strat->sl; j++)
+  {
+    strat->S[j] = strat->S[j+1];
+    strat->sig[j] = strat->sig[j+1];
+    strat->ecartS[j] = strat->ecartS[j+1];
+    strat->sevS[j] = strat->sevS[j+1];
+    strat->sevSig[j] = strat->sevSig[j+1];
+    strat->S_2_R[j] = strat->S_2_R[j+1];
+    strat->fromS[j] = strat->fromS[j+1];
   }
 #endif
@@ -1668 +1736 @@
 
 /*2
+* put the pair (s[i],p)  into the set B, ecart=ecart(p)
+* NOTE: here we need to add the signature-based criteria
+*/
+
+void enterOnePairSig (int i, poly p, poly pSig, int from, int ecart, int isFromQ, kStrategy strat, int atR = -1)
+{
+  assume(i<=strat->sl);
+  if (strat->interred_flag) return;
+
+  int      l,j,compare;
+  poly m1 = NULL,m2 = NULL; // we need the multipliers for the s-polynomial to compute
+              // the corresponding signatures for criteria checks
+  LObject  Lp;
+  poly last;
+  poly pSigMult = p_Copy(pSig,currRing);
+  poly sSigMult = p_Copy(strat->sig[i],currRing);
+  unsigned long pSigMultNegSev,sSigMultNegSev;
+  Lp.i_r = -1;
+
+#ifdef KDEBUG
+  Lp.ecart=0; Lp.length=0;
+#endif
+  /*- computes the lcm(s[i],p) -*/
+  Lp.lcm = pInit();
+  k_GetLeadTerms(p,strat->S[i],currRing,m1,m2,currRing);
+#ifndef HAVE_RATGRING
+  pLcm(p,strat->S[i],Lp.lcm);
+#elif defined(HAVE_RATGRING)
+  //  if (rIsRatGRing(currRing))
+  pLcmRat(p,strat->S[i],Lp.lcm, currRing->real_var_start); // int rat_shift
+#endif
+  pSetm(Lp.lcm);
+
+  // set coeffs of multipliers m1 and m2
+  pSetCoeff0(m1, nInit(1));
+  pSetCoeff0(m2, nInit(1));
+//#if 1
+#ifdef DEBUGF5
+  Print("P1  ");
+  pWrite(pHead(p));
+  Print("FROM: %d\n", from);
+  Print("P2  ");
+  pWrite(pHead(strat->S[i]));
+  Print("FROM: %d\n", strat->fromS[i]);
+  Print("M1  ");
+  pWrite(m1);
+  Print("M2  ");
+  pWrite(m2);
+#endif
+  // get multiplied signatures for testing
+  pSigMult = currRing->p_Procs->pp_Mult_mm(pSigMult,m1,currRing,last);
+  pSigMultNegSev = ~p_GetShortExpVector(pSigMult,currRing);
+  sSigMult = currRing->p_Procs->pp_Mult_mm(sSigMult,m2,currRing,last);
+  sSigMultNegSev = ~p_GetShortExpVector(sSigMult,currRing);
+  
+  pDelete (&m1);
+  pDelete (&m2);
+
+//#if 1
+#ifdef DEBUGF5
+  Print("----------------\n");
+  pWrite(pSigMult);
+  pWrite(sSigMult);
+  Print("----------------\n");
+#endif
+  // testing by syzCrit = F5 Criterion 
+  // testing by rewCrit1 = Rewritten Criterion
+  if  ( strat->syzCrit(pSigMult,pSigMultNegSev,strat) ||
+        strat->syzCrit(sSigMult,sSigMultNegSev,strat) 
+        || strat->rewCrit1(sSigMult,sSigMultNegSev,strat,i+1)
+      )
+  {
+    pDelete(&pSigMult);
+    pDelete(&sSigMult);
+    strat->cp++;
+    pLmFree(Lp.lcm);
+    Lp.lcm=NULL;
+    return;
+  }
+  // in any case Lp is checked up to the next strat->P which is added
+  // to S right after this critical pair creation.
+  // NOTE: this even holds if the 2nd generator gives the bigger signature
+  //       moreover, this improves rewCriterion, 
+  //       i.e. strat->checked > strat->from if and only if the 2nd generator
+  //       gives the bigger signature. 
+  Lp.checked = strat->sl+1;
+  int sigCmp = p_LmCmp(pSigMult,sSigMult,currRing);
+//#if 1
+#if DEBUGF5
+  printf("IN PAIR GENERATION - COMPARING SIGS: %d\n",sigCmp);
+  pWrite(pSigMult);
+  pWrite(sSigMult);
+#endif
+  if(sigCmp==0)
+  {
+    // printf("!!!!   EQUAL SIGS   !!!!\n");
+    // pSig = sSig, delete element due to Rewritten Criterion
+    strat->cp++;
+    pDelete(&pSigMult);
+    pDelete(&sSigMult);
+    pLmFree(Lp.lcm);
+    Lp.lcm=NULL;
+    return;
+  }
+  // at this point it is clear that the pair will be added to L, since it has
+  // passed all tests up to now
+
+  // store from which element this pair comes from for further tests
+  Lp.from = strat->sl+1;    
+  if(sigCmp==pOrdSgn)
+  {
+    // pSig > sSig
+    pDelete (&sSigMult);
+    Lp.sig    = pSigMult;
+    Lp.sevSig = ~pSigMultNegSev;
+  }
+  else
+  {
+    // pSig < sSig
+    pDelete (&pSigMult);
+    Lp.sig    = sSigMult;
+    Lp.sevSig = ~sSigMultNegSev;
+  }
+#if DEBUGF5
+  printf("SIGNATURE OF PAIR:  ");
+  pWrite(Lp.sig);
+#endif
+  /*
+  *the pair (S[i],p) enters B if the spoly != 0
+  */
+  /*-  compute the short s-polynomial -*/
+  if (strat->fromT && !TEST_OPT_INTSTRATEGY)
+    pNorm(p);
+
+  if ((strat->S[i]==NULL) || (p==NULL))
+    return;
+
+  if ((strat->fromQ!=NULL) && (isFromQ!=0) && (strat->fromQ[i]!=0))
+    Lp.p=NULL;
+  else
+  {
+    #ifdef HAVE_PLURAL
+    if ( rIsPluralRing(currRing) )
+    {
+      if(pHasNotCF(p, strat->S[i]))
+      {
+         if(ncRingType(currRing) == nc_lie)
+         {
+             // generalized prod-crit for lie-type
+             strat->cp++;
+             Lp.p = nc_p_Bracket_qq(pCopy(p),strat->S[i]);
+         }
+         else
+        if( ALLOW_PROD_CRIT(strat) )
+        {
+            // product criterion for homogeneous case in SCA
+            strat->cp++;
+            Lp.p = NULL;
+        }
+        else
+        {
+          Lp.p = // nc_CreateSpoly(strat->S[i],p,currRing);
+                nc_CreateShortSpoly(strat->S[i], p, currRing);
+
+          assume(pNext(Lp.p)==NULL); // TODO: this may be violated whenever ext.prod.crit. for Lie alg. is used
+          pNext(Lp.p) = strat->tail; // !!!
+        }
+      }
+      else
+      {
+        Lp.p = // nc_CreateSpoly(strat->S[i],p,currRing);
+              nc_CreateShortSpoly(strat->S[i], p, currRing);
+
+        assume(pNext(Lp.p)==NULL); // TODO: this may be violated whenever ext.prod.crit. for Lie alg. is used
+        pNext(Lp.p) = strat->tail; // !!!
+
+      }
+
+
+#if MYTEST
+      if (TEST_OPT_DEBUG)
+      {
+        PrintS("enterOnePairNormal::\n strat->S[i]: "); pWrite(strat->S[i]);
+        PrintS("p: "); pWrite(p);
+        PrintS("SPoly: "); pWrite(Lp.p);
+      }
+#endif
+
+    }
+    else
+    #endif
+    {
+      assume(!rIsPluralRing(currRing));
+      Lp.p = ksCreateShortSpoly(strat->S[i], p, strat->tailRing);
+#if MYTEST
+      if (TEST_OPT_DEBUG)
+      {
+        PrintS("enterOnePairNormal::\n strat->S[i]: "); pWrite(strat->S[i]);
+        PrintS("p: "); pWrite(p);
+        PrintS("commutative SPoly: "); pWrite(Lp.p);
+      }
+#endif
+
+      }
+  }
+  if (Lp.p == NULL)
+  {
+    /*- the case that the s-poly is 0 -*/
+    if (strat->pairtest==NULL) initPairtest(strat);
+    strat->pairtest[i] = TRUE;/*- hint for spoly(S^[i],p)=0 -*/
+    strat->pairtest[strat->sl+1] = TRUE;
+    /*hint for spoly(S[i],p) == 0 for some i,0 <= i <= sl*/
+    /*
+    *suppose we have (s,r),(r,p),(s,p) and spoly(s,p) == 0 and (r,p) is
+    *still in B (i.e. lcm(r,p) == lcm(s,p) or the leading term of s does not
+    *devide lcm(r,p)). In the last case (s,r) can be canceled if the leading
+    *term of p devides the lcm(s,r)
+    *(this canceling should be done here because
+    *the case lcm(s,p) == lcm(s,r) is not covered in chainCrit)
+    *the first case is handeled in chainCrit
+    */
+    if (Lp.lcm!=NULL) pLmFree(Lp.lcm);
+  }
+  else
+  {
+    /*- the pair (S[i],p) enters B -*/
+    Lp.p1 = strat->S[i];
+    Lp.p2 = p;
+
+    if (
+        (!rIsPluralRing(currRing))
+//      ||  (rIsPluralRing(currRing) && (ncRingType(currRing) != nc_lie))
+       )
+    {
+      assume(pNext(Lp.p)==NULL); // TODO: this may be violated whenever ext.prod.crit. for Lie alg. is used
+      pNext(Lp.p) = strat->tail; // !!!
+    }
+
+    if (atR >= 0)
+    {
+      Lp.i_r1 = strat->S_2_R[i];
+      Lp.i_r2 = atR;
+    }
+    else
+    {
+      Lp.i_r1 = -1;
+      Lp.i_r2 = -1;
+    }
+    strat->initEcartPair(&Lp,strat->S[i],p,strat->ecartS[i],ecart);
+
+    if (TEST_OPT_INTSTRATEGY)
+    {
+      if (!rIsPluralRing(currRing))
+        nDelete(&(Lp.p->coef));
+    }
+
+    l = strat->posInLSba(strat->B,strat->Bl,&Lp,strat);
+    enterL(&strat->B,&strat->Bl,&strat->Bmax,Lp,l);
+  }
+}
+
+/*2
 * put the pair (s[i],p) into the set L, ecart=ecart(p)
 * in the case that s forms a SB of (s)
@@ -1771 +2101 @@
   {
     j = strat->posInL(strat->L,j,&(strat->B[i]),strat);
+    enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
+  }
+  strat->Bl = -1;
+}
+
+/*2
+* merge set B into L
+*/
+void kMergeBintoLSba(kStrategy strat)
+{
+  int j=strat->Ll+strat->Bl+1;
+  if (j>strat->Lmax)
+  {
+    j=((j+setmaxLinc-1)/setmaxLinc)*setmaxLinc;
+    strat->L = (LSet)omReallocSize(strat->L,strat->Lmax*sizeof(LObject),
+                                 j*sizeof(LObject));
+    strat->Lmax=j;
+  }
+  j = strat->Ll;
+  int i;
+  for (i=strat->Bl; i>=0; i--)
+  {
+    j = strat->posInLSba(strat->L,j,&(strat->B[i]),strat);
     enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
   }
@@ -1988 +2341 @@
       j--;
     }
+  }
+}
+/*2
+*the pairset B of pairs of type (s[i],p) is complete now. It will be updated
+*using the chain-criterion in B and L and enters B to L
+*/
+void chainCritSig (poly p,int ecart,kStrategy strat)
+{
+  int i,j,l;
+  kMergeBintoLSba(strat);
+  j = strat->Ll;
+  loop  /*cannot be changed into a for !!! */
+  {
+    if (j <= 0)
+    {
+      /*now L[0] cannot be canceled any more and the tail can be removed*/
+      if (strat->L[0].p2 == strat->tail) strat->L[0].p2 = p;
+      break;
+    }
+    if (strat->L[j].p2 == p)
+    {
+      i = j-1;
+      loop
+      {
+        if (i < 0)  break;
+        if ((strat->L[i].p2 == p) && pLmEqual(strat->L[j].lcm,strat->L[i].lcm))
+        {
+          /*L[i] could be canceled but we search for a better one to cancel*/
+          strat->c3++;
+          if (isInPairsetL(i-1,strat->L[j].p1,strat->L[i].p1,&l,strat)
+              && (pNext(strat->L[l].p) == strat->tail)
+              && (!pLmEqual(strat->L[i].p,strat->L[l].p))
+              && pDivisibleBy(p,strat->L[l].lcm))
+          {
+            /*
+             *"NOT equal(...)" because in case of "equal" the element L[l]
+             *is "older" and has to be from theoretical point of view behind
+             *L[i], but we do not want to reorder L
+             */
+            strat->L[i].p2 = strat->tail;
+            /*
+             *L[l] will be canceled, we cannot cancel L[i] later on,
+             *so we mark it with "tail"
+             */
+            deleteInL(strat->L,&strat->Ll,l,strat);
+            i--;
+          }
+          else
+          {
+            deleteInL(strat->L,&strat->Ll,i,strat);
+          }
+          j--;
+        }
+        i--;
+      }
+    }
+    else if (strat->L[j].p2 == strat->tail)
+    {
+      /*now L[j] cannot be canceled any more and the tail can be removed*/
+      strat->L[j].p2 = p;
+    }
+    j--;
   }
 }
@@ -2342 +2757 @@
 }
 
+/*2
+*(s[0],h),...,(s[k],h) will be put to the pairset L
+*using signatures <= only for signature-based standard basis algorithms
+*/
+void initenterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int isFromQ,kStrategy strat, int atR = -1)
+{
+
+  if ((strat->syzComp==0)
+  || (pGetComp(h)<=strat->syzComp))
+  {
+    int j;
+    BOOLEAN new_pair=FALSE;
+
+    if (pGetComp(h)==0)
+    {
+      /* for Q!=NULL: build pairs (f,q),(f1,f2), but not (q1,q2)*/
+      if ((isFromQ)&&(strat->fromQ!=NULL))
+      {
+        for (j=0; j<=k; j++)
+        {
+          if (!strat->fromQ[j])
+          {
+            new_pair=TRUE;
+            enterOnePairSig(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
+          //Print("j:%d, Ll:%d\n",j,strat->Ll);
+          }
+        }
+      }
+      else
+      {
+        new_pair=TRUE;
+        for (j=0; j<=k; j++)
+        {
+          enterOnePairSig(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
+          //Print("j:%d, Ll:%d\n",j,strat->Ll);
+        }
+      }
+    }
+    else
+    {
+      for (j=0; j<=k; j++)
+      {
+        if ((pGetComp(h)==pGetComp(strat->S[j]))
+        || (pGetComp(strat->S[j])==0))
+        {
+          new_pair=TRUE;
+          enterOnePairSig(j,h,hSig,hFrom,ecart,isFromQ,strat, atR);
+        //Print("j:%d, Ll:%d\n",j,strat->Ll);
+        }
+      }
+    }
+
+    if (new_pair)
+    {
+#ifdef HAVE_RATGRING
+      if (currRing->real_var_start>0)
+        chainCritPart(h,ecart,strat);
+      else
+#endif
+      strat->chainCrit(h,ecart,strat);
+    }
+  }
+}
+
 #ifdef HAVE_RINGS
 /*2
@@ -3100 +3579 @@
   }
  // PrintS("end enterpairs\n");
+}
+
+/*2
+*(s[0],h),...,(s[k],h) will be put to the pairset L(via initenterpairs)
+*superfluous elements in S will be deleted
+*this is a special variant of signature-based algorithms including the
+*signatures for criteria checks
+*/
+void enterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int pos,kStrategy strat, int atR)
+{
+int j=pos;
+
+#ifdef HAVE_RINGS
+assume (!rField_is_Ring(currRing));
+#endif
+
+initenterpairsSig(h,hSig,hFrom,k,ecart,0,strat, atR);
+if ( (!strat->fromT)
+&& ((strat->syzComp==0)
+  ||(pGetComp(h)<=strat->syzComp)))
+{
+  //Print("start clearS k=%d, pos=%d, sl=%d\n",k,pos,strat->sl);
+  unsigned long h_sev = pGetShortExpVector(h);
+  loop
+  {
+    if (j > k) break;
+    clearS(h,h_sev, &j,&k,strat);
+    j++;
+  }
+  //Print("end clearS sl=%d\n",strat->sl);
+}
+// PrintS("end enterpairs\n");
 }
 
@@ -3953 +4464 @@
 * e is the ecart of p
 * set[length] is the smallest element in set with respect
+* to the signature order
+*/
+int posInLSig (const LSet set, const int length,
+            LObject* p,const kStrategy strat)
+{
+if (length<0) return 0;
+if (pLmCmp(set[length].sig,p->sig)== pOrdSgn)
+  return length+1;
+
+int i;
+int an = 0;
+int en= length;
+loop
+{
+  if (an >= en-1)
+  {
+    if (pLmCmp(set[an].sig,p->sig) == pOrdSgn) return en;
+    return an;
+  }
+  i=(an+en) / 2;
+  if (pLmCmp(set[i].sig,p->sig) == pOrdSgn) an=i;
+  else                                      en=i;
+  /*aend. fuer lazy == in !=- machen */
+}
+}
+
+/*2
+* 
+* is only used in F5C, must ensure that the interreduction process does add new
+* critical pairs to strat->L only behind all other critical pairs which are
+* still in strat->L!
+*/
+int posInLF5C (const LSet set, const int length,
+            LObject* p,const kStrategy strat)
+{
+  return strat->Ll+1;
+}
+
+/*2
+* looks up the position of polynomial p in set
+* e is the ecart of p
+* set[length] is the smallest element in set with respect
 * to the ordering-procedure totaldegree,pComp
 */
@@ -5018 +5571 @@
   }
 }
+
+void initSLSba (ideal F, ideal Q,kStrategy strat)
+{
+  int   i,j,pos, ctr=0, ps=0;
+  if (Q!=NULL) i=((IDELEMS(Q)+(setmaxTinc-1))/setmaxTinc)*setmaxTinc;
+  else i=setmaxT;
+  strat->ecartS =   initec(i);
+  strat->fromS  =   initec(i);
+  strat->sevS   =   initsevS(i);
+  strat->sevSig =   initsevS(i);
+  strat->S_2_R  =   initS_2_R(i);
+  strat->fromQ  =   NULL;
+  strat->Shdl   =   idInit(i,F->rank);
+  strat->S      =   strat->Shdl->m;
+  strat->sig    =   (poly *)omAlloc0(i*sizeof(poly));
+  if (!strat->incremental)
+  {
+    strat->syz    = (poly *)omAlloc0(i*sizeof(poly));
+    strat->sevSyz = initsevS(i);
+    strat->syzmax = i;
+    strat->syzl   = 0;
+  }
+  /*- put polys into S -*/
+  if (Q!=NULL)
+  {
+    strat->fromQ=initec(i);
+    memset(strat->fromQ,0,i*sizeof(int));
+    for (i=0; i<IDELEMS(Q); i++)
+    {
+      if (Q->m[i]!=NULL)
+      {
+        LObject h;
+        h.p = pCopy(Q->m[i]);
+        if (pOrdSgn==-1)
+        {
+          deleteHC(&h,strat);
+        }
+        if (TEST_OPT_INTSTRATEGY)
+        {
+          //pContent(h.p);
+          h.pCleardenom(); // also does a pContent
+        }
+        else
+        {
+          h.pNorm();
+        }
+        if (h.p!=NULL)
+        {
+          strat->initEcart(&h);
+          if (strat->sl==-1)
+            pos =0;
+          else
+          {
+            pos = posInS(strat,strat->sl,h.p,h.ecart);
+          }
+          h.sev = pGetShortExpVector(h.p);
+          strat->enterS(h,pos,strat,-1);
+          strat->fromQ[pos]=1;
+        }
+      }
+    }
+  }
+  for (i=0; i<IDELEMS(F); i++)
+  {
+    if (F->m[i]!=NULL)
+    {
+      LObject h;
+      h.p = pCopy(F->m[i]);
+      h.sig = pOne();
+      //h.sig = pInit();
+      //p_SetCoeff(h.sig,nInit(1),currRing);
+      p_SetComp(h.sig,i+1,currRing);
+      // if we are working with the Schreyer order we generate it 
+      // by multiplying the initial signatures with the leading monomial
+      // of the corresponding initial polynomials generating the ideal
+      // => we can keep the underlying monomial order and get a Schreyer 
+      //    order without any bigger overhead
+      if (!strat->incremental)
+      {
+        p_ExpVectorAdd (h.sig,F->m[i],currRing);  
+      }
+      h.sevSig = pGetShortExpVector(h.sig);
+#ifdef DEBUGF5
+      pWrite(h.p);
+      pWrite(h.sig);
+#endif
+      if (h.p!=NULL)
+      {
+        if (pOrdSgn==-1)
+        {
+          cancelunit(&h);  /*- tries to cancel a unit -*/
+          deleteHC(&h, strat);
+        }
+        if (h.p!=NULL)
+        {
+          if (TEST_OPT_INTSTRATEGY)
+          {
+            //pContent(h.p);
+            h.pCleardenom(); // also does a pContent
+          }
+          else
+          {
+            h.pNorm();
+          }
+          strat->initEcart(&h);
+          if (strat->Ll==-1)
+            pos =0;
+          else
+            pos = strat->posInLSba(strat->L,strat->Ll,&h,strat);
+          h.sev = pGetShortExpVector(h.p);
+          enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
+        }
+      }
+      /*
+      if (!strat->incremental)
+      {
+        for(j=0;j<i;j++)
+        {
+          strat->syz[ctr] = pCopy(F->m[j]);
+          p_SetCompP(strat->syz[ctr],i+1,currRing);
+          // add LM(F->m[i]) to the signature to get a Schreyer order
+          // without changing the underlying polynomial ring at all
+          p_ExpVectorAdd (strat->syz[ctr],F->m[i],currRing);  
+          // since p_Add_q() destroys all input
+          // data we need to recreate help 
+          // each time
+          poly help = pCopy(F->m[i]);
+          p_SetCompP(help,j+1,currRing);
+          pWrite(strat->syz[ctr]);
+          pWrite(help);
+          printf("%d\n",pLmCmp(strat->syz[ctr],help));
+          strat->syz[ctr] = p_Add_q(strat->syz[ctr],help,currRing);
+          printf("%d. SYZ  ",ctr);
+          pWrite(strat->syz[ctr]);
+          strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
+          ctr++;
+        }
+        strat->syzl = ps;
+      }
+      */
+    }
+  }
+  /*- test, if a unit is in F -*/
+
+  if ((strat->Ll>=0)
+#ifdef HAVE_RINGS
+       && nIsUnit(pGetCoeff(strat->L[strat->Ll].p))
+#endif
+       && pIsConstant(strat->L[strat->Ll].p))
+  {
+    while (strat->Ll>0) deleteInL(strat->L,&strat->Ll,strat->Ll-1,strat);
+  }
+}
+
+void initSyzRules (kStrategy strat)
+{
+  if( strat->S[0] )
+  {
+    if( strat->S[1] )
+    {
+      omFreeSize(strat->syzIdx,(strat->syzidxmax)*sizeof(int));
+      omFreeSize(strat->sevSyz,(strat->syzmax)*sizeof(unsigned long));
+      omFreeSize(strat->syz,(strat->syzmax)*sizeof(poly));
+    }
+    int i, j, k, diff, comp, comp_old, ps=0, ctr=0;
+    /************************************************************
+     * computing the length of the syzygy array needed
+     ***********************************************************/
+    for(i=1; i<=strat->sl; i++)
+    {
+      if (pGetComp(strat->sig[i-1]) != pGetComp(strat->sig[i]))
+      { 
+        ps += i;
+      }
+    }
+    ps += strat->sl+1;
+    //comp              = pGetComp (strat->P.sig);
+    comp              = strat->currIdx;
+    strat->syzIdx     = initec(comp);
+    strat->sevSyz     = initsevS(ps);
+    strat->syz        = (poly *)omAlloc(ps*sizeof(poly));
+    strat->syzl       = strat->syzmax = ps;
+    strat->syzidxmax  = comp;
+#ifdef DEBUGF5 || DEBUGF51
+    printf("------------- GENERATING SYZ RULES NEW ---------------\n");
+#endif
+    i = 1; 
+    j = 0;
+    /************************************************************
+     * generating the leading terms of the principal syzygies
+     ***********************************************************/
+    while (i <= strat->sl)
+    {
+      /**********************************************************
+       * principal syzygies start with component index 2
+       * the array syzIdx starts with index 0
+       * => the rules for a signature with component comp start
+       *    at strat->syz[strat->syzIdx[comp-2]] !
+       *********************************************************/
+      if (pGetComp(strat->sig[i-1]) != pGetComp(strat->sig[i]))
+      {
+        comp      = pGetComp(strat->sig[i]);
+        comp_old  = pGetComp(strat->sig[i-1]);
+        diff      = comp - comp_old - 1;
+        // diff should be zero, but sometimes also the initial generating
+        // elements of the input ideal reduce to zero. then there is an
+        // index-gap between the signatures. for these inbetween signatures we
+        // can safely set syzIdx[j] = 0 as no such element will be ever computed
+        // in the following.
+        // doing this, we keep the relation "j = comp - 2" alive, which makes
+        // jumps way easier when checking criteria
+        while (diff>0)
+        {
+          strat->syzIdx[j]  = 0;
+          diff--;
+          j++;
+        }
+        strat->syzIdx[j]  = ctr;
+        j++;
+        for (k = 0; k<i; k++)
+        {
+          poly p          = pOne();
+          pLcm(strat->S[k],strat->S[i],p);
+          strat->syz[ctr] = p;
+          p_SetCompP (strat->syz[ctr], comp, currRing);
+          poly q          = p_Copy(p, currRing);
+          q               = p_Neg (q, currRing);
+          p_SetCompP (q, p_GetComp(strat->sig[k], currRing), currRing);
+          strat->syz[ctr] = p_Add_q (strat->syz[ctr], q, currRing);
+#ifdef DEBUGF5 || DEBUGF51
+          pWrite(strat->syz[ctr]);
+#endif
+          strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
+          ctr++;
+        }
+      }
+      i++;
+    }
+    /**************************************************************
+    * add syzygies for upcoming first element of new iteration step
+    **************************************************************/
+    comp      = strat->currIdx;
+    comp_old  = pGetComp(strat->sig[i-1]);
+    diff      = comp - comp_old - 1;
+    // diff should be zero, but sometimes also the initial generating
+    // elements of the input ideal reduce to zero. then there is an
+    // index-gap between the signatures. for these inbetween signatures we
+    // can safely set syzIdx[j] = 0 as no such element will be ever computed
+    // in the following.
+    // doing this, we keep the relation "j = comp - 2" alive, which makes
+    // jumps way easier when checking criteria
+    while (diff>0)
+    {
+      strat->syzIdx[j]  = 0;
+      diff--;
+      j++;
+    }
+    strat->syzIdx[j]  = ctr;
+    for (k = 0; k<strat->sl+1; k++)
+    {
+      strat->syz[ctr] = p_Copy (pHead(strat->S[k]), currRing);
+      p_SetCompP (strat->syz[ctr], comp, currRing);
+      poly q          = p_Copy (pHead(strat->L[strat->Ll].p), currRing);
+      q               = p_Neg (q, currRing);
+      p_SetCompP (q, p_GetComp(strat->sig[k], currRing), currRing);
+      strat->syz[ctr] = p_Add_q (strat->syz[ctr], q, currRing);
+//#if 1
+#if DEBUGF5 || DEBUGF51
+      printf("..");
+      pWrite(strat->syz[ctr]);
+#endif
+      strat->sevSyz[ctr] = p_GetShortExpVector(strat->syz[ctr],currRing);
+      ctr++;
+    }
+//#if 1
+#ifdef DEBUGF5
+    Print("Principal syzygies:\n");
+    Print("--------------------------------\n");
+    for(i=0;i<=ps-1;i++)
+    {
+      pWrite(strat->syz[i]);
+    }
+    Print("--------------------------------\n");
+#endif
+
+  }
+}
+
 
 
@@ -5665 +6506 @@
 
 /*2
+* -puts p to the standardbasis s at position at
+* -saves the result in S
+*/
+void enterSSba (LObject p,int atS,kStrategy strat, int atR)
+{
+  int i;
+  strat->news = TRUE;
+  /*- puts p to the standardbasis s at position at -*/
+  if (strat->sl == IDELEMS(strat->Shdl)-1)
+  {
+    strat->sevS = (unsigned long*) omRealloc0Size(strat->sevS,
+                                    IDELEMS(strat->Shdl)*sizeof(unsigned long),
+                                    (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(unsigned long));
+    strat->sevSig = (unsigned long*) omRealloc0Size(strat->sevSig,
+                                    IDELEMS(strat->Shdl)*sizeof(unsigned long),
+                                    (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(unsigned long));
+    strat->ecartS = (intset)omReallocSize(strat->ecartS,
+                                          IDELEMS(strat->Shdl)*sizeof(int),
+                                          (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(int));
+    strat->fromS = (intset)omReallocSize(strat->fromS,
+                                          IDELEMS(strat->Shdl)*sizeof(int),
+                                          (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(int));
+    strat->S_2_R = (int*) omRealloc0Size(strat->S_2_R,
+                                         IDELEMS(strat->Shdl)*sizeof(int),
+                                         (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                  *sizeof(int));
+    if (strat->lenS!=NULL)
+      strat->lenS=(int*)omRealloc0Size(strat->lenS,
+                                       IDELEMS(strat->Shdl)*sizeof(int),
+                                       (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                 *sizeof(int));
+    if (strat->lenSw!=NULL)
+      strat->lenSw=(wlen_type*)omRealloc0Size(strat->lenSw,
+                                       IDELEMS(strat->Shdl)*sizeof(wlen_type),
+                                       (IDELEMS(strat->Shdl)+setmaxTinc)
+                                                 *sizeof(wlen_type));
+    if (strat->fromQ!=NULL)
+    {
+      strat->fromQ = (intset)omReallocSize(strat->fromQ,
+                                    IDELEMS(strat->Shdl)*sizeof(int),
+                                    (IDELEMS(strat->Shdl)+setmaxTinc)*sizeof(int));
+    }
+    pEnlargeSet(&strat->S,IDELEMS(strat->Shdl),setmaxTinc);
+    pEnlargeSet(&strat->sig,IDELEMS(strat->Shdl),setmaxTinc);
+    IDELEMS(strat->Shdl)+=setmaxTinc;
+    strat->Shdl->m=strat->S;
+  }
+  // in a signature-based algorithm the following situation will never
+  // appear due to the fact that the critical pairs are already sorted
+  // by increasing signature.
+  if (atS <= strat->sl)
+  {
+#ifdef ENTER_USE_MEMMOVE
+// #if 0
+    memmove(&(strat->S[atS+1]), &(strat->S[atS]),
+            (strat->sl - atS + 1)*sizeof(poly));
+    memmove(&(strat->ecartS[atS+1]), &(strat->ecartS[atS]),
+            (strat->sl - atS + 1)*sizeof(int));
+    memmove(&(strat->fromS[atS+1]), &(strat->fromS[atS]),
+            (strat->sl - atS + 1)*sizeof(int));
+    memmove(&(strat->sevS[atS+1]), &(strat->sevS[atS]),
+            (strat->sl - atS + 1)*sizeof(unsigned long));
+    memmove(&(strat->S_2_R[atS+1]), &(strat->S_2_R[atS]),
+            (strat->sl - atS + 1)*sizeof(int));
+    if (strat->lenS!=NULL)
+    memmove(&(strat->lenS[atS+1]), &(strat->lenS[atS]),
+            (strat->sl - atS + 1)*sizeof(int));
+    if (strat->lenSw!=NULL)
+    memmove(&(strat->lenSw[atS+1]), &(strat->lenSw[atS]),
+            (strat->sl - atS + 1)*sizeof(wlen_type));
+#else
+    for (i=strat->sl+1; i>=atS+1; i--)
+    {
+      strat->S[i] = strat->S[i-1];
+      strat->ecartS[i] = strat->ecartS[i-1];
+      strat->fromS[i] = strat->fromS[i-1];
+      strat->sevS[i] = strat->sevS[i-1];
+      strat->S_2_R[i] = strat->S_2_R[i-1];
+    }
+    if (strat->lenS!=NULL)
+    for (i=strat->sl+1; i>=atS+1; i--)
+      strat->lenS[i] = strat->lenS[i-1];
+    if (strat->lenSw!=NULL)
+    for (i=strat->sl+1; i>=atS+1; i--)
+      strat->lenSw[i] = strat->lenSw[i-1];
+#endif
+  }
+  if (strat->fromQ!=NULL)
+  {
+#ifdef ENTER_USE_MEMMOVE
+    memmove(&(strat->fromQ[atS+1]), &(strat->fromQ[atS]),
+                  (strat->sl - atS + 1)*sizeof(int));
+#else
+    for (i=strat->sl+1; i>=atS+1; i--)
+    {
+      strat->fromQ[i] = strat->fromQ[i-1];
+    }
+#endif
+    strat->fromQ[atS]=0;
+  }
+
+  /*- save result -*/
+  strat->S[atS] = p.p;
+  strat->sig[atS] = p.sig; // TODO: get ths correct signature in here!
+  if (strat->honey) strat->ecartS[atS] = p.ecart;
+  if (p.sev == 0)
+    p.sev = pGetShortExpVector(p.p);
+  else
+    assume(p.sev == pGetShortExpVector(p.p));
+  strat->sevS[atS] = p.sev;
+  // during the interreduction process of a signature-based algorithm we do not
+  // compute the signature at this point, but when the whole interreduction
+  // process finishes, i.e. f5c terminates!
+  if (p.sig != NULL)
+  {
+    if (p.sevSig == 0)
+      p.sevSig = pGetShortExpVector(p.sig);
+    else
+      assume(p.sevSig == pGetShortExpVector(p.sig));
+    strat->sevSig[atS] = p.sevSig; // TODO: get the correct signature in here!
+  }
+  strat->ecartS[atS] = p.ecart;
+  strat->fromS[atS] = p.from;
+  strat->S_2_R[atS] = atR;
+  strat->sl++;
+#ifdef DEBUGF5
+  int k;
+  Print("--- LIST S: %d ---\n",strat->sl);
+  for(k=0;k<=strat->sl;k++)
+  {
+    pWrite(strat->sig[k]);
+  }
+  Print("--- LIST S END ---\n");
+#endif
+}
+
+/*2
 * puts p to the set T at position atT
 */
@@ -5735 +6717 @@
   kTest_T(&(strat->T[atT]));
 }
+
+/*2
+* puts signature p.sig to the set syz
+*/
+void enterSyz(LObject p, kStrategy strat)
+{
+  int i = strat->syzl;
+
+  strat->newt = TRUE;
+  if (strat->syzl == strat->syzmax)
+  {
+    pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
+    strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
+                                    (strat->syzmax)*sizeof(unsigned long),
+                                    ((strat->syzmax)+setmaxTinc)
+                                                  *sizeof(unsigned long));
+    strat->syzmax += setmaxTinc;
+  }
+  strat->syz[i] = p.sig;
+  strat->sevSyz[i] = p.sevSig;
+  strat->syzl++;
+#ifdef DEBUGF5
+  Print("last element in strat->syz: %d--%d  ",i+1,strat->syzmax);
+  pWrite(strat->syz[i]);
+#endif
+  // recheck pairs in strat->L with new rule and delete correspondingly
+  int cc = strat->Ll;
+  while (cc>-1)
+  {
+    if (p_LmShortDivisibleBy( strat->syz[strat->syzl-1], strat->sevSyz[strat->syzl-1], 
+                              strat->L[cc].sig, ~strat->L[cc].sevSig, currRing))
+    {
+      deleteInL(strat->L,&strat->Ll,cc,strat);
+    }
+    cc--;
+  }
+
+}
+
 
 void initHilbCrit(ideal/*F*/, ideal /*Q*/, intvec **hilb,kStrategy strat)
@@ -5771 +6792 @@
   * - in local rings, - in lex order case, -in ring over extensions */
   strat->noTailReduction = !TEST_OPT_REDTAIL;
+
+#ifdef HAVE_PLURAL
+  // and r is plural_ring
+  //  hence this holds for r a rational_plural_ring
+  if( rIsPluralRing(currRing) || (rIsSCA(currRing) && !strat->z2homog) )
+  {    //or it has non-quasi-comm type... later
+    strat->sugarCrit = FALSE;
+    strat->Gebauer = FALSE;
+    strat->honey = FALSE;
+  }
+#endif
+
+#ifdef HAVE_RINGS
+  // Coefficient ring?
+  if (rField_is_Ring(currRing))
+  {
+    strat->sugarCrit = FALSE;
+    strat->Gebauer = FALSE ;
+    strat->honey = FALSE;
+  }
+#endif
+  #ifdef KDEBUG
+  if (TEST_OPT_DEBUG)
+  {
+    if (strat->homog) PrintS("ideal/module is homogeneous\n");
+    else              PrintS("ideal/module is not homogeneous\n");
+  }
+  #endif
+}
+
+void initSbaCrit(kStrategy strat)
+{
+  //strat->enterOnePair=enterOnePairNormal;
+  strat->enterOnePair = enterOnePairNormal;
+  //strat->chainCrit=chainCritNormal;
+  strat->chainCrit    = chainCritSig;
+  /******************************************
+   * rewCrit1 and rewCrit2 are already set in
+   * kSba() in kstd1.cc
+   *****************************************/
+  //strat->rewCrit1     = faugereRewCriterion;
+  if (strat->incremental)
+  {
+    strat->syzCrit  = syzCriterionInc;
+  }
+  else
+  {
+    strat->syzCrit  = syzCriterion;
+  }
+#ifdef HAVE_RINGS
+  if (rField_is_Ring(currRing))
+  {
+    strat->enterOnePair=enterOnePairRing;
+    strat->chainCrit=chainCritRing;
+  }
+#endif
+#ifdef HAVE_RATGRING
+  if (rIsRatGRing(currRing))
+  {
+     strat->chainCrit=chainCritPart;
+     /* enterOnePairNormal get rational part in it */
+  }
+#endif
+
+  strat->sugarCrit =        TEST_OPT_SUGARCRIT;
+  strat->Gebauer =          strat->homog || strat->sugarCrit;
+  strat->honey =            !strat->homog || strat->sugarCrit || TEST_OPT_WEIGHTM;
+  if (TEST_OPT_NOT_SUGAR) strat->honey = FALSE;
+  strat->pairtest = NULL;
+  /* alway use tailreduction, except:
+  * - in local rings, - in lex order case, -in ring over extensions */
+  strat->noTailReduction = !TEST_OPT_REDTAIL;
+  //strat->noTailReduction = NULL;
 
 #ifdef HAVE_PLURAL

kernel/kutil.h

@@ -67 +67 @@
 {
 public:
+  unsigned long sevSig;
+  poly sig;   // the signature of the element
   poly p;       // Lm(p) \in currRing Tail(p) \in tailRing
   poly t_p;     // t_p \in tailRing: as monomials Lm(t_p) == Lm(p)
@@ -77 +79 @@
     i_r;        // index of TObject in R set, or -1 if not in T
   BOOLEAN is_normalized; // true, if pNorm was called on p, false otherwise
+  // used in incremental sba() with F5C:
+  // we know some of the redundant elements in 
+  // strat->T beforehand, so we can just discard
+  // them and do not need to consider them in the
+  // interreduction process
+  BOOLEAN is_redundant;
+  // used in sba's sig-safe reduction:
+  // sometimes we already know that a reducer
+  // is sig-safe, so no need for a real
+  // sig-safeness check
+  BOOLEAN is_sigsafe;
+
 
 #ifdef HAVE_PLURAL  
@@ -167 +181 @@
 public:
   unsigned long sev;
+  unsigned long from; // from which polynomial it comes from
+            // this is important for signature-based
+            // algorithms
+  unsigned long checked; // this is the index of S up to which
+                      // the corresponding LObject was already checked in
+                      // critical pair creation => when entering the
+                      // reduction process it is enough to start a second
+                      // rewritten criterion check from checked+1 onwards
   poly  p1,p2; /*- the pair p comes from,
                  lm(pi) in currRing, tail(pi) in tailring -*/
@@ -252 +274 @@
   kStrategy next;
   int (*red)(LObject * L,kStrategy strat);
+  int (*red2)(LObject * L,kStrategy strat);
   void (*initEcart)(LObject * L);
   int (*posInT)(const TSet T,const int tl,LObject &h);
+  int (*posInLSba)(const LSet set, const int length,
+                LObject* L,const kStrategy strat);
   int (*posInL)(const LSet set, const int length,
                 LObject* L,const kStrategy strat);
@@ -262 +287 @@
   void (*enterOnePair) (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR /*= -1*/);
   void (*chainCrit) (poly p,int ecart,kStrategy strat);
+  BOOLEAN (*syzCrit) (poly sig, unsigned long not_sevSig, kStrategy strat);
+  BOOLEAN (*rewCrit1) (poly sig, unsigned long not_sevSig, kStrategy strat, int start /*= 0*/);
+  BOOLEAN (*rewCrit2) (poly sig, unsigned long not_sevSig, kStrategy strat, int start /*= 0*/);
   pFDegProc pOrigFDeg;
   pLDegProc pOrigLDeg;
@@ -272 +300 @@
   ideal M; /*set of minimal generators*/
   polyset S;
+  polyset syz;
+  polyset sig;
   intset ecartS;
+  intset fromS; // from which S[i] S[j] comes from
+                // this is important for signature-based
+                // algorithms
+  intset syzIdx;// index in the syz array at which the first
+                // syzygy of component i comes up
+                // important for signature-based algorithms
+  BOOLEAN incremental;
+  unsigned long currIdx;
+  int max_lower_index;
   intset lenS;
   wlen_set lenSw; /* for tgb.ccc */
   intset fromQ;
   unsigned long* sevS;
+  unsigned long* sevSyz;
+  unsigned long* sevSig;
   unsigned long* sevT;
   TSet T;
@@ -306 +347 @@
   int cv; // in shift bases: counting V criterion
   int sl,mu;
+  int syzl,syzmax,syzidxmax;
   int tl,tmax;
   int Ll,Lmax;
@@ -367 +409 @@
 void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
 void deleteInS (int i,kStrategy strat);
+void deleteInSSba (int i,kStrategy strat);
 void cleanT (kStrategy strat);
 static inline LSet initL (int nr=setmaxL)
@@ -373 +416 @@
 void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
 void enterSBba (LObject p,int atS,kStrategy strat, int atR = -1);
+void enterSSba (LObject p,int atS,kStrategy strat, int atR = -1);
 void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
 void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
@@ -381 +425 @@
 int posInT2 (const TSet set,const int length,LObject &p);
 int posInT11 (const TSet set,const int length,LObject &p);
+int posInTSig (const TSet set,const int length,LObject &p);
 int posInT110 (const TSet set,const int length,LObject &p);
 int posInT13 (const TSet set,const int length,LObject &p);
@@ -396 +441 @@
 
 void reorderS (int* suc,kStrategy strat);
+int posInLF5C (const LSet set, const int length,
+               LObject* L,const kStrategy strat);
+int posInLSig (const LSet set, const int length,
+               LObject* L,const kStrategy strat);
 int posInL0 (const LSet set, const int length,
              LObject* L,const kStrategy strat);
@@ -437 +486 @@
 int redLazy (LObject* h,kStrategy strat);
 int redHomog (LObject* h,kStrategy strat);
+int redSig (LObject* h,kStrategy strat);
+//adds hSig to be able to check with F5's criteria when entering pairs!
+void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
 void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
 void entersets (LObject h);
@@ -452 +504 @@
 void initS (ideal F, ideal Q,kStrategy strat);
 void initSL (ideal F, ideal Q,kStrategy strat);
+void initSLSba (ideal F, ideal Q,kStrategy strat);
+/*************************************************
+ * when initializing a new bunch of principal 
+ * syzygies at the beginning of a new iteration
+ * step in a signature-based algorithm we 
+ * compute ONLY the leading elements of those
+ * syzygies, NOT the whole syzygy
+ * NOTE: this needs to be adjusted for a more
+ * general approach on signature-based algorithms
+ ***********************************************/
+void initSyzRules (kStrategy strat);
 void updateS(BOOLEAN toT,kStrategy strat);
+void enterSyz (LObject p,kStrategy strat);
 void enterT (LObject p,kStrategy strat, int atT = -1);
 void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
 void HEckeTest (poly pp,kStrategy strat);
 void initBuchMoraCrit(kStrategy strat);
+void initSbaCrit(kStrategy strat);
 void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
 void initBuchMoraPos(kStrategy strat);
+void initSbaPos(kStrategy strat);
 void initBuchMora (ideal F, ideal Q,kStrategy strat);
+void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
 void exitBuchMora (kStrategy strat);
+void exitSba (kStrategy strat);
 void updateResult(ideal r,ideal Q,kStrategy strat);
 void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
 void kFreeStrat(kStrategy strat);
 void enterOnePairNormal (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
+void enterOnePairSig (int i,poly p,poly pSig,int ecart, int isFromQ,kStrategy strat, int atR);
 void chainCritNormal (poly p,int ecart,kStrategy strat);
+void chainCritSig (poly p,int ecart,kStrategy strat);
 BOOLEAN homogTest(polyset F, int Fmax);
 BOOLEAN newHEdge(kStrategy strat);
+BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
+BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
+KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
+BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
+BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
+BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
 // returns index of p in TSet, or -1 if not found
 int kFindInT(poly p, TSet T, int tlength);
@@ -541 +617 @@
 poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
+ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
+ideal ssg (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
+ideal ssgincschreyer (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
+ideal ssgnoninc (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
 poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
 ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
 void initBba(ideal F,kStrategy strat);
+void initSba(ideal F,kStrategy strat);
+void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg, 
+          int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
+          intvec *w,intvec *hilb );
 
 /***************************************************************
@@ -569 +653 @@
                  kStrategy strat = NULL);
 
+// Reduces PR with PW
+// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
+// Changes: PR
+// Const:   PW
+// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
+// If strat != NULL, tailRing is changed if reduction would violate exp bound
+// of tailRing
+// Returns: 0 everything ok, no tailRing change
+//          1 tailRing has successfully changed (strat != NULL)
+//          2 no reduction performed, tailRing needs to be changed first
+//            (strat == NULL)
+//          3 no reduction performed, not sig-safe!!!
+//         -1 tailRing change could not be performed due to exceeding exp
+//            bound of currRing
+int ksReducePolySig(LObject* PR,
+                 TObject* PW,
+                 long idx,
+                 poly spNoether = NULL,
+                 number *coef = NULL,
+                 kStrategy strat = NULL);
+
 // Reduces PR at Current->next with PW
 // Assumes PR != NULL, Current contained in PR
@@ -638 +743 @@
 void kDebugPrint(kStrategy strat);
 
+// getting sb order for sba computations
+ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
 
 KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,