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 over monoid rings and compute Groebner bases of finite generated 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 coefficients a_{i} in Q\{0} and terms w_{i} in M. This ring is called the '''monoid ring''' of M over Q.
+
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.
  
 
Notice that in this package
 
Notice that in this package

Revision as of 12:13, 22 October 2009

Package gbmr is designed to provide basic operations over monoid rings and compute Groebner bases of finite generated 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 Relations, let Q[M] denote the ring 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. This ring is called the monoid ring of M over Q.

Notice that in this package

(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.

(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,""]].

(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.

(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.


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.