Changeset 3f58e0f in git

Timestamp:

Dec 21, 2017, 8:26:44 PM (5 years ago)

Author:

Karim Abou Zeid <karim23697@…>

Branches:

(u'spielwiese', '91fdef05f09f54b8d58d92a472e9c4a43aa4656f')

Children:

cb8124385abff6727059b05b1827fc734f8c42c8

Parents:

86d5ade6a65b37e57178a78ac1ba4a5b1a5d5e1044168ad1298cc934d410b44610566740ef33fc03

Message:

Merge branch 'spielwiese' into stable

Location:

Singular/LIB

Files:

• fpadim.lib (modified) (43 diffs)
• fpaprops.lib (added)
• freegb.lib (modified) (17 diffs)
• ncfrac.lib (added)
• ncloc.lib (added)
• olga.lib (added)

Singular/LIB/fpadim.lib

@@ -4 +4 @@
 info="
 LIBRARY: fpadim.lib     Algorithms for quotient algebras in the letterplace case
-AUTHORS: Grischa Studzinski,       grischa.studzinski@rwth-aachen.de
+AUTHORS: Grischa Studzinski,       grischa.studzinski at rwth-aachen.de
+@*       Viktor Levandovskyy,      viktor.levandovskyy at math.rwth-aachen.de
+@*       Karim Abou Zeid,          karim.abou.zeid at rwth-aachen.de
 
 Support: Joint projects LE 2697/2-1 and KR 1907/3-1 of the Priority Programme SPP 1489:
-@* 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
-@* of the German DFG
-
-OVERVIEW: Given the free algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
+'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
+of the German DFG
+and Project II.6 of the transregional collaborative research centre
+SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG
+
+OVERVIEW: Given the free associative algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
       GB = {g_1,..,g_w}, one is interested in the K-dimension and in the
       explicit K-basis of A/<GB>.
       Therefore one is interested in the following data:
-@*      - the Ufnarovskij graph induced by GB
-@*      - the mistletoes of A/<GB>
-@*      - the K-dimension of A/<GB>
-@*      - the Hilbert series of A/<GB>
-
-      The Ufnarovskij graph is used to determine whether A/<GB> has finite
-      K-dimension. One has to check if the graph contains cycles.
-      For the whole theory we refer to [ufna]. Given a
-      reduced set of monomials GB one can define the basis tree, whose vertex
-      set V consists of all normal monomials w.r.t. GB. For every two
-      monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
-      only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
-      set M = {m in V | there is no edge from m to another monomial in V} is
-      called the set of mistletoes. As one can easily see it consists of
-      the endpoints of the graph. Since there is a unique path to every
-      monomial in V the whole graph can be described only from the knowledge
-      of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
-      knowing the mistletoes we know a K-basis. The name mistletoes was given
-      to those points because of these miraculous value and the algorithm is
-      named sickle, because a sickle is the tool to harvest mistletoes.
-      For more details see [studzins]. This package uses the Letterplace
-      format introduced by [lls]. The algebra can either be represented as a
-      Letterplace ring or via integer vectors: Every variable will only be
-      represented by its number, so variable one is represented as 1,
-      variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will
-      be stored as (1,3,2). Multiplication is concatenation. Note that there
-      is no algorithm for computing the normal form needed for our case.
-      Note that the name fpadim.lib is short for dimensions of finite
-      presented algebras.
+      - the Ufnarovskij graph induced by GB
+      - the mistletoes of A/<GB> (special monomials in a basis)
+      - the K-dimension of A/<GB>
+      - the Hilbert series of A/<GB>
+
+@*      The Ufnarovskij graph is used to determine whether A/<GB> has finite
+@*      K-dimension. One has to check if the graph contains cycles.
+@*      For the whole theory we refer to [ufna]. Given a
+@*      reduced set of monomials GB one can define the basis tree, whose vertex
+@*      set V consists of all normal monomials w.r.t. GB. For every two
+@*      monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
+@*      only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
+@*      set M = {m in V | there is no edge from m to another monomial in V} is
+@*      called the set of mistletoes. As one can easily see it consists of
+@*      the endpoints of the graph. Since there is a unique path to every
+@*      monomial in V the whole graph can be described only from the knowledge
+@*      of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
+@*      knowing the mistletoes we know a K-basis. The name mistletoes was given
+@*      to those points because of these miraculous value and the algorithm is
+@*      named sickle, because a sickle is the tool to harvest mistletoes.
+@*      For more details see [studzins]. This package uses the Letterplace
+@*      format introduced by [lls]. The algebra can either be represented as a
+@*      Letterplace ring or via integer vectors: Every variable will only be
+@*      represented by its number, so variable one is represented as 1,
+@*      variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will
+@*      be stored as (1,3,2). Multiplication is concatenation. Note that the
+@*      approach in this library does not need an algorithm for computing the normal
+@*      form yet. Note that the name fpadim.lib is short for dimensions of
+@*      finite presented algebras.
+@*
 
 REFERENCES:
@@ -48 +53 @@
 @*   [ufna] Ufnarovskij: Combinatorical and asymptotic methods in algebra, 1990
 @*   [lls] Levandovskyy, La Scala: Letterplace ideals and non-commutative
-          Groebner bases, 2009
+Groebner bases, 2009
 @*   [studzins] Studzinski: Dimension computations in non-commutative,
-                     associative algebras, Diploma thesis, RWTH Aachen, 2010
-
-Assumptions:
-@* - basering is always a Letterplace ring
-@* - all intvecs correspond to Letterplace monomials
-@* - if you specify a different degree bound d,
-     d <= attrib(basering,uptodeg) should hold.
-@* In the procedures below, 'iv' stands for intvec representation
-  and 'lp' for the letterplace representation of monomials
+associative algebras, Diploma thesis, RWTH Aachen, 2010
+
+NOTE:
+- basering is always a Letterplace ring
+- all intvecs correspond to Letterplace monomials
+- if you specify a different degree bound d, d <= attrib(basering,uptodeg) holds
+
+In the procedures below, 'iv' stands for intvec representation
+and 'lp' for the letterplace representation of monomials
 
 PROCEDURES:
+
+lpMis2Dim(M);              computes the K-dimension of the monomial factor algebra
+lpKDim(G[,d,n]);           computes the K-dimension of A/<G>
+lpDimCheck(G);             checks if the K-dimension of A/<G> is infinite
+lpMis2Base(M);             computes a K-basis of the factor algebra
+lpHilbert(G[,d,n]);        computes the Hilbert series of A/<G> in lp format
+lpDHilbert(G[,d,n]);       computes the K-dimension and Hilbert series of A/<G>
+lpDHilbertSickle(G[,d,n]); computes mistletoes, K-dimension and Hilbert series
 
 ivDHilbert(L,n[,d]);       computes the K-dimension and the Hilbert series
@@ -73 +86 @@
 ivSickleHil(L,n[,d]);      computes the mistletoes and Hilbert series of A/<L>
 ivSickleDim(L,n[,d]);      computes the mistletoes and the K-dimension of A/<L>
-lpDHilbert(G[,d,n]);       computes the K-dimension and Hilbert series of A/<G>
-lpDHilbertSickle(G[,d,n]); computes mistletoes, K-dimension and Hilbert series
-lpHilbert(G[,d,n]);        computes the Hilbert series of A/<G> in lp format
-lpDimCheck(G);             checks if the K-dimension of A/<G> is infinite
-lpKDim(G[,d,n]);           computes the K-dimension of A/<G> in lp format
-lpMis2Base(M);             computes a K-basis of the factor algebra
-lpMis2Dim(M);              computes the K-dimension of the factor algebra
 lpOrdMisLex(M);            orders an ideal of lp-monomials lexicographically
 lpSickle(G[,d,n]);         computes the mistletoes of A/<G> in lp format
@@ -85 +91 @@
 lpSickleDim(G[,d,n]);      computes the mistletoes and the K-dimension of A/<G>
 sickle(G[,m,d,h]);         can be used to access all lp main procedures
-
 
 ivL2lpI(L);           transforms a list of intvecs into an ideal of lp monomials
@@ -145 +150 @@
     {for (i3 = 1; i3 <= n; i3++)
       {for (i4 = 1; i4 <= (n^(i1-1)); i4++)
-      {
-        M[i2,i1] = i3;
+        {M[i2,i1] = i3;
           i2 = i2 + 1;
-       }
+        }
       }
     }
@@ -170 +174 @@
 "PURPOSE:checks, if all entries in M are variable-related
 "
-{if ((nrows(M) == 1) && (ncols(M) == 1)) {if (M[1,1] == 0){return(0);}}
- int i,j;
+{int i,j;
   for (i = 1; i <= nrows(M); i++)
   {for (j = 1; j <= ncols(M); j++)
@@ -328 +331 @@
 }
 
+
+static proc findCycleDFS(int i, intmat T, intvec V)
+"
+PURPOSE:
+this is a classical deep-first search for cycles contained in a graph given by an intmat
+"
+{
+  intvec rV;
+  int k,k1,t;
+  int j = V[size(V)];
+  if (T[j,i] > 0) {return(V);}
+  else
+  {
+    for (k = 1; k <= ncols(T); k++)
+    {
+      t = 0;
+      if (T[j,k] > 0)
+      {
+        for (k1 = 1; k1 <= size(V); k1++) {if (V[k1] == k) {t = 1; break;}}
+        if (t == 0)
+        {
+          rV = V;
+          rV[size(rV)+1] = k;
+          rV = findCycleDFS(i,T,rV);
+          if (rV[1] > -1) {return(rV);}
+        }
+      }
+    }
+  }
+  return(intvec(-1));
+}
+
+
+
 static proc findHCoeff(intvec V,int n,list L,intvec P,intvec H,list #)
 "USAGE: findHCoeff(V,n,L,P,H,degbound); L a list of intmats, degbound an integer
@@ -565 +602 @@
       }
       return(R);
-
     }
   }
@@ -647 +683 @@
 }
 
+static proc growthAlg(intmat T, list #)
+"
+real algorithm for checking the growth of an algebra
+"
+{
+  int s = 1;
+  if (size(#) > 0) { s = #[1];}
+  int j;
+  int n = ncols(T);
+  intvec NV,C; NV[n] = 0; int m,i;
+  intmat T2[n][n] = T[1..n,1..n]; intmat N[n][n];
+  if (T2 == N)
+  {
+    for (i = 1; i <= n; i++)
+    {
+      if (m <  T[n+1,i]) { m = T[n+1,i];}
+    }
+    return(m);
+  }
+
+  //first part: the diagonals
+  for (i = s; i <= n; i++)
+  {
+    if (T[i,i] > 0)
+    {
+      if ((T[i,i] >= 1) && (T[n+1,i] > 0)) {return(-1);}
+      if ((T[i,i] == 1) && (T[n+1,i] == 0))
+      {
+        T[i,i] = 0;
+        T[n+1,i] = 1;
+        return(growthAlg(T));
+      }
+    }
+  }
+
+  //second part: searching for the last but one vertices
+  T2 = T2*T2;
+  for (i = s; i <= n; i++)
+  {
+    if ((intvec(T[i,1..n]) <> intvec(0)) && (intvec(T2[i,1..n]) == intvec(0)))
+    {
+      for (j = 1; j <= n; j++)
+      {
+        if ((T[i,j] > 0) && (m < T[n+1,j])) {m = T[n+1,j];}
+      }
+      T[n+1,i] = T[n+1,i] + m;
+      T[i,1..n] = NV;
+      return(growthAlg(T));
+    }
+  }
+  m = 0;
+
+  //third part: searching for circles
+  for (i = s; i <= n; i++)
+  {
+    T2 = T[1..n,1..n];
+    C = findCycleDFS(i,T2, intvec(i));
+    if (C[1] > 0)
+    {
+      for (j = 2; j <= size(C); j++)
+      {
+        T[i,1..n] = T[i,1..n] + T[C[j],1..n];
+        T[C[j],1..n] = NV;
+      }
+      for (j = 2; j <= size(C); j++)
+      {
+        T[1..n,i] = T[1..n,i] + T[1..n,C[j]];
+        T[1..n,C[j]] = NV;
+      }
+      T[i,i] = T[i,i] - size(C) + 1;
+      m = 0;
+      for (j = 1; j <= size(C); j++)
+      {
+        m = m + T[n+1,C[j]];
+      }
+      for (j = 1; j <= size(C); j++)
+      {
+        T[n+1,C[j]] = m;
+      }
+      return(growthAlg(T,i));
+    }
+    else {ERROR("No Cycle found, something seems wrong! Please contact the authors.");}
+  }
+
+  m = 0;
+  for (i = 1; i <= n; i++)
+  {
+    if (m < T[n+1,i])
+    {
+      m = T[n+1,i];
+    }
+  }
+  return(m);
+}
+
+static proc GlDimSuffix(intvec v, intvec g)
+{
+  //Computes the shortest r such that g is a suffix for vr
+  //only valid for lex orderings?
+  intvec r,gt,vt,lt,g2;
+  int lg,lv,l,i,c,f;
+  lg = size(g); lv = size(v);
+  if (lg <= lv)
+  {
+    l = lv-lg;
+  }
+  else
+  {
+    l = 0; g2 = g[(lv+1)..lg];
+    g = g[1..lv]; lg = size(g);
+    c = 1;
+  }
+  while (l < lv)
+  {
+    vt = v[(l+1)..lv];
+    gt = g[1..(lv-l)];
+    lt = size(gt);
+    for (i = 1; i <= lt; i++)
+    {
+      if (vt[i]<>gt[i]) {l++; break;}
+    }
+    if (lt <=i ) { f = 1; break;}
+  }
+  if (f == 0) {return(g);}
+  r = g[(lv-l+1)..lg];
+  if (c == 1) {r = r,g2;}
+  return(r);
+}
+
+static proc isNormal(intvec V, list G)
+{
+  int i,j,k,l;
+  k = 0;
+  for (i = 1; i <= size(G); i++)
+  {
+    if ( size(G[i]) <= size(V) )
+    {
+      while ( size(G[i])+k <= size(V) )
+      {
+        if ( G[i] == V[(1+k)..size(V)] ) {return(1);}
+      }
+    }
+  }
+  return(0);
+}
+
+static proc findDChain(list L)
+{
+  list Li; int i,j;
+  for (i = 1; i <= size(L); i++) {Li[i] = size(L[i]);}
+  Li = sort(Li); Li = Li[1];
+  return(Li[size(Li)]);
+}
+
 static proc isInList(intvec V, list L)
 "USAGE: isInList(V,L); V an intvec, L a list of intvecs
@@ -684 +874 @@
 }
 
+
+static proc isPF(intvec P, intvec I)
+"
+PURPOSE:
+checks, if a word P is a praefix of another word I
+"
+{
+  int n = size(P);
+  if (n <= 0 || P == 0) {return(1);}
+  if (size(I) < n) {return(0);}
+  intvec IP = I[1..n];
+  if (IP == P) {return(1);}
+  else {return(0);}
+}
+
 proc ivL2lpI(list L)
 "USAGE: ivL2lpI(L); L a list of intvecs
 RETURN: ideal
-PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials.
-@*      For the encoding of the variables see the overview.
+PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials
 ASSUME: - Intvec corresponds to a Letterplace monomial
 @*      - basering has to be a Letterplace ring
+NOTE:   - Assumptions will not be checked!
 EXAMPLE: example ivL2lpI; shows examples
 "
-{checkAssumptions(0,L);
+{
   int i; ideal G;
   poly p;
@@ -718 +923 @@
 RETURN: poly
 PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial
-@*      For the encoding of the variables see the overview.
 ASSUME: - Intvec corresponds to a Letterplace monomial
 @*      - basering has to be a Letterplace ring
@@ -748 +952 @@
 RETURN: ideal
 PURPOSE:Converting a list of intmats into an ideal of corresponding monomials
-@*      The rows of the intmat corresponds to an intvec, which stores the
-@*      monomial.
-@*      For the encoding of the variables see the overview.
 ASSUME: - The rows of each intmat in L must correspond to a Letterplace monomial
 @*      - basering has to be a Letterplace ring
@@ -779 +980 @@
 "USAGE: iv2lpMat(M); M an intmat
 RETURN: ideal
-PURPOSE:Converting an intmat into an ideal of the corresponding monomials.
-@*      The rows of the intmat corresponds to an intvec, which stores the
-@*      monomial.
-@*      For the encoding of the variables see the overview.
+PURPOSE:Converting an intmat into an ideal of the corresponding monomials
 ASSUME: - The rows of M must correspond to Letterplace monomials
 @*      - basering has to be a Letterplace ring
@@ -816 +1014 @@
 "USAGE: lpId2ivLi(G); G an ideal
 RETURN: list
-PURPOSE:Transforming an ideal into the corresponding list of intvecs.
-@*      For the encoding of the variables see the overview.
+PURPOSE:Transforming an ideal into the corresponding list of intvecs
 ASSUME: - basering has to be a Letterplace ring
 EXAMPLE: example lpId2ivLi; shows examples
 "
-{int i,j,k;
+{
+  int i,j,k;
   list M;
   checkAssumptions(0,M);
@@ -840 +1038 @@
 "USAGE: lp2iv(p); p a poly
 RETURN: intvec
-PURPOSE:Transforming a monomial into the corresponding intvec.
-@*      For the encoding of the variables see the overview.
+PURPOSE:Transforming a monomial into the corresponding intvec
 ASSUME: - basering has to be a Letterplace ring
 NOTE:   - Assumptions will not be checked!
@@ -883 +1080 @@
 RETURN: list
 PURPOSE:Converting an ideal into an list of intmats,
-@*      the corresponding intvecs forming the rows.
-@*      For the encoding of the variables see the overview.
+@*      the corresponding intvecs forming the rows
 ASSUME: - basering has to be a Letterplace ring
 EXAMPLE: example lp2ivId; shows examples
@@ -925 +1121 @@
 // -----------------main procedures----------------------
 
+static proc lpGraphOfNormalWords(ideal G)
+"USAGE: lpGraphOfNormalWords(G); G a set of monomials in a letterplace ring
+RETURN: intmat
+PURPOSE: Constructs the graph of normal words induced by G
+@*:      the adjacency matrix of the graph of normal words induced by G
+ASSUME: - basering is a Letterplace ring
+- G are the leading monomials of a Groebner basis
+"
+{
+  // construct the Graph of normal words [Studzinski page 78]
+  // construct set of vertices
+  int v = attrib(basering,"lV"); int d = attrib(basering,"uptodeg");
+  ideal V; poly p,q,w;
+  ideal LG = lead(G);
+  int i,j,k,b; intvec E,Et;
+  for (i = 1; i <= v; i++){V = V, var(i);}
+  for (i = 1; i <= size(LG); i++)
+  {
+    E = leadexp(LG[i]);
+    if (E == intvec(0)) {V = V,monomial(intvec(0));}
+    else
+    {
+      for (j = 1; j < d; j++)
+      {
+        Et = E[(j*v+1)..(d*v)];
+        if (Et == intvec(0)) {break;}
+        else {V = V, monomial(Et);}
+      }
+    }
+  }
+  V = simplify(V,2+4);
+  printf("V = %p", V);
+
+
+  // construct incidence matrix
+
+  list LV = lpId2ivLi(V);
+  intvec Ip,Iw;
+  int n = size(V);
+  intmat T[n+1][n];
+  for (i = 1; i <= n; i++)
+  {
+    // printf("for1 (i=%p, n=%p)", i, n);
+    p = V[i]; Ip = lp2iv(p);
+    for (j = 1; j <= n; j++)
+    {
+      // printf("for2 (j=%p, n=%p)", j, n);
+      k = 1; b = 1;
+      q = V[j];
+      w = lpNF(lpMult(p,q),LG);
+      if (w <> 0)
+      {
+        Iw = lp2iv(w);
+        while (k <= n)
+        {
+          // printf("while (k=%p, n=%p)", k, n);
+          if (isPF(LV[k],Iw) > 0)
+          {if (isPF(LV[k],Ip) == 0) {b = 0; k = n+1;} else {k++;}
+          }
+          else {k++;}
+        }
+        T[i,j] = b;
+        //  print("Incidence Matrix:");
+        // print(T);
+      }
+    }
+  }
+  return(T);
+}
+
+// This proc is deprecated, see lpGkDim() in fpaprops.lib
+/* proc lpGkDim(ideal G) */
+/* "USAGE: lpGkDim(G); G an ideal in a letterplace ring */
+/* RETURN: int */
+/* PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> */
+/* @*:     -1 means it is infinite */
+/* ASSUME: - basering is a Letterplace ring */
+/* - G is a Groebner basis */
+/* NOTE: see fpaprops.lib for a faster and more up to date version of this method */
+/* " */
+/* { */
+/*   return(growthAlg(lpGraphOfNormalWords(G))); */
+/* } */
+
 proc ivDHilbert(list L, int n, list #)
 "USAGE: ivDHilbert(L,n[,degbound]); L a list of intmats, n an integer,
@@ -932 +1212 @@
 ASSUME: - basering is a Letterplace ring
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        for the encoding of the variables see the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds
 NOTE: - If L is the list returned, then L[1] is an integer corresponding to the
 @*      dimension, L[2] is an intvec which contains the coefficients of the
@@ -984 +1263 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - All rows of each intmat correspond to a Letterplace monomial.
-@*        for the encoding of the variables see the overview
 @*      - If you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, L[2] is an intvec
 @*      which contains the coefficients of the Hilbert series and L[3]
@@ -1031 +1309 @@
 RETURN: int, 0 if the dimension is finite, or 1 otherwise
 PURPOSE:Decides, whether the K-dimension is finite or not
-ASSUME: - basering is a Letterplace ring
-@*      - All rows of each intmat correspond to a Letterplace monomial
-@*        For the encoding of the variables see the overview.
-NOTE:   - n is the number of variables
+ASSUME: - basering is a Letterplace ring.
+@*      - All rows of each intmat correspond to a Letterplace monomial.
+NOTE:   - n is the number of variables.
 EXAMPLE: example ivDimCheck; shows examples
 "
@@ -1090 +1367 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        for the encoding of the variables see the overview
 @*      - if you specify a different degree bound degbound,
-@*       degbound <= attrib(basering,uptodeg) should hold.
+@*       degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, a degree bound  will be added. By default there
 @*      is no degree bound.
@@ -1176 +1452 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        for the encoding of the variables see the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, a degree bound will be added. By default there
 @*      is no degree bound.
@@ -1263 +1538 @@
 "
 {
-//checkAssumptions(0,M);
+  //checkAssumptions(0,M);
   intvec L,A;
   if (size(M) == 0){ERROR("There are no mistletoes, so it appears your dimension is infinite!");}
@@ -1274 +1549 @@
   for (i = 2; i <= size(M); i++)
   {A = M[i]; L = M[i-1];
-   s = size(A);
-   if (s > size(L))
-   {d = size(L);
-    for (j = s; j > d; j--) {Rt = insert(Rt,intvec(A[1..j]));}
-    A = A[1..d];
-   }
-   if (size(L) > s){L = L[1..s];}
-   while (A <> L)
-   {Rt = insert(Rt, intvec(A));
-    if (size(A) > 1)
-    {A = A[1..(size(A)-1)];
-     L = L[1..(size(L)-1)];
-    }
-    else {break;}
-   }
+    s = size(A);
+    if (s > size(L))
+    {d = size(L);
+      for (j = s; j > d; j--) {Rt = insert(Rt,intvec(A[1..j]));}
+      A = A[1..d];
+    }
+    if (size(L) > s){L = L[1..s];}
+    while (A <> L)
+    {Rt = insert(Rt, intvec(A));
+      if (size(A) > 1)
+      {A = A[1..(size(A)-1)];
+        L = L[1..(size(L)-1)];
+      }
+      else {break;}
+    }
   }
   return(Rt);
@@ -1313 +1588 @@
 @*        Otherwise the returned value may differ from the K-dimension.
 @*      - basering is a Letterplace ring.
-@*      - mistletoes are stored as intvecs, as described in the overview
 EXAMPLE: example ivMis2Dim; shows examples
 "
@@ -1321 +1595 @@
   if (isInList(L,M) > 0) {print("1 is a mistletoe, therefore dim = 1"); return(1);}
   int i,j,d,s;
+  j = 1;
   d = 1 + size(M[1]);
   for (i = 1; i < size(M); i++)
-  {j = 1;
-   s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);}
-   while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;}
-   d = d + size(M[i+1])- j + 1;
+  {s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);}
+    while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;}
+    d = d + size(M[i+1])- j + 1;
   }
   return(d);
@@ -1348 +1622 @@
 PURPOSE:Orders a given set of mistletoes lexicographically
 ASSUME: - basering is a Letterplace ring.
-@*      - intvecs correspond to monomials, as explained in the overview
+- intvecs correspond to monomials
 NOTE:   - This is preprocessing, it's not needed if the mistletoes are returned
 @*        from the sickle algorithm.
@@ -1374 +1648 @@
 @*      optional integer
 RETURN: list, containing intvecs, the mistletoes of A/<L>
-PURPOSE:Computing the mistletoes for a given Groebner basis L, given by intmats
+PURPOSE:Computing the mistletoes for a given Groebner basis L
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        as explained in the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, a degree bound will be added. By default there
 @*      is no degree bound.
@@ -1457 +1730 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        as explained in the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, L[2] is a list,
 @*      containing the mistletoes as intvecs.
@@ -1545 +1817 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        as explained in the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an intvec, L[2] is a list,
 @*      containing the mistletoes as intvecs.
@@ -1630 +1901 @@
 RETURN: list
 PURPOSE:Computing K-dimension and Hilbert series, starting with a lp-ideal
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer corresponding to the
 @*      dimension, L[2] is an intvec which contains the coefficients of the
@@ -1672 +1943 @@
 RETURN: list
 PURPOSE:Computing K-dimension, Hilbert series and mistletoes at once
-ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension,
 @*      L[2] is an intvec, the Hilbert series and L[3] is an ideal,
@@ -1715 +1986 @@
 RETURN: intvec, containing the coefficients of the Hilbert series
 PURPOSE:Computing the Hilbert series
-ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, there will be a degree bound added. 0 means no
 @*      degree bound. Default: attrib(basering,uptodeg).
@@ -1753 +2024 @@
 RETURN: int, 1 if K-dimension of the factor algebra is infinite, 0 otherwise
 PURPOSE:Checking a factor algebra for finiteness of the K-dimension
-ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 EXAMPLE: example lpDimCheck; shows examples
 "
@@ -1781 +2052 @@
 RETURN: int, the K-dimension of the factor algebra
 PURPOSE:Computing the K-dimension of a factor algebra, given via an ideal
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, there will be a degree bound added. 0 means no
 @*      degree bound. Default: attrib(basering, uptodeg).
@@ -1840 +2111 @@
 RETURN: int, the K-dimension of the factor algebra
 PURPOSE:Computing the K-dimension out of given mistletoes
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - M contains only monomials
 NOTE:   - The mistletoes have to be ordered lexicographically -> OrdMisLex.
@@ -1864 +2135 @@
 RETURN: ideal, containing the mistletoes, ordered lexicographically
 PURPOSE:A given set of mistletoes is ordered lexicographically
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 NOTE:   This is preprocessing, it is not needed if the mistletoes are returned
 @*      from the sickle algorithm.
@@ -1885 +2156 @@
 RETURN: ideal
 PURPOSE:Computing the mistletoes of K[X]/<G>
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, there will be a degree bound added. 0 means no
 @*      degree bound. Default: attrib(basering,uptodeg).
@@ -1923 +2194 @@
 RETURN: list
 PURPOSE:Computing the K-dimension and the mistletoes
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension,
 @*      L[2] is an ideal, the mistletoes.
@@ -1962 +2233 @@
 RETURN: list
 PURPOSE:Computing the Hilbert series and the mistletoes
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an intvec, corresponding to the
 @*      Hilbert series, L[2] is an ideal, the mistletoes.
@@ -2004 +2275 @@
 RETURN: list
 PURPOSE:Allowing the user to access all procs with one command
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE:   The returned object will always be a list, but the entries of the
 @*      returned list may be very different
@@ -2062 +2333 @@
   sickle(G,0,0,1); // computes Hilbert series only
 }
+
+proc ivMaxIdeal(int l, int lonly)
+  "USAGE: lpMaxIdeal(l, lonly); l an integer, lonly an integer
+  RETURN: list
+  PURPOSE: computes a list of free monomials in intvec presentation
+  @*       with length <= l
+  @*       if donly <> 0, only monomials of degree d are returned
+  ASSUME: - basering is a Letterplace ring.
+  NOTE: see also lpMaxIdeal()
+  "
+{
+  if (l < 0) {
+    ERROR("l must not be negative")
+  }
+  list words;
+  if (l == 0) {
+     words = 0;
+     return (words);
+  }
+  int lV = attrib(basering, "lV"); // variable count
+  list prevWords;
+  if (l > 1) {
+    prevWords = ivMaxIdeal(l - 1, lonly);
+  } else {
+    prevWords = 0;
+  }
+  for (int i = 1; i <= size(prevWords); i++) {
+    if (size(prevWords[i]) >= l - 1) {
+      for (int j = 1; j <= lV; j++) {
+        intvec word = prevWords[i];
+        word[l] = j;
+        words = insert(words, word);
+        kill word;
+      } kill j;
+    }
+  } kill i;
+  if (!lonly && l > 1) {
+    words = prevWords + words;
+  }
+  return (words);
+}
+example {
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(a,b,c),dp;
+  def R = makeLetterplaceRing(7); setring R;
+  ivMaxIdeal(1,0);
+  ivMaxIdeal(2,0);
+  ivMaxIdeal(2,1);
+  ivMaxIdeal(4,0);
+  ivMaxIdeal(4,1);
+}
+
+proc lpMaxIdeal(int d, int donly)
+  "USAGE: lpMaxIdeal(d, donly); d an integer, donly an integer
+  RETURN: ideal
+  PURPOSE: computes a list of free monomials of degree at most d
+  @*       if donly <> 0, only monomials of degree d are returned
+  ASSUME: - basering is a Letterplace ring.
+  @*      - d <= attrib(basering,uptodeg) holds.
+  NOTE: analogous to maxideal(d) in the commutative case
+  "
+{
+  ivL2lpI(ivMaxIdeal(d, donly));
+}
+example {
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(a,b,c),dp;
+  def R = makeLetterplaceRing(7); setring R;
+  lpMaxIdeal(1,0);
+  lpMaxIdeal(2,0);
+  lpMaxIdeal(2,1);
+  lpMaxIdeal(4,0);
+  lpMaxIdeal(4,1);
+}
+
+proc monomialBasis(int d, int donly, ideal J)
+  "USAGE: monomialBasis(d, donly, J); d, donly integers, J an ideal
+  RETURN: ideal
+  PURPOSE: computes a list of free monomials in a Letterplace
+  @*       basering R of degree at most d and not contained in <LM(J)>
+  @*       if donly <> 0, only monomials of degree d are returned
+  ASSUME: - basering is a Letterplace ring.
+  @*      - d <= attrib(basering,uptodeg) holds.
+  @*      - J is a Groebner basis
+  "
+{
+  int nv = attrib(basering,"uptodeg");
+  if ((d>nv) || (d<0) )
+  {
+    ERROR("incorrect degree");
+  }
+  nv = attrib(basering,"lV"); // nvars
+  if (d==0)
+  {
+    return(ideal(1));
+  }
+  /* from now on d>=1 */
+  ideal I;
+  if (size(J)==0)
+  {
+    I = lpMaxIdeal(d,donly);
+    if (!donly)
+    {
+      // append 1 as the first element; d>=1
+      I = 1, I;
+    }
+    return( I );
+  }
+  // ok, Sickle misbehaves: have to remove all
+  // elts from J of degree >d
+  ideal JJ;
+  int j; int sj = ncols(J);
+  int cnt=0;
+  for(j=1;j<=sj;j++)
+  {
+    if (deg(J[j]) <= d)
+    {
+      cnt++;
+      JJ[cnt]=lead(J[j]); // only LMs are needed
+    }
+  }
+  if (cnt==0)
+  {
+    // there are no elements in J of degree <= d
+    // return free stuff and the 1
+    I = monomialBasis(d, donly, std(0));
+    if (!donly)
+    {
+      I = 1, I;
+    }
+    return(I);
+  }
+  // from here on, Ibase is not zero
+  ideal Ibase = lpMis2Base(lpSickle(JJ,d)); // the complete K-basis modulo J up to d
+  if (!donly)
+  {
+    // for not donly, give everything back
+    // sort by DP starting with smaller terms
+    Ibase = sort(Ibase,"Dp")[1];
+    return(Ibase);
+  }
+  /* !donly: pick out only monomials of degree d */
+  int i; int si = ncols(Ibase);
+  cnt=0;
+  I=0;
+  for(i=1;i<=si;i++)
+  {
+    if (deg(Ibase[i]) == d)
+    {
+      cnt++;
+      I[cnt]=Ibase[i];
+    }
+  }
+  kill Ibase;
+  return(I);
+}
+example {
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y),dp;
+  def R = makeLetterplaceRing(7); setring R;
+  ideal J = x(1)*y(2)*x(3) - y(1)*x(2)*y(3);
+  option(redSB); option(redTail);
+  J = letplaceGBasis(J);
+  J;
+  monomialBasis(2,1,std(0));
+  monomialBasis(2,0,std(0));
+  monomialBasis(3,1,J);
+  monomialBasis(3,0,J);
+}
+
+
+///////////////////////////////////////////////////////////////////////////////
+/* vl: stuff for conversion to Magma and to SD
+todo: doc, example
+ */
+static proc extractVars(r)
+{
+  int i = 1;
+  int j = 1;
+  string candidate;
+  list result = list();
+  for (i = 1; i<=nvars(r);i++)
+  {
+    candidate = string(var(i))[1,find(string(var(i)),"(")-1];
+    if (!inList(result, candidate))
+    {
+      result = insert(result,candidate,size(result));
+    }
+  }
+  return(result);
+}
+
+static proc letterPlacePoly2MagmaString(poly h)
+{
+  int pos;
+  string s = string(h);
+  while(find(s,"("))
+  {
+    pos = find(s,"(");
+    while(s[pos]!=")")
+    {
+      s = s[1,pos-1]+s[pos+1,size(s)-pos];
+    }
+    if (size(s)!=pos)
+    {
+      s = s[1,pos-1]+s[pos+1,size(s)-pos]; // The last (")")
+    }
+    else
+    {
+      s = s[1,pos-1];
+    }
+  }
+  return(s);
+}
+
+static proc letterPlaceIdeal2SD(ideal I, int upToDeg)
+{
+  int i;
+  print("Don't forget to fill in the formal Data in the file");
+  string result = "<?xml version=\"1.0\"?>"+newline+"<FREEALGEBRA createdAt=\"\" createdBy=\"Singular\" id=\"FREEALGEBRA/\">"+newline;
+  result = result + "<vars>"+string(extractVars(basering))+"</vars>"+newline;
+  result = result + "<basis>"+newline;
+  for (i = 1;i<=size(I);i++)
+  {
+    result = result + "<poly>"+letterPlacePoly2MagmaString(I[i])+"</poly>"+newline;
+  }
+  result = result + "</basis>"+newline;
+  result = result + "<uptoDeg>"+ string(upToDeg)+"</uptoDeg>"+newline;
+  result = result + "<Comment></Comment>"+newline;
+  result = result + "<Version></Version>"+newline;
+  result = result + "</FREEALGEBRA>";
+  return(result);
+}
+
 
 ///////////////////////////////////////////////////////////////////////////////
@@ -2098 +2603 @@
   example lp2ivId;
   example lpId2ivLi;
-}
-
-
-
-
+  example lpSubstitute;
+}
 
 /*
-  Here are some examples one may try. Just copy them into your console.
-  These are relations for braid groups, up to degree d:
-
-
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d =10; // degree
-  def R = makeLetterplaceRing(d);
-  setring R;
-  ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
-  z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
-  z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,3);
-  lpDimCheck(J);
-  sickle(J,1,1,1,d);//Computes mistletoes, K-dimension and the Hilbert series
-
-
-
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d =11; // degree
-  def R = makeLetterplaceRing(d);
-  setring R;
-  ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*z(3) - z(1)*x(2)*y(3),
-  z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
-  z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,3);
-  lpDimCheck(J);
-  sickle(J,1,1,1,d);
-
-
-
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d  = 6; // degree
-  def R  = makeLetterplaceRing(d);
-  setring R;
-  ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
-  z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) -2*y(1)*y(2)*y(3) + 3*z(1)*z(2)*z(3) -4*x(1)*y(2)*z(3) + 5*x(1)*z(2)*z(3)- 6*x(1)*y(2)*y(3) +7*x(1)*x(2)*z(3) - 8*x(1)*x(2)*y(3);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,3);
-  lpDimCheck(J);
-  sickle(J,1,1,1,d);
+   Here are some examples one may try. Just copy them into your console.
+   These are relations for braid groups, up to degree d:
+
+   LIB "fpadim.lib";
+   ring r = 0,(x,y,z),dp;
+   int d =10; // degree
+   def R = makeLetterplaceRing(d);
+   setring R;
+   ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
+   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
+   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
+   option(prot);
+   option(redSB);option(redTail);option(mem);
+   ideal J = system("freegb",I,d,3);
+   lpDimCheck(J);
+   sickle(J,1,1,1,d);//Computes mistletoes, K-dimension and the Hilbert series
+
+
+
+   LIB "fpadim.lib";
+   ring r = 0,(x,y,z),dp;
+   int d =11; // degree
+   def R = makeLetterplaceRing(d);
+   setring R;
+   ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*z(3) - z(1)*x(2)*y(3),
+   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
+   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
+   option(prot);
+   option(redSB);option(redTail);option(mem);
+   ideal J = system("freegb",I,d,3);
+   lpDimCheck(J);
+   sickle(J,1,1,1,d);
+
+
+
+   LIB "fpadim.lib";
+   ring r = 0,(x,y,z),dp;
+   int d  = 6; // degree
+   def R  = makeLetterplaceRing(d);
+   setring R;
+   ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
+   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) -2*y(1)*y(2)*y(3) + 3*z(1)*z(2)*z(3) -4*x(1)*y(2)*z(3) + 5*x(1)*z(2)*z(3)- 6*x(1)*y(2)*y(3) +7*x(1)*x(2)*z(3) - 8*x(1)*x(2)*y(3);
+   option(prot);
+   option(redSB);option(redTail);option(mem);
+   ideal J = system("freegb",I,d,3);
+   lpDimCheck(J);
+   sickle(J,1,1,1,d);
+ */
+
+/*
+   Here are some examples, which can also be found in [studzins]:
+
+// takes up to 880Mb of memory
+LIB "fpadim.lib";
+ring r = 0,(x,y,z),dp;
+int d =10; // degree
+def R = makeLetterplaceRing(d);
+setring R;
+ideal I =
+z(1)*z(2)*z(3)*z(4) + y(1)*x(2)*y(3)*x(4) - x(1)*y(2)*y(3)*x(4) - 3*z(1)*y(2)*x(3)*z(4), x(1)*x(2)*x(3) + y(1)*x(2)*y(3) - x(1)*y(2)*x(3), z(1)*y(2)*x(3)-x(1)*y(2)*z(3) + z(1)*x(2)*z(3);
+option(prot);
+option(redSB);option(redTail);option(mem);
+ideal J = system("freegb",I,d,nvars(r));
+lpDimCheck(J);
+sickle(J,1,1,1,d); // dimension is 24872
+
+
+LIB "fpadim.lib";
+ring r = 0,(x,y,z),dp;
+int d =10; // degree
+def R = makeLetterplaceRing(d);
+setring R;
+ideal I = x(1)*y(2) + y(1)*z(2), x(1)*x(2) + x(1)*y(2) - y(1)*x(2) - y(1)*y(2);
+option(prot);
+option(redSB);option(redTail);option(mem);
+ideal J = system("freegb",I,d,3);
+lpDimCheck(J);
+sickle(J,1,1,1,d);
+ */
+
+
+/*
+   Example for computing GK dimension:
+   returns a ring which contains an ideal I
+   run gkDim(I) inside this ring and it should return 2n (the GK dimension
+   of n-th Weyl algebra including evaluation operators).
+
+   static proc createWeylEx(int n, int d)
+   "
+   "
+   {
+   int baseringdef;
+   if (defined(basering)) // if a basering is defined, it should be saved for later use
+   {
+   def save = basering;
+   baseringdef = 1;
+   }
+   ring r = 0,(d(1..n),x(1..n),e(1..n)),dp;
+   def R = makeLetterplaceRing(d);
+   setring R;
+   ideal I; int i,j;
+
+   for (i = 1; i <= n; i++)
+   {
+   for (j = i+1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(i),var(j));
+   }
+   }
+
+   for (i = 1; i <= n; i++)
+   {
+   for (j = i+1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(n+i),var(n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(i),var(n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(i),var(2*n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(2*n+i),var(n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(2*n+i),var(2*n+j));
+   }
+   }
+   I = simplify(I,2+4);
+   I = letplaceGBasis(I);
+   export(I);
+   if (baseringdef == 1) {setring save;}
+   return(R);
+   }
+
+proc TestGKAuslander3()
+{
+  ring r = (0,q),(z,x,y),(dp(1),dp(2));
+  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = q*x(1)*y(2) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2);
+  I = letplaceGBasis(I);
+  lpGkDim(I); // must be 3
+  I = x(1)*y(2)*z(3) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2);//gkDim = 2
+  I = letplaceGBasis(I); // not finite BUT contains a poly in x,y only
+  lpGkDim(I); // must be 4
+
+  ring r = 0,(y,x,z),dp;
+  def R = makeLetterplaceRing(10); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = x(1)*y(2)*z(3) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2);//gkDim = 2
+  I = letplaceGBasis(I); // computed as it would be homogenized; infinite
+  poly p = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  lpNF(p, I); // 0 as expected
+
+  // with inverse of z
+  ring r = 0,(iz,z,x,y),dp;
+  def R = makeLetterplaceRing(11); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = x(1)*y(2)*z(3) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2),
+    iz(1)*y(2) - y(1)*iz(2), iz(1)*x(2) - x(1)*iz(2), iz(1)*z(2)-1, z(1)*iz(2) -1;
+  I = letplaceGBasis(I); //
+  setring r;
+  def R2 = makeLetterplaceRing(23); // constructs a Letterplace ring
+  setring R2; // sets basering to Letterplace ring
+  ideal I = imap(R,I);
+  lpGkDim(I);
+
+
+  ring r = 0,(t,z,x,y),(dp(2),dp(2));
+  def R = makeLetterplaceRing(20); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = x(1)*y(2)*z(3) - y(1)*x(2)*t(3), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2),
+    t(1)*y(2) - y(1)*t(2), t(1)*x(2) - x(1)*t(2), t(1)*z(2) - z(1)*t(2);//gkDim = 2
+  I = letplaceGBasis(I); // computed as it would be homogenized; infinite
+  LIB "elim.lib";
+  ideal Inoz = nselect(I,intvec(2,6,10,14,18,22,26,30));
+  for(int i=1; i<=20; i++)
+  {
+    Inoz=subst(Inoz,t(i),1);
+  }
+  ideal J = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  J = letplaceGBasis(J);
+
+  poly p = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  lpNF(p, I); // 0 as expected
+
+  ring r2 = 0,(x,y),dp;
+  def R2 = makeLetterplaceRing(50); // constructs a Letterplace ring
+  setring R2;
+  ideal J = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  J = letplaceGBasis(J);
+}
+
 */
 
-/*
-  Here are some examples, which can also be found in [studzins]:
-
-  // takes up to 880Mb of memory
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d =10; // degree
-  def R = makeLetterplaceRing(d);
-  setring R;
-  ideal I =
-  z(1)*z(2)*z(3)*z(4) + y(1)*x(2)*y(3)*x(4) - x(1)*y(2)*y(3)*x(4) - 3*z(1)*y(2)*x(3)*z(4), x(1)*x(2)*x(3) + y(1)*x(2)*y(3) - x(1)*y(2)*x(3), z(1)*y(2)*x(3)-x(1)*y(2)*z(3) + z(1)*x(2)*z(3);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,nvars(r));
-  lpDimCheck(J);
-  sickle(J,1,1,1,d); // dimension is 24872
-
-
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d =10; // degree
-  def R = makeLetterplaceRing(d);
-  setring R;
-  ideal I = x(1)*y(2) + y(1)*z(2), x(1)*x(2) + x(1)*y(2) - y(1)*x(2) - y(1)*y(2);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,3);
-  lpDimCheck(J);
-  sickle(J,1,1,1,d);
-*/
+
+/*   more tests : downup algebra A
+LIB "fpadim.lib";
+ring r = (0,a,b,g),(x,y),Dp;
+def R = makeLetterplaceRing(6); // constructs a Letterplace ring
+setring R;
+poly F1 = g*x(1);
+poly F2 = g*y(1);
+ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1,
+x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2;
+J = letplaceGBasis(J);
+lpGkDim(J); // 3 == correct
+
+// downup algebra B
+LIB "fpadim.lib";
+ring r = (0,a,b,g, p(1..7),q(1..7)),(x,y),Dp;
+def R = makeLetterplaceRing(6); // constructs a Letterplace ring
+setring R;
+ideal imn = 1, y(1)*y(2)*y(3), x(1)*y(2), y(1)*x(2), x(1)*x(2), y(1)*y(2), x(1), y(1);
+int i;
+poly F1, F2;
+for(i=1;i<=7;i++)
+{
+F1 = F1 + p(i)*imn[i];
+F2 = F2 + q(i)*imn[i];
+}
+ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1,
+x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2;
+J = letplaceGBasis(J);
+lpGkDim(J); // 3 == correct
+
+ */

Singular/LIB/freegb.lib

@@ -3 +3 @@
 category="Noncommutative";
 info="
-LIBRARY: freegb.lib   Compute two-sided Groebner bases in free algebras via
-@*                    letterplace
+LIBRARY: freegb.lib   Compute two-sided Groebner bases in free algebras via letterplace approach
 AUTHORS: Viktor Levandovskyy,     viktor.levandovskyy@math.rwth-aachen.de
-@*       Grischa Studzinski,      grischa.studzinski@math.rwth-aachen.de
-
-OVERVIEW: For the theory, see chapter 'Letterplace' in the Singular Manual
+       Grischa Studzinski,      grischa.studzinski@math.rwth-aachen.de
+
+OVERVIEW: For the theory, see chapter 'Letterplace' in the @sc{Singular} Manual
+
+Support: Joint projects LE 2697/2-1 and KR 1907/3-1 of the Priority Programme SPP 1489:
+'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
+of the German DFG
+and Project II.6 of the transregional collaborative research centre
+SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG
 
 PROCEDURES:
-makeLetterplaceRing(d);    creates a ring with d blocks of shifted original
-@*                         variables
-letplaceGBasis(I); computes two-sided Groebner basis of a letterplace ideal I
-@*                 up to a degree bound
-lpNF(f,I);      normal form of f with respect to ideal I
-freeGBasis(L, n);  computes two-sided Groebner basis of an ideal, encoded via
-@*                 list L, up to degree n
+makeLetterplaceRing(d); creates a ring with d blocks of shifted original variables
+letplaceGBasis(I); computes two-sided Groebner basis of a letterplace ideal I up to a degree bound
+lpNF(f,I); two-sided normal form of f with respect to ideal I
 setLetterplaceAttributes(R,d,b); supplies ring R with the letterplace structure
-
+freeGBasis(L, n);  computes two-sided Groebner basis of an ideal, encoded via list L, up to degree n
 
 lpMult(f,g);    letterplace multiplication of letterplace polynomials
 shiftPoly(p,i); compute the i-th shift of letterplace polynomial p
 lpPower(f,n);   natural power of a letterplace polynomial
-lp2lstr(K, s);      convert letter-place ideal to a list of modules
-lst2str(L[, n]);   convert a list (of modules) into polynomials in free algebra
-mod2str(M[, n]); convert a module into a polynomial in free algebra
+lieBracket(a,b[, N]);  compute Lie bracket ab-ba of two letterplace polynomials
+
+lp2lstr(K, s);  convert a letterplace ideal into a list of modules
+lst2str(L[, n]); convert a list (of modules) into polynomials in free algebra via strings
+mod2str(M[, n]); convert a module into a polynomial in free algebra via strings
 vct2str(M[, n]);   convert a vector into a word in free algebra
-lieBracket(a,b[, N]);  compute Lie bracket ab-ba of two letterplace polynomials
-serreRelations(A,z);   compute the homogeneous part of Serre's relations
-@*                     associated to a generalized Cartan matrix A
-fullSerreRelations(A,N,C,P,d); compute the ideal of all Serre's relations
-@*                             associated to a generalized Cartan matrix A
-isVar(p);                   check whether p is a power of a single variable
+
+serreRelations(A,z); compute the homogeneous part of Serre's relations associated to a generalized Cartan matrix A
+fullSerreRelations(A,N,C,P,d); compute the ideal of all Serre's relations associated to a generalized Cartan matrix A
+isVar(p);              check whether p is a power of a single variable
 ademRelations(i,j);    compute the ideal of Adem relations for i<2j in char 0
 
@@ -968 +969 @@
 RETURN:  ring
 PURPOSE: creates a ring with the ordering, used in letterplace computations
-NOTE: if h is given and nonzero, the pure homogeneous letterplace block
-@*    ordering will be used.
+NOTE: h = 0 (default) : Dp ordering will be used
+h = 2 : weights 1 used for all the variables, a tie breaker is a list of block of original ring
+h = 1 : the pure homogeneous letterplace block ordering (applicable in the situation of homogeneous input ideals) will be used.
 EXAMPLE: example makeLetterplaceRing; shows examples
 "
 {
-  int use_old_mlr = 0;
+  int alternativeVersion = 0;
   if ( size(#)>0 )
   {
-    if (( typeof(#[1]) == "int" ) || ( typeof(#[1]) == "poly" ) )
-    {
-      poly x = poly(#[1]);
-      if (x!=0)
-      {
-        use_old_mlr = 1;
-      }
-    }
-  }
-  if (use_old_mlr)
+    if (typeof(#[1]) == "int")
+    {
+      alternativeVersion = #[1];
+    }
+  }
+  if (alternativeVersion == 1)
   {
     def @A = makeLetterplaceRing1(d);
   }
-  else
-  {
-    def @A = makeLetterplaceRing2(d);
+  else { 
+    if (alternativeVersion == 2)
+    {
+      def @A = makeLetterplaceRing2(d);
+    }
+    else {
+      def @A = makeLetterplaceRing4(d);
+    }
   }
   return(@A);
@@ -1205 +1208 @@
 }
 
+static proc makeLetterplaceRing4(int d)
+"USAGE:  makeLetterplaceRing2(d); d an integer
+RETURN:  ring
+PURPOSE: creates a Letterplace ring with a Dp ordering, suitable for
+@* the use of non-homogeneous letterplace
+NOTE: the matrix for the ordering looks as follows: first row is 1,1,...,1
+EXAMPLE: example makeLetterplaceRing2; shows examples
+"
+{
+
+  // ToDo future: inherit positive weights in the orig ring
+  // complain on nonpositive ones
+
+  // d = up to degree, will be shifted to d+1
+  if (d<1) {"bad d"; return(0);}
+
+  int uptodeg = d; int lV = nvars(basering);
+
+  int ppl = printlevel-voice+2;
+  string err = "";
+
+  int i,j,s;
+  def save = basering;
+  int D = d-1;
+  list LR  = ringlist(save);
+  list L, tmp, tmp2, tmp3;
+  L[1] = LR[1]; // ground field
+  L[4] = LR[4]; // quotient ideal
+  tmp  = LR[2]; // varnames
+  s = size(LR[2]);
+  for (i=1; i<=D; i++)
+  {
+    for (j=1; j<=s; j++)
+    {
+      tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")";
+    }
+  }
+  for (i=1; i<=s; i++)
+  {
+    tmp[i] = string(tmp[i])+"("+string(1)+")";
+  }
+  L[2] = tmp;
+  list OrigNames = LR[2];
+
+  s = size(LR[3]);
+  list ordering;
+  ordering[1] = list("Dp",intvec(1: int(d*lV)));
+  ordering[2] = LR[3][s]; // module ord to place at the very end
+  LR[3] = ordering;
+
+  L[3] = LR[3];
+  attrib(L,"maxExp",1);
+  def @R = ring(L);
+  def @@R = setLetterplaceAttributes(@R,uptodeg,lV);
+  return (@@R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y,z),(dp(1),dp(2));
+  def A = makeLetterplaceRing2(2);
+  setring A;
+  A;
+  attrib(A,"isLetterplaceRing");
+  attrib(A,"uptodeg");  // degree bound
+  attrib(A,"lV"); // number of variables in the main block
+}
+
 // P[s;sigma] approach
 static proc makeLetterplaceRing3(int d)
@@ -1314 +1385 @@
   attrib(A,"lV"); // number of variables in the main block
 }
-
-
 
 /* EXAMPLES:
@@ -2600 +2669 @@
   if (i>N)
   {
-    ERROR("The total number of elements in input ideals must not exceed the dimension of the ground ring");
+    string s1="The total number of elements in input ideals";
+    string s2="must not exceed the dimension of the ground ring";
+    ERROR(s1+s2);
   }
   if (i < N)
@@ -3029 +3100 @@
 */
 
-//static
-proc lpMultX(poly f, poly g)
+static proc lpMultX(poly f, poly g)
 {
   /* multiplies two polys in a very general setting correctly */
@@ -3083 +3153 @@
 }
 
-// TODO:
 // multiply two letterplace polynomials, lpMult: done
 // reduction/ Normalform? needs kernel stuff
@@ -3172 +3241 @@
 //@* else there wouldn't be an dvec representation
 
-//Mainprocedure for the user
+//Main procedure for the user
 
 proc lpNF(poly p, ideal G)
 "USAGE: lpNF(p,G); f letterplace polynomial, ideal I
 RETURN: poly
-PURPOSE: computation of the normalform of p with respect to G
+PURPOSE: computation of the normal form of p with respect to G
 ASSUME: p is a Letterplace polynomial, G is a set Letterplace polynomials,
 being a Letterplace Groebner basis (no check for this will be done)
 NOTE: Strategy: take the smallest monomial wrt ordering for reduction
-@*     For homogenous ideals the shift does not matter
-@*     For non-homogenous ideals the first shift will be the smallest monomial
+-     For homogenous ideals the shift does not matter
+-     For non-homogenous ideals the first shift will be the smallest monomial
 EXAMPLE: example lpNF; shows examples
 "
@@ -3189 +3258 @@
  G = sort(G)[1];
  list L = makeDVecI(G);
- return(normalize(lpNormalForm1(p,G,L)));
+ return(normalize(lpNormalForm2(p,G,L)));
 }
 example
@@ -3214 +3283 @@
 RETURN: list of intvecs
 PURPOSE: convert G into a list of intvecs, corresponding to the exponent vector
-@* of the leading monomials of G
+ of the leading monomials of G
 "
 {int i; list L;
@@ -3220 +3289 @@
  return(L);
 }
-
 
 static proc delSupZero(intvec I)
@@ -3247 +3315 @@
 }
 
-
 static proc delSupZeroList(list L)
 "USUAGE:delSupZeroList(L); L a list, containing intvecs
@@ -3326 +3393 @@
 }
 
-
-
-//the actual normalform procedure, if a user want not to presort the ideal, just make it not static
-
+//the first normal form procedure, if a user want not to presort the ideal, just make it not static
 
 static proc lpNormalForm1(poly p, ideal G, list L)
@@ -3358 +3422 @@
 
 
+// new VL; called from lpNF
+static proc lpNormalForm2(poly pp, ideal G, list L)
+"USUAGE:lpNormalForm2(p,G);
+RETURN:poly
+PURPOSE:computation of the normal form of p w.r.t. G
+ASSUME: p is a Letterplace polynomial, G is a set of Letterplace polynomials
+NOTE: Taking the first possible reduction
+"
+{
+ poly one = 1;
+ if ( (pp == 0) || (leadmonom(pp) == one) ) { return(pp); }
+ poly p = pp; poly q;
+ int i; int s; intvec V;
+ while ( (p != 0) && (leadmonom(p) != one) )
+ {
+   //"entered while with p="; p;
+   V = makeDVec(delSupZero(leadexp(p)));
+   i = 0;
+   s = -1;
+   //"look for divisor";
+   while ( (s == -1) && (i<size(L)) )
+   {
+     i = i+1;
+     s = dShiftDiv(V, L[i])[1];
+   }
+ // now, out of here: either i=size(L) and s==-1 => no reduction
+ // otherwise: i<=size(L) and s!= -1 => reduction
+    //"out of divisor search: s="; s; "i="; i;
+    if (s != -1)
+    {
+    //"start reducing with G[i]:";
+      p = lpReduce(p,G[i],s); // lm-reduction
+      //"reduced to p="; p;
+    }
+    else
+    {
+      // ie no lm-reduction possible; proceed with the tail reduction
+      q = p-lead(p);
+      p = lead(p);
+      if (q!=0)
+      {
+        p = p + lpNormalForm2(q,G,L);
+      }
+      return(p);
+    }
+ }
+ // out of while when p==0 or p == const
+ return(p);
+}
+
+
 
 
@@ -3521 +3636 @@
 // // interface
 
-// proc whichshift(poly p, int numvars)
+// static proc whichshift(poly p, int numvars)
 // {
 // // numvars = number of vars of the orig free algebra
@@ -3538 +3653 @@
 
 // LIB "qhmoduli.lib";
-// proc polyshift(poly p,  int numvars)
+// static proc polyshift(poly p,  int numvars)
 // {
 //   poly q = p; int i = 0;
@@ -3615 +3730 @@
   lpMultX(a,b); // seems to work properly
 }
+
+/* THE FOLLOWING ARE UNDER DEVELOPMENT
+// copied following from freegb_wrkcp.lib by Karim Abou Zeid on 07.04.2017:
+// makeLetterplaceRingElim(int d)
+// makeLetterplaceRingNDO(int d)
+// setLetterplaceAttributesElim(def R, int uptodeg, int lV)
+// lpElimIdeal(ideal I)
+// makeLetterplaceRingWt(int d, intvec W)
+
+static proc makeLetterplaceRingElim(int d)
+"USAGE:  makeLetterplaceRingElim(d); d integers
+RETURN:  ring
+PURPOSE: creates a ring with an elimination ordering
+NOTE: the matrix for the ordering looks as follows: first row is 1,..,0,1,0,..
+@* then 0,1,0,...,0,0,1,0... and so on, lastly its lp
+@* this ordering is only correct if only polys with same shift are compared
+EXAMPLE: example makeLetterplaceRingElim; shows examples
+"
+{
+
+  // ToDo future: inherit positive weights in the orig ring
+  // complain on nonpositive ones
+
+  // d = up to degree, will be shifted to d+1
+  if (d<1) {"bad d"; return(0);}
+
+  int uptodeg = d; int lV = nvars(basering);
+
+  int ppl = printlevel-voice+2;
+  string err = "";
+
+  int i,j,s; intvec iV,iVl;
+  def save = basering;
+  int D = d-1;
+  list LR  = ringlist(save);
+  list L, tmp, tmp2, tmp3;
+  L[1] = LR[1]; // ground field
+  L[4] = LR[4]; // quotient ideal
+  tmp  = LR[2]; // varnames
+  s = size(LR[2]);
+  for (i=1; i<=D; i++)
+  {
+    for (j=1; j<=s; j++)
+    {
+      tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")";
+    }
+  }
+  for (i=1; i<=s; i++)
+  {
+    tmp[i] = string(tmp[i])+"("+string(1)+")";
+  }
+  L[2] = tmp;
+  L[3] = list();
+  list OrigNames = LR[2];
+  s = size(LR[3]);
+  //creation of first block
+
+  if (s==2)
+  {
+    // not a blockord, 1 block + module ord
+    tmp = LR[3][s]; // module ord
+    for (i = 1; i <= lV;  i++)
+    {
+      iV = (0: lV);
+      iV[i] = 1;
+      iVl = iV;
+      for (j = 1; j <= D; j++)
+       { iVl = iVl,iV; }
+      L[3][i] = list("a",iVl);
+    }
+//    for (i=1; i<=d; i++)
+//    {
+//      LR[3][s-1+i] = LR[3][1];
+//    }
+    //    LR[3][s+D] = tmp;
+    //iV = (1:(d*lV));
+    L[3][lV+1] = list("lp",(1:(d*lV)));
+    L[3][lV+2] = tmp;
+  }
+  else {ERROR("Please set the ordering of basering to dp");}
+//  if (s>2)
+//  {
+//    // there are s-1 blocks
+//    int nb = s-1;
+//    tmp = LR[3][s]; // module ord to place at the very end
+//   tmp2 = LR[3]; tmp2 = tmp2[1..nb];
+//    LR[3][1] = list("a",LTO);
+//    //tmp3[1] = list("a",intvec(1: int(d*lV))); // deg-ord, insert as the 1st
+//    for (i=1; i<=d; i++)
+//    {
+//      tmp3 = tmp3 + tmp2;
+//    }
+//    tmp3 = tmp3 + list(tmp);
+//    LR[3] = tmp3;
+//     for (i=1; i<=d; i++)
+//     {
+//       for (j=1; j<=nb; j++)
+//       {
+//         //        LR[3][i*nb+j+1]= LR[3][j];
+//         LR[3][i*nb+j+1]= tmp2[j];
+//       }
+//     }
+//     //    size(LR[3]);
+//     LR[3][(s-1)*d+2] = tmp;
+//     LR[3] = list("a",intvec(1: int(d*lV))) + LR[3]; // deg-ord, insert as the 1st
+    // remove everything behind nb*(D+1)+1 ?
+    //    tmp = LR[3];
+    //    LR[3] = tmp[1..size(tmp)-1];
+ // }
+ // L[3] = LR[3];
+  def @R = ring(L);
+  //  setring @R;
+  //  int uptodeg = d; int lV = nvars(basering); // were defined before
+  def @@R = setLetterplaceAttributesElim(@R,uptodeg,lV);
+  return (@@R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y,z),lp;
+  def A = makeLetterplaceRingElim(2);
+  setring A;
+  A;
+  attrib(A,"isLetterplaceRing");
+  attrib(A,"uptodeg");  // degree bound
+  attrib(A,"lV"); // number of variables in the main block
+}
+
+
+
+static proc makeLetterplaceRingNDO(int d)
+"USAGE:  makeLetterplaceRingNDO(d); d an integer
+RETURN:  ring
+PURPOSE: creates a ring with a non-degree first ordering, suitable for
+@* the use of non-homogeneous letterplace
+NOTE: the matrix for the ordering looks as follows:
+@*    'd' blocks of shifted original variables
+EXAMPLE: example makeLetterplaceRingNDO; shows examples
+"
+{
+
+  // ToDo future: inherit positive weights in the orig ring
+  // complain on nonpositive ones
+
+  // d = up to degree, will be shifted to d+1
+  if (d<1) {"bad d"; return(0);}
+
+  int uptodeg = d; int lV = nvars(basering);
+
+  int ppl = printlevel-voice+2;
+  string err = "";
+
+  int i,j,s;
+  def save = basering;
+  int D = d-1;
+  list LR  = ringlist(save);
+  list L, tmp, tmp2, tmp3;
+  L[1] = LR[1]; // ground field
+  L[4] = LR[4]; // quotient ideal
+  tmp  = LR[2]; // varnames
+  s = size(LR[2]);
+  for (i=1; i<=D; i++)
+  {
+    for (j=1; j<=s; j++)
+    {
+      tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")";
+    }
+  }
+  for (i=1; i<=s; i++)
+  {
+    tmp[i] = string(tmp[i])+"("+string(1)+")";
+  }
+  L[2] = tmp;
+  list OrigNames = LR[2];
+  // ordering: one 1..1 a above
+  // ordering: d blocks of the ord on r
+  // try to get whether the ord on r is blockord itself
+  // TODO: make L(2) ordering! exponent is maximally 2
+  s = size(LR[3]);
+  if (s==2)
+  {
+    // not a blockord, 1 block + module ord
+    tmp = LR[3][s]; // module ord
+    for (i=1; i<=d; i++)
+    {
+      LR[3][i] = LR[3][1];
+    }
+    //    LR[3][s+D] = tmp;
+    LR[3][d+1] = tmp;
+    //LR[3][1] = list("a",intvec(1: int(d*lV))); // deg-ord not wanted here
+  }
+  if (s>2)
+  {
+    // there are s-1 blocks
+    int nb = s-1;
+    tmp = LR[3][s]; // module ord to place at the very end
+    tmp2 = LR[3]; tmp2 = tmp2[1..nb];
+    //tmp3[1] = list("a",intvec(1: int(d*lV))); // deg-ord not wanted here
+    for (i=1; i<=d; i++)
+    {
+      tmp3 = tmp3 + tmp2;
+    }
+    tmp3 = tmp3 + list(tmp);
+    LR[3] = tmp3;
+//     for (i=1; i<=d; i++)
+//     {
+//       for (j=1; j<=nb; j++)
+//       {
+//         //        LR[3][i*nb+j+1]= LR[3][j];
+//         LR[3][i*nb+j+1]= tmp2[j];
+//       }
+//     }
+//     //    size(LR[3]);
+//     LR[3][(s-1)*d+2] = tmp;
+//     LR[3] = list("a",intvec(1: int(d*lV))) + LR[3]; // deg-ord, insert as the 1st
+    // remove everything behind nb*(D+1)+1 ?
+    //    tmp = LR[3];
+    //    LR[3] = tmp[1..size(tmp)-1];
+  }
+  L[3] = LR[3];
+  def @R = ring(L);
+  //  setring @R;
+  //  int uptodeg = d; int lV = nvars(basering); // were defined before
+  def @@R = setLetterplaceAttributes(@R,uptodeg,lV);
+  return (@@R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y,z),lp;
+  def A = makeLetterplaceRingNDO(2);
+  setring A;
+  A;
+  attrib(A,"isLetterplaceRing");
+  attrib(A,"uptodeg");  // degree bound
+  attrib(A,"lV"); // number of variables in the main block
+}
+
+static proc setLetterplaceAttributesElim(def R, int uptodeg, int lV)
+"USAGE: setLetterplaceAttributesElim(R, d, b, eV); R a ring, b,d, eV integers
+RETURN: ring with special attributes set
+PURPOSE: sets attributes for a letterplace ring:
+@*      'isLetterplaceRing' = true, 'uptodeg' = d, 'lV' = b, 'eV' = eV, where
+@*      'uptodeg' stands for the degree bound,
+@*      'lV' for the number of variables in the block 0
+@*      'eV' for the number of elimination variables
+NOTE: Activate the resulting ring by using @code{setring}
+"
+{
+  if (uptodeg*lV != nvars(R))
+  {
+    ERROR("uptodeg and lV do not agree on the basering!");
+  }
+
+
+    // Set letterplace-specific attributes for the output ring!
+  attrib(R, "uptodeg", uptodeg);
+  attrib(R, "lV", lV);
+  attrib(R, "isLetterplaceRing", 1);
+  attrib(R, "HasElimOrd", 1);
+  return (R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x(1),y(1),x(2),y(2),x(3),y(3),x(4),y(4)),dp;
+  def R = setLetterplaceAttributesElim(r, 4, 2, 1); setring R;
+  attrib(R,"isLetterplaceRing");
+  lieBracket(x(1),y(1),2);
+}
+
+
+static proc lpElimIdeal(ideal I)
+"
+does not work for degree reasons (deg function does not work for lp rings -> newone!)
+"
+{
+  def lpring = attrib(basering,"isLetterplaceRing");
+  def lpEO =  attrib(basering,"HasElimOrd");
+  if ( typeof(lpring)!="int" && typeof(lpEO)!="int")
+  {
+    ERROR("Ring is not a lp-ring with an elimination ordering");
+  }
+
+  //int nE = attrib(basering, "eV");
+
+  return(letplaceGBasis(I));
+}
+
+
+static proc makeLetterplaceRingWt(int d, intvec W)
+"USAGE:  makeLetterplaceRingWt(d,W); d an integer, W a vector of positive integers
+RETURN:  ring
+PURPOSE: creates a ring with a special ordering, suitable for
+@* the use of non-homogeneous letterplace
+NOTE: the matrix for the ordering looks as follows: first row is W,W,W,...
+@* then there come 'd' blocks of shifted original variables
+EXAMPLE: example makeLetterplaceRing2; shows examples
+"
+{
+
+  // ToDo future: inherit positive weights in the orig ring
+  // complain on nonpositive ones
+
+  // d = up to degree, will be shifted to d+1
+  if (d<1) {"bad d"; return(0);}
+
+  int uptodeg = d; int lV = nvars(basering);
+
+  //check weightvector
+  if (size(W) <> lV) {"bad weights"; return(0);}
+
+  int i;
+  for (i = 1; i <= size(W); i++) {if (W[i] < 0) {"bad weights"; return(0);}}
+  intvec Wt = W;
+  for (i = 2; i <= d; i++) {Wt = Wt, W;}
+  kill i;
+
+  int ppl = printlevel-voice+2;
+  string err = "";
+
+  int i,j,s;
+  def save = basering;
+  int D = d-1;
+  list LR  = ringlist(save);
+  list L, tmp, tmp2, tmp3;
+  L[1] = LR[1]; // ground field
+  L[4] = LR[4]; // quotient ideal
+  tmp  = LR[2]; // varnames
+  s = size(LR[2]);
+  for (i=1; i<=D; i++)
+  {
+    for (j=1; j<=s; j++)
+    {
+      tmp[i*s+j] = string(tmp[j])+"("+string(i+1)+")";
+    }
+  }
+  for (i=1; i<=s; i++)
+  {
+    tmp[i] = string(tmp[i])+"("+string(1)+")";
+  }
+  L[2] = tmp;
+  list OrigNames = LR[2];
+  // ordering: one 1..1 a above
+  // ordering: d blocks of the ord on r
+  // try to get whether the ord on r is blockord itself
+  // TODO: make L(2) ordering! exponent is maximally 2
+  s = size(LR[3]);
+  if (s==2)
+  {
+    // not a blockord, 1 block + module ord
+    tmp = LR[3][s]; // module ord
+    for (i=1; i<=d; i++)
+    {
+      LR[3][s-1+i] = LR[3][1];
+    }
+    //    LR[3][s+D] = tmp;
+    LR[3][s+1+D] = tmp;
+    LR[3][1] = list("a",Wt); // deg-ord
+  }
+  if (s>2)
+  {
+    // there are s-1 blocks
+    int nb = s-1;
+    tmp = LR[3][s]; // module ord to place at the very end
+    tmp2 = LR[3]; tmp2 = tmp2[1..nb];
+    tmp3[1] = list("a",Wt); // deg-ord, insert as the 1st
+    for (i=1; i<=d; i++)
+    {
+      tmp3 = tmp3 + tmp2;
+    }
+    tmp3 = tmp3 + list(tmp);
+    LR[3] = tmp3;
+
+  }
+  L[3] = LR[3];
+  def @R = ring(L);
+  //  setring @R;
+  //  int uptodeg = d; int lV = nvars(basering); // were defined before
+  def @@R = setLetterplaceAttributes(@R,uptodeg,lV);
+  return (@@R);
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y,z),(dp(1),dp(2));
+  def A = makeLetterplaceRingWt(2,intvec(1,2,3));
+  setring A;
+  A;
+  attrib(A,"isLetterplaceRing");
+  attrib(A,"uptodeg");  // degree bound
+  attrib(A,"lV"); // number of variables in the main block
+}
+*/