Home Online Manual
Top
Back: Monomial orderings on free algebras
Forward: Letterplace correspondence
FastBack:
FastForward:
Up: Singular Manual
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

7.9.3 Groebner bases for two-sided ideals in free associative algebras

We say that a monomial $v$ divides (two-sided or bilaterally) a monomial $w$, if there exist monomials $p,s \in X$, such that $w = p \cdot v \cdot s$, in other words $v$ is a subword of $w$.

For a subset $G \subset K\langle x_1,\dots,x_n \rangle =: T$, define the leading ideal of $G$ to be the two-sided ideal $LM(G) \; = \; {}_{T} \langle$ $\; \{lm(g) \;\vert\; g \in G\setminus\{0\} \}$ $\; \rangle_{T} \subseteq T$.

Let $<$ be a fixed monomial ordering on $T$. We say that a subset $G\subset I$ is a (two-sided) Groebner basis for the ideal $I$ with respect to $<$, if $LM(G) = LM(I)$. That is $\forall f\in I\setminus\{0\}$ there exists $g\in G$, such that $lm(g)$ divides $lm(f)$.

Suppose, that the weights of the ring variables are strictly positive. We can interprete these weights as defining a nonstandard grading on the ring. If the set of input polynomials is weighted homogeneous with respect to the given weights of the ring variables, then computing up to a weighted degree (and thus, also length) bound $d$

results in the truncated Groebner basis $G(d)$. In other words, by trimming elements of degree exceeding $d$ from the complete Groebner basis $G$, one obtains precisely $G(d)$.

In general, given a set $G(d)$, which is the result of Groebner basis computation up to weighted degree bound $d$, then it is the complete finite Groebner basis, if and only if $G(2d-1)=G(d)$ holds.