# Difference between revisions of "ApCoCoA-1:NCo.PrefixReducedGB"

(New page: <command> <title>NCo.PrefixReducedGB</title> <short_description> Compute a prefix reduced Groebner basis of a finitely generated right ideal in a finitely presented monoid ring. <par/> Let...) |
m (replaced <quotes> tag by real quotes) |
||

(5 intermediate revisions by 3 users not shown) | |||

Line 1: | Line 1: | ||

+ | {{Version|1}} | ||

<command> | <command> | ||

<title>NCo.PrefixReducedGB</title> | <title>NCo.PrefixReducedGB</title> | ||

<short_description> | <short_description> | ||

Compute a prefix reduced Groebner basis of a finitely generated right ideal in a finitely presented monoid ring. | Compute a prefix reduced Groebner basis of a finitely generated right ideal in a finitely presented monoid ring. | ||

− | |||

− | |||

</short_description> | </short_description> | ||

<syntax> | <syntax> | ||

Line 10: | Line 9: | ||

</syntax> | </syntax> | ||

<description> | <description> | ||

+ | Let <tt>P=K<X|R></tt> be a finitely presented monoid ring, and let <tt>I</tt> be a right ideal of <tt>P</tt>. Given a word ordering <tt>Ordering</tt>, a set <tt>G</tt> of non-zero polynomials is called a <em>prefix Groebner basis</em> of <tt>I</tt> with respect to <tt>Ordering</tt> if, for each non-zero polynomial <tt>f</tt> in <tt>I</tt>, there exists a polynomial <tt>g</tt> such that the leading word of <tt>g</tt> is a prefix of the leading word of <tt>f</tt>. A prefix Groebner basis <tt>G</tt> is called a <em>prefix reduced Groebner basis</em> if <tt>G</tt> is interreduced (see <ref>ApCoCoA-1:NCo.PrefixInterreduction|NCo.PrefixInterreduction</ref>) and all polynomials in <tt>G</tt> are monic. Note that each ideal has a unique prefix reduced Groebner basis. However, it is not necessarily finite. Thus this function might not terminate. | ||

+ | <par/> | ||

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

<par/> | <par/> | ||

− | Please set ring environment coefficient field <tt> K</tt>, alphabet (or set of indeterminates) <tt>X</tt>, rewrite relations <tt>Relations</tt> and word ordering <tt>Ordering</tt> through the functions <ref>NCo.SetFp</ref>, <ref>NCo.SetX</ref>, <ref>NCo.SetRelations</ref> and <ref>NCo.SetOrdering</ref>, respectively, before using this function. The default coefficient field is the field of rational numbers, i.e. RAT in CoCoAL, and the default ordering is the length-lexicographic ordering | + | Please set ring environment coefficient field <tt> K</tt>, alphabet (or set of indeterminates) <tt>X</tt>, rewrite relations <tt>Relations</tt> and word ordering <tt>Ordering</tt> through the functions <ref>ApCoCoA-1:NCo.SetFp|NCo.SetFp</ref>, <ref>ApCoCoA-1:NCo.SetX|NCo.SetX</ref>, <ref>ApCoCoA-1:NCo.SetRelations|NCo.SetRelations</ref> and <ref>ApCoCoA-1:NCo.SetOrdering|NCo.SetOrdering</ref>, respectively, before using this function. The default coefficient field is the field of rational numbers, i.e. RAT in CoCoAL, and the default ordering is the length-lexicographic ordering "LLEX". For more information, please check the relevant functions. |

<itemize> | <itemize> | ||

− | <item>@param <em>G:</em> a LIST of non-zero polynomials generating a right ideal in the monoid ring. Each polynomial is represented as a LIST of LISTs, i.e. as <tt>[[C1,W1],...,[Cs,Ws]]</tt> where, for each i, Wi is a term represented as a STRING and Ci is the coefficient of Wi. For example, polynomial <tt>f=xy-y+1</tt> is represented as F:=[[1, | + | <item>@param <em>G:</em> a LIST of non-zero polynomials generating a right ideal in the monoid ring. Each polynomial is represented as a LIST of LISTs, i.e. as <tt>[[C1,W1],...,[Cs,Ws]]</tt> where, for each i, Wi is a term represented as a STRING and Ci is the coefficient of Wi. For example, polynomial <tt>f=xy-y+1</tt> is represented as F:=[[1,"xy"], [-1, "y"], [1,""]]. The zero polynomial <tt>0</tt> is represented as the empty LIST [].</item> |

<item>@return: a LIST of polynomials, which is a prefix reduced Groebner basis of the right ideal generated by G.</item> | <item>@return: a LIST of polynomials, which is a prefix reduced Groebner basis of the right ideal generated by G.</item> | ||

</itemize> | </itemize> | ||

<example> | <example> | ||

− | NCo.SetX( | + | NCo.SetX("abc"); |

− | NCo.SetOrdering( | + | NCo.SetOrdering("LLEX"); |

− | NCo.SetRelations([[ | + | NCo.SetRelations([["aa",""], ["bb",""], ["ab","c"], ["ac", "b"], ["cb", "a"]]); |

− | F := [[1, | + | F := [[1,"a"],[1,"b"],[1,"c"]]; |

NCo.PrefixReducedGB([F]); | NCo.PrefixReducedGB([F]); | ||

− | [[[1, | + | [[[1, "b"], [-1, ""]], [[1, "a"], [1, "c"], [1, ""]], [[1, "cc"], [1, "c"], [1, ""]], [[1, "ca"], [-1, "c"]]] |

-------------------------------- | -------------------------------- | ||

</example> | </example> | ||

</description> | </description> | ||

<seealso> | <seealso> | ||

− | <see>NCo.PrefixGB</see> | + | <see>ApCoCoA-1:NCo.PrefixGB|NCo.PrefixGB</see> |

− | <see>NCo.PrefixInterreduction</see> | + | <see>ApCoCoA-1:NCo.PrefixInterreduction|NCo.PrefixInterreduction</see> |

− | <see>NCo.PrefixNR</see> | + | <see>ApCoCoA-1:NCo.PrefixNR|NCo.PrefixNR</see> |

− | <see>NCo.PrefixSaturation</see> | + | <see>ApCoCoA-1:NCo.PrefixSaturation|NCo.PrefixSaturation</see> |

− | <see>Introduction to CoCoAServer</see> | + | <see>ApCoCoA-1:NCo.SetFp|NCo.SetFp</see> |

+ | <see>ApCoCoA-1:NCo.SetOrdering|NCo.SetOrdering</see> | ||

+ | <see>ApCoCoA-1:NCo.SetRelations|NCo.SetRelations</see> | ||

+ | <see>ApCoCoA-1:NCo.SetX|NCo.SetX</see> | ||

+ | <see>ApCoCoA-1:Introduction to CoCoAServer|Introduction to CoCoAServer</see> | ||

</seealso> | </seealso> | ||

<types> | <types> | ||

Line 45: | Line 50: | ||

<key>NCo.PrefixReducedGB</key> | <key>NCo.PrefixReducedGB</key> | ||

<key>PrefixReducedGB</key> | <key>PrefixReducedGB</key> | ||

− | <wiki-category>Package_gbmr</wiki-category> | + | <wiki-category>ApCoCoA-1:Package_gbmr</wiki-category> |

</command> | </command> |

## Latest revision as of 13:44, 29 October 2020

This article is about a function from ApCoCoA-1. |

## NCo.PrefixReducedGB

Compute a prefix reduced Groebner basis of a finitely generated right ideal in a finitely presented monoid ring.

### Syntax

NCo.PrefixReducedGB(G:LIST):LIST

### Description

Let `P=K<X|R>` be a finitely presented monoid ring, and let `I` be a right ideal of `P`. Given a word ordering `Ordering`, a set `G` of non-zero polynomials is called a *prefix Groebner basis* of `I` with respect to `Ordering` if, for each non-zero polynomial `f` in `I`, there exists a polynomial `g` such that the leading word of `g` is a prefix of the leading word of `f`. A prefix Groebner basis `G` is called a *prefix reduced Groebner basis* if `G` is interreduced (see NCo.PrefixInterreduction) and all polynomials in `G` are monic. Note that each ideal has a unique prefix reduced Groebner basis. However, it is not necessarily finite. Thus this function might not terminate.

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

Please set ring environment coefficient field ` K`, alphabet (or set of indeterminates) `X`, rewrite relations `Relations` and word ordering `Ordering` through the functions NCo.SetFp, NCo.SetX, NCo.SetRelations and NCo.SetOrdering, respectively, before using this function. The default coefficient field is the field of rational numbers, i.e. RAT in CoCoAL, and the default ordering is the length-lexicographic ordering "LLEX". For more information, please check the relevant functions.

@param

*G:*a LIST of non-zero polynomials generating a right ideal in the monoid ring. Each polynomial is represented as a LIST of LISTs, i.e. as`[[C1,W1],...,[Cs,Ws]]`where, for each i, Wi is a term represented as a STRING and Ci is the coefficient of Wi. For example, polynomial`f=xy-y+1`is represented as F:=[[1,"xy"], [-1, "y"], [1,""]]. The zero polynomial`0`is represented as the empty LIST [].@return: a LIST of polynomials, which is a prefix reduced Groebner basis of the right ideal generated by G.

#### Example

NCo.SetX("abc"); NCo.SetOrdering("LLEX"); NCo.SetRelations([["aa",""], ["bb",""], ["ab","c"], ["ac", "b"], ["cb", "a"]]); F := [[1,"a"],[1,"b"],[1,"c"]]; NCo.PrefixReducedGB([F]); [[[1, "b"], [-1, ""]], [[1, "a"], [1, "c"], [1, ""]], [[1, "cc"], [1, "c"], [1, ""]], [[1, "ca"], [-1, "c"]]] --------------------------------

### See also