Difference between revisions of "Category:ApCoCoA-1:Package gbmr"

From ApCoCoAWiki
Line 1: Line 1:
−
Package gbmr is designed to provide basic operations over monoid rings and compute Groebner bases of finite generated ideals.
+
Package gbmr is designed to provide basic operations (addition, subtraction, multiplication) over monoid rings and Groebner basis computations for finite generated (one and two-sided) ideals.
  
−
For the field of rationals '''Q''' and a monoid '''M''' presented by a string rewriting system ('''Alphabet''', '''Rs'''), where '''Alphabet''' is finite alphabet and '''Rs''' is set of '''Relation'''s, let Q[M] denote the ring of all finite formal sums (called '''Polynomial'''s) a_{1}*w_{1}+ a_{2}*w_{2} +...+a_{n}*w_{n} with '''Coefficient'''s a_{i} in Q\{0} and '''Term'''s w_{i} in M. This ring is called the '''monoid ring''' of M over Q.
+
Let Q be rational field and M=<X, R> be a finited presented monoid, where X is a finite alphabet and R is a finite set of relations. A monoid ring of M over Q, denoted by Q[M], is a ing of all finite formal sums (called polynomials) a_{1}*w_{1}+ a_{2}*w_{2} +...+a_{n}*w_{n} with coefficients a_{i} in Q\{0} and terms w_{i} in M.
  
−
Notice that in this package
+
Notice that
  
−
(i) '''Alphabet''' is of '''STRING''' type. Every letters in Alphabet MUST appear ONLY ONCE, since the order of letters in '''Alphabet''' will induce the order of terms later. For example, Alphabet:="abc"; Order:="LLEX"; means length-lex ordering induced by the ordering a>b>c.
+
(i) X is of STRING type in this package. Every letters in X MUST appear only once. The order of letters in X is very important, since it induces a term ordering later. For example, X:="abc"; Order:="LLEX"; means a length-lexicographic ordering induced by a>b>c.
  
−
(ii) Each '''Polynomial''' is represented as a LIST of LISTs, which are pairs of '''Term''' (of '''STRING''' type) and corresponding '''Coefficient'''. '''Polynomial:=[[Term,Coefficient],...,[Term, Coefficient]]'''. For example, polynomial F:=a+1 is represented as F:=[[1,"a"], [1,""]].  
+
(ii) Each element (relation) in R is of form [L, R], where L and R are terms in M. Each term in M is represented as a STRING. For example, xy^2x is represented as "xyyx", and relation (yx, xy) is represented as ["yx", "xy"].
  
−
(iii) Each '''Relation''' is a pair '''[L:Term, R:Polynomial]''', where '''L''' is left side of relation and '''R''' is right side of relation. For example, R:=["ba",[[1,"ab"], [1,""]]]; means relation ba->ab+1.  
+
(iii) Each polynomial in Q[M] is represented as a LIST of LISTs, which are pairs of form [a_{i}, w_{i}]. For example, polynomial F:=xy-y+1 is represented as F:=[[1,"xy"], [-1, "y"], [1,""]].  
  
−
(iv) '''Order''' is a total well-founded admissible ordering induced by the order of letters in '''Alphabet'''. It is represented as a '''STRING''', which is the name of ordering. And "LLEX" (length-lex ordering) is the only ordering supported currently.
+
(iv) Ordering is of STRING type, which is an abbreviated name of a term ordering. For exapme, "LLEX" stands for a length-lexicographic ordering and "ELIM" stands for an elimination ordering. These two term orderings are the only supported orderings currently.
  
  

Revision as of 08:36, 26 May 2010

Package gbmr is designed to provide basic operations (addition, subtraction, multiplication) over monoid rings and Groebner basis computations for finite generated (one and two-sided) ideals.

Let Q be rational field and M=<X, R> be a finited presented monoid, where X is a finite alphabet and R is a finite set of relations. A monoid ring of M over Q, denoted by Q[M], is a ing of all finite formal sums (called polynomials) a_{1}*w_{1}+ a_{2}*w_{2} +...+a_{n}*w_{n} with coefficients a_{i} in Q\{0} and terms w_{i} in M.

Notice that

(i) X is of STRING type in this package. Every letters in X MUST appear only once. The order of letters in X is very important, since it induces a term ordering later. For example, X:="abc"; Order:="LLEX"; means a length-lexicographic ordering induced by a>b>c.

(ii) Each element (relation) in R is of form [L, R], where L and R are terms in M. Each term in M is represented as a STRING. For example, xy^2x is represented as "xyyx", and relation (yx, xy) is represented as ["yx", "xy"].

(iii) Each polynomial in Q[M] is represented as a LIST of LISTs, which are pairs of form [a_{i}, w_{i}]. For example, polynomial F:=xy-y+1 is represented as F:=[[1,"xy"], [-1, "y"], [1,""]].

(iv) Ordering is of STRING type, which is an abbreviated name of a term ordering. For exapme, "LLEX" stands for a length-lexicographic ordering and "ELIM" stands for an elimination ordering. These two term orderings are the only supported orderings currently.


Let p, f be two non-zero polynomials in Q[M]. We say f prefix reduces p to q at a monomial a*t of p in one step, denoted by p-->_{f}q if 

 (1) LT(f)w = t for some w in M, i.e., LT(f) is a prefix of t, and
 (2) q = p-a*LT(f)^{-1}*f*w.

A set G is said to be a Groebner basis with respect to the reduction -->, if <-->_{G} = Equiv_{Ideal(G)} and -->_{G} is confluent.


Please note: The function(s) explained on this page is/are using the ApCoCoAServer. You will have to start the ApCoCoAServer in order to use it/them.

Retrieved from "http://apcocoa.uni-passau.de/wiki/index.php?title=Category:ApCoCoA-1:Package_gbmr&oldid=10506"