Difference between revisions of "ApCoCoA-1:NCo.BIsGB"

From ApCoCoAWiki
(New page: <command> <title>NCo.BIsGB</title> <short_description> Check whether a finite LIST of non-zero polynomials in a free monoid ring over the binary field F_{2}={0,1} is a Groebner basis. <par...)
 
m (replaced <quotes> tag by real quotes)
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
{{Version|1}}
 
<command>
 
<command>
 
<title>NCo.BIsGB</title>
 
<title>NCo.BIsGB</title>
 
<short_description>
 
<short_description>
 
Check whether a finite LIST of non-zero polynomials in a free monoid ring over the binary field F_{2}={0,1} is a Groebner basis.
 
Check whether a finite LIST of non-zero polynomials in a free monoid ring over the binary field F_{2}={0,1} is a Groebner basis.
<par/>
 
Note that, given an ideal <tt>I</tt> and a word ordering <tt>Ordering</tt>, a set <tt>Gb</tt> of non-zero polynomials is called a <em>Groebner basis</em> of <tt>I</tt> with respect to <tt>Ordering</tt> if the leading word set <tt>LW{Gb}</tt> generates the leading word ideal <tt>LW(I)</tt>. The function checks whether a given finite set of non-zero polynomials <tt>G</tt> is a Groebner basis by using the <tt>Buchberger Criterion</tt>, i.e. <tt>G</tt> is a Groebner basis if the S-polynomials of all obstructions of <tt>G</tt> have the zero normal remainder with respect to <tt>G</tt>.
 
 
</short_description>
 
</short_description>
 
<syntax>
 
<syntax>
Line 10: Line 9:
 
</syntax>
 
</syntax>
 
<description>
 
<description>
 +
Given a word ordering <tt>Ordering</tt>, a set <tt>Gb</tt> of non-zero polynomials is called a <em>Groebner basis</em> with respect to <tt>Ordering</tt> if the leading word set <tt>BLW{Gb}</tt> generates the leading word ideal <tt>BLW(&lt;Gb&gt;)</tt>. The function checks whether a given finite set of non-zero polynomials <tt>G</tt> is a Groebner basis by using the <tt>Buchberger Criterion</tt>, i.e. <tt>G</tt> is a Groebner basis if the S-polynomials of all obstructions of <tt>G</tt> have the zero normal remainder with respect to <tt>G</tt>.
 +
<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 <em>alphabet</em> (or set of indeterminates) <tt>X</tt> and <em>word ordering</em> via the functions <ref>NCo.SetX</ref> and <ref>NCo.SetOrdering</ref>, respectively, before calling this function. The default ordering is the length-lexicographic ordering (<quotes>LLEX</quotes>). For more information, please check the relevant functions.
+
Please set ring environment <em>alphabet</em> (or set of indeterminates) <tt>X</tt> and <em>word ordering</em> via the functions <ref>ApCoCoA-1:NCo.SetX|NCo.SetX</ref> and <ref>ApCoCoA-1:NCo.SetOrdering|NCo.SetOrdering</ref>, respectively, before calling this function. 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 in the free monoid ring <tt>F_{2}&lt;X&gt;</tt>. Each polynomial is represented as a LIST of words (or terms) in <tt>&lt;X&gt;</tt>. Each word is represented as a STRING. For example, <tt>xy^2x</tt> is represented as <quotes>xyyx</quotes>, and the identity is represented as the empty string <quotes></quotes>. Thus, the polynomial <tt>f=xy-y+1</tt> is represented as F:=[<quotes>xy</quotes>, <quotes>y</quotes>, <quotes></quotes>]. The zero polynomial <tt>0</tt> is represented as the empty LIST [].</item>
+
<item>@param <em>G:</em> a LIST of non-zero polynomials in the free monoid ring <tt>F_{2}&lt;X&gt;</tt>. Each polynomial is represented as a LIST of words (or terms) in <tt>&lt;X&gt;</tt>. Each word is represented as a STRING. For example, <tt>xy^2x</tt> is represented as "xyyx", and the identity is represented as the empty string "". Thus, the polynomial <tt>f=xy-y+1</tt> is represented as F:=["xy", "y", ""]. The zero polynomial <tt>0</tt> is represented as the empty LIST [].</item>
 
<item>@return: a BOOL, which is True if G is a Groebner basis with respect to the current word ordering and is False otherwise.</item>
 
<item>@return: a BOOL, which is True if G is a Groebner basis with respect to the current word ordering and is False otherwise.</item>
 
</itemize>
 
</itemize>
 
<example>
 
<example>
NCo.SetX(<quotes>ab</quotes>);
+
NCo.SetX("ab");
NCo.SetOrdering(<quotes>LLEX</quotes>);
+
NCo.SetOrdering("LLEX");
F1:=[<quotes>aa</quotes>, <quotes></quotes>];
+
F1:=["aa", ""];
F2:=[<quotes>bbb</quotes>, <quotes></quotes>];
+
F2:=["bbb", ""];
F3:=[<quotes>abababbabbabababbabb</quotes>, <quotes></quotes>];
+
F3:=["abababbabbabababbabb", ""];
 
G:=[F1,F2,F3];
 
G:=[F1,F2,F3];
 
NCo.BIsGB(G);
 
NCo.BIsGB(G);
Line 31: Line 32:
 
GB;
 
GB;
  
[[<quotes>aa</quotes>, <quotes></quotes>], [<quotes>bbb</quotes>, <quotes></quotes>], [<quotes>abbabbabab</quotes>, <quotes>bbabbababa</quotes>],  
+
[["aa", ""], ["bbb", ""], ["abbabbabab", "bbabbababa"],  
[<quotes>abbabababb</quotes>, <quotes>babbabbaba</quotes>], [<quotes>ababbabbab</quotes>, <quotes>bbabababba</quotes>], [<quotes>abababbabb</quotes>, <quotes>bababbabba</quotes>],  
+
["abbabababb", "babbabbaba"], ["ababbabbab", "bbabababba"], ["abababbabb", "bababbabba"],  
[<quotes>babbabbabab</quotes>, <quotes>abbababa</quotes>], [<quotes>ababbabbaba</quotes>, <quotes>bbabababb</quotes>], [<quotes>bbabbabababb</quotes>, <quotes>abbabbaba</quotes>],  
+
["babbabbabab", "abbababa"], ["ababbabbaba", "bbabababb"], ["bbabbabababb", "abbabbaba"],  
[<quotes>bbabababbabb</quotes>, <quotes>ababbabba</quotes>], [<quotes>ababbabbabab</quotes>, <quotes>bbababa</quotes>], [<quotes>bababbabbabab</quotes>, <quotes>ababa</quotes>],  
+
["bbabababbabb", "ababbabba"], ["ababbabbabab", "bbababa"], ["bababbabbabab", "ababa"],  
[<quotes>abababbababab</quotes>, <quotes>babababbababa</quotes>], [<quotes>ababababbabab</quotes>, <quotes>bababbabababa</quotes>], [<quotes>abbababababbab</quotes>, <quotes>babbababababba</quotes>],  
+
["abababbababab", "babababbababa"], ["ababababbabab", "bababbabababa"], ["abbababababbab", "babbababababba"],  
[<quotes>ababbababababb</quotes>, <quotes>bbababababbaba</quotes>], [<quotes>abababbabbabab</quotes>, <quotes>baba</quotes>], [<quotes>ababababbababa</quotes>, <quotes>bababbababab</quotes>],  
+
["ababbababababb", "bbababababbaba"], ["abababbabbabab", "baba"], ["ababababbababa", "bababbababab"],  
[<quotes>bbabababbababab</quotes>, <quotes>abababbababa</quotes>], [<quotes>bababbababababb</quotes>, <quotes>ababababbaba</quotes>], [<quotes>ababbababababba</quotes>, <quotes>bbababababbab</quotes>],  
+
["bbabababbababab", "abababbababa"], ["bababbababababb", "ababababbaba"], ["ababbababababba", "bbababababbab"],  
[<quotes>abababbabbababa</quotes>, <quotes>bab</quotes>], [<quotes>bbabbababababbab</quotes>, <quotes>abbababababba</quotes>], [<quotes>abababbababbabab</quotes>, <quotes>bababbababbababa</quotes>],  
+
["abababbabbababa", "bab"], ["bbabbababababbab", "abbababababba"], ["abababbababbabab", "bababbababbababa"],  
[<quotes>abababbabbabababb</quotes>, <quotes>ba</quotes>], [<quotes>bbabababbababbabab</quotes>, <quotes>ababbababbababa</quotes>], [<quotes>babbabbabbabbabbab</quotes>, <quotes>abbababababababba</quotes>],  
+
["abababbabbabababb", "ba"], ["bbabababbababbabab", "ababbababbababa"], ["babbabbabbabbabbab", "abbababababababba"],  
[<quotes>abbabbabbabbabbaba</quotes>, <quotes>bbabbababababababb</quotes>], [<quotes>abbababbababbababa</quotes>, <quotes>bababbabababababab</quotes>], [<quotes>abbabababababababb</quotes>, <quotes>babbabababababbaba</quotes>],  
+
["abbabbabbabbabbaba", "bbabbababababababb"], ["abbababbababbababa", "bababbabababababab"], ["abbabababababababb", "babbabababababbaba"],  
[<quotes>ababbabababababbab</quotes>, <quotes>bbabababababababba</quotes>], [<quotes>abababbabbabababba</quotes>, <quotes>b</quotes>], [<quotes>bbabbababbababbabab</quotes>, <quotes>ababbababababababa</quotes>],  
+
["ababbabababababbab", "bbabababababababba"], ["abababbabbabababba", "b"], ["bbabbababbababbabab", "ababbababababababa"],  
[<quotes>bbabbababababababba</quotes>, <quotes>abbabbabbabbabbab</quotes>], [<quotes>bababbababbababbabb</quotes>, <quotes>abababababababbaba</quotes>], [<quotes>bababbabababababbab</quotes>, <quotes>abababababababba</quotes>],  
+
["bbabbababababababba", "abbabbabbabbabbab"], ["bababbababbababbabb", "abababababababbaba"], ["bababbabababababbab", "abababababababba"],  
[<quotes>bababbababababababa</quotes>, <quotes>abbababbababbabab</quotes>], [<quotes>ababbababbababbabba</quotes>, <quotes>bbabababababababbab</quotes>], [<quotes>ababbabababababbaba</quotes>, <quotes>bbabababababababb</quotes>],  
+
["bababbababababababa", "abbababbababbabab"], ["ababbababbababbabba", "bbabababababababbab"], ["ababbabababababbaba", "bbabababababababb"],  
[<quotes>bbabbabababababababb</quotes>, <quotes>abbabababababbaba</quotes>], [<quotes>bbabababababababbaba</quotes>, <quotes>ababbababbababbabb</quotes>], [<quotes>bababbababbababbabba</quotes>, <quotes>abababababababbab</quotes>],  
+
["bbabbabababababababb", "abbabababababbaba"], ["bbabababababababbaba", "ababbababbababbabb"], ["bababbababbababbabba", "abababababababbab"],  
[<quotes>abababbabbabababbabb</quotes>, <quotes></quotes>], [<quotes>abbababababababababbab</quotes>, <quotes>babbababababababababba</quotes>],  
+
["abababbabbabababbabb", ""], ["abbababababababababbab", "babbababababababababba"],  
[<quotes>ababbababbabababababab</quotes>, <quotes>bababbababbabababababa</quotes>], [<quotes>ababbababababababababb</quotes>, <quotes>bbababababababababbaba</quotes>],  
+
["ababbababbabababababab", "bababbababbabababababa"], ["ababbababababababababb", "bbababababababababbaba"],  
[<quotes>babbababbababbababbabab</quotes>, <quotes>abbabababababababababa</quotes>], [<quotes>bababbababbababbababbab</quotes>, <quotes>ababababababababababba</quotes>],  
+
["babbababbababbababbabab", "abbabababababababababa"], ["bababbababbababbababbab", "ababababababababababba"],  
[<quotes>abbababababababababbaba</quotes>, <quotes>babbababababababababb</quotes>], [<quotes>ababbababbababbababbaba</quotes>, <quotes>bbababababababababababb</quotes>],  
+
["abbababababababababbaba", "babbababababababababb"], ["ababbababbababbababbaba", "bbababababababababababb"],  
[<quotes>ababbababababababababab</quotes>, <quotes>babbabababababababababa</quotes>], [<quotes>ababababababababababbab</quotes>, <quotes>babababababababababbaba</quotes>],  
+
["ababbababababababababab", "babbabababababababababa"], ["ababababababababababbab", "babababababababababbaba"],  
[<quotes>bbabbababababababababbab</quotes>, <quotes>abbababababababababba</quotes>], [<quotes>bbabbabababababababababa</quotes>, <quotes>abbababbababbababbabab</quotes>],  
+
["bbabbababababababababbab", "abbababababababababba"], ["bbabbabababababababababa", "abbababbababbababbabab"],  
[<quotes>bbababababababababababba</quotes>, <quotes>ababbababbababbababbab</quotes>], [<quotes>abbababababababababababb</quotes>, <quotes>babbababbababbababbaba</quotes>],  
+
["bbababababababababababba", "ababbababbababbababbab"], ["abbababababababababababb", "babbababbababbababbaba"],  
[<quotes>ababababababababababbaba</quotes>, <quotes>babababababababababbab</quotes>], [<quotes>abababababababababababab</quotes>, <quotes>babababababababababababa</quotes>],  
+
["ababababababababababbaba", "babababababababababbab"], ["abababababababababababab", "babababababababababababa"],  
[<quotes>abbababababababababababab</quotes>, <quotes>babababababababababababba</quotes>], [<quotes>ababababababababababababb</quotes>, <quotes>bbabababababababababababa</quotes>],  
+
["abbababababababababababab", "babababababababababababba"], ["ababababababababababababb", "bbabababababababababababa"],  
[<quotes>bbabababababababababababab</quotes>, <quotes>abababababababababababa</quotes>], [<quotes>ababababababababababababba</quotes>, <quotes>bbababababababababababab</quotes>]]
+
["bbabababababababababababab", "abababababababababababa"], ["ababababababababababababba", "bbababababababababababab"]]
 
-------------------------------
 
-------------------------------
 
NCo.BIsGB(GB);
 
NCo.BIsGB(GB);
Line 63: Line 64:
 
</description>
 
</description>
 
<seealso>
 
<seealso>
<see>NCo.SetOrdering</see>
+
<see>ApCoCoA-1:NCo.BGB|NCo.BGB</see>
<see>NCo.SetX</see>
+
<see>ApCoCoA-1:NCo.BLW|NCo.BLW</see>
<see>Introduction to CoCoAServer</see>
+
<see>ApCoCoA-1:NCo.BReductedGB|NCo.BReductedGB</see>
 +
<see>ApCoCoA-1:NCo.BTruncatedGB|NCo.BTruncatedGB</see>
 +
<see>ApCoCoA-1:NCo.SetOrdering|NCo.SetOrdering</see>
 +
<see>ApCoCoA-1:NCo.SetX|NCo.SetX</see>
 +
<see>ApCoCoA-1:Introduction to CoCoAServer|Introduction to CoCoAServer</see>
 
</seealso>
 
</seealso>
 
<types>
 
<types>
Line 76: Line 81:
 
<key>NCo.BIsGB</key>
 
<key>NCo.BIsGB</key>
 
<key>BIsGB</key>
 
<key>BIsGB</key>
<wiki-category>Package_gbmr</wiki-category>
+
<wiki-category>ApCoCoA-1:Package_gbmr</wiki-category>
 
</command>
 
</command>

Latest revision as of 13:37, 29 October 2020

This article is about a function from ApCoCoA-1.

NCo.BIsGB

Check whether a finite LIST of non-zero polynomials in a free monoid ring over the binary field F_{2}={0,1} is a Groebner basis.

Syntax

NCo.BIsGB(G:LIST):INT

Description

Given a word ordering Ordering, a set Gb of non-zero polynomials is called a Groebner basis with respect to Ordering if the leading word set BLW{Gb} generates the leading word ideal BLW(<Gb>). The function checks whether a given finite set of non-zero polynomials G is a Groebner basis by using the Buchberger Criterion, i.e. G is a Groebner basis if the S-polynomials of all obstructions of G have the zero normal remainder with respect to G.

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 alphabet (or set of indeterminates) X and word ordering via the functions NCo.SetX and NCo.SetOrdering, respectively, before calling this function. 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 in the free monoid ring F_{2}<X>. Each polynomial is represented as a LIST of words (or terms) in <X>. Each word is represented as a STRING. For example, xy^2x is represented as "xyyx", and the identity is represented as the empty string "". Thus, the polynomial f=xy-y+1 is represented as F:=["xy", "y", ""]. The zero polynomial 0 is represented as the empty LIST [].

  • @return: a BOOL, which is True if G is a Groebner basis with respect to the current word ordering and is False otherwise.

Example

NCo.SetX("ab");
NCo.SetOrdering("LLEX");
F1:=["aa", ""];
F2:=["bbb", ""];
F3:=["abababbabbabababbabb", ""];
G:=[F1,F2,F3];
NCo.BIsGB(G);

False
-------------------------------
GB:=NCo.GGB(G);
GB;

[["aa", ""], ["bbb", ""], ["abbabbabab", "bbabbababa"], 
["abbabababb", "babbabbaba"], ["ababbabbab", "bbabababba"], ["abababbabb", "bababbabba"], 
["babbabbabab", "abbababa"], ["ababbabbaba", "bbabababb"], ["bbabbabababb", "abbabbaba"], 
["bbabababbabb", "ababbabba"], ["ababbabbabab", "bbababa"], ["bababbabbabab", "ababa"], 
["abababbababab", "babababbababa"], ["ababababbabab", "bababbabababa"], ["abbababababbab", "babbababababba"], 
["ababbababababb", "bbababababbaba"], ["abababbabbabab", "baba"], ["ababababbababa", "bababbababab"], 
["bbabababbababab", "abababbababa"], ["bababbababababb", "ababababbaba"], ["ababbababababba", "bbababababbab"], 
["abababbabbababa", "bab"], ["bbabbababababbab", "abbababababba"], ["abababbababbabab", "bababbababbababa"], 
["abababbabbabababb", "ba"], ["bbabababbababbabab", "ababbababbababa"], ["babbabbabbabbabbab", "abbababababababba"], 
["abbabbabbabbabbaba", "bbabbababababababb"], ["abbababbababbababa", "bababbabababababab"], ["abbabababababababb", "babbabababababbaba"], 
["ababbabababababbab", "bbabababababababba"], ["abababbabbabababba", "b"], ["bbabbababbababbabab", "ababbababababababa"], 
["bbabbababababababba", "abbabbabbabbabbab"], ["bababbababbababbabb", "abababababababbaba"], ["bababbabababababbab", "abababababababba"], 
["bababbababababababa", "abbababbababbabab"], ["ababbababbababbabba", "bbabababababababbab"], ["ababbabababababbaba", "bbabababababababb"], 
["bbabbabababababababb", "abbabababababbaba"], ["bbabababababababbaba", "ababbababbababbabb"], ["bababbababbababbabba", "abababababababbab"], 
["abababbabbabababbabb", ""], ["abbababababababababbab", "babbababababababababba"], 
["ababbababbabababababab", "bababbababbabababababa"], ["ababbababababababababb", "bbababababababababbaba"], 
["babbababbababbababbabab", "abbabababababababababa"], ["bababbababbababbababbab", "ababababababababababba"], 
["abbababababababababbaba", "babbababababababababb"], ["ababbababbababbababbaba", "bbababababababababababb"], 
["ababbababababababababab", "babbabababababababababa"], ["ababababababababababbab", "babababababababababbaba"], 
["bbabbababababababababbab", "abbababababababababba"], ["bbabbabababababababababa", "abbababbababbababbabab"], 
["bbababababababababababba", "ababbababbababbababbab"], ["abbababababababababababb", "babbababbababbababbaba"], 
["ababababababababababbaba", "babababababababababbab"], ["abababababababababababab", "babababababababababababa"], 
["abbababababababababababab", "babababababababababababba"], ["ababababababababababababb", "bbabababababababababababa"], 
["bbabababababababababababab", "abababababababababababa"], ["ababababababababababababba", "bbababababababababababab"]]
-------------------------------
NCo.BIsGB(GB);

True
-------------------------------

See also

NCo.BGB

NCo.BLW

NCo.BReductedGB

NCo.BTruncatedGB

NCo.SetOrdering

NCo.SetX

Introduction to CoCoAServer