<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html><head> <title>GAP (AutMan) - Appendix D: Semilinear expressions</title> <meta http-equiv="content-type" content="text/html; charset=iso-8859-1"> <meta name="generator" content="GAPDoc2HTML"> <link rel=stylesheet type="text/css" href="manual.css"> </head> <body> <div class="pcenter"><table class="chlink"><tr><td class="chlink1">Goto Chapter: </td><td><a href="chap0.html">Top</a></td><td><a href="chap1.html">1</a></td><td><a href="chap2.html">2</a></td><td><a href="chap3.html">3</a></td><td><a href="chap4.html">4</a></td><td><a href="chap5.html">5</a></td><td><a href="chapA.html">A</a></td><td><a href="chapB.html">B</a></td><td><a href="chapBib.html">Bib</a></td><td><a href="chapC.html">C</a></td><td><a href="chapD.html">D</a></td><td><a href="chapE.html">E</a></td><td><a href="chapInd.html">Ind</a></td></tr></table><br></div> <p><a name="s0ss0"></a></p> <h3>D. Semilinear expressions</h3> <p><a name="s1ss0"></a></p> <h4>D.1 Semilinear Sets</h4> <p>A <em>semilinear</em> set, is a finite union of <em>linear</em> sets, i.e., of sets of the form a+b_1Bbb N+ cdots +b_pBbb N, with a, b_1, ..., b_pin Bbb N^n. We consider also sets of the form a+b_1Bbb Z+ cdots +b_pBbb Z, with a, b_1, ..., b_pin Bbb Z^n, i.e., cosets of subgroups of Bbb Z^n. We call them <em>Bbb Z-linear</em>. Finite unions of Bbb Z-linear sets are then called <em>Bbb Z-semilinear</em>. An expression of the form a+b_1N+ cdots +b_pN , with a, b_1, ..., b_pin Bbb N^n, is said to be a <em>linear expression</em>. Let us call n its <em>arity</em>, a its <em>base point</em> and b_1, ..., b_p its <em>vectors</em>. (Analogous definitions may be given for Bbb Z-linear sets.) Linear and Bbb Z-linear sets may be given using the functions that follow.</p> <p><a name="s1ss1"></a></p> <h5>D.1-1 NLinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NLinear</code>( <var>arity, base\_point, vectors</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Returns a linear set. The meaning of the arguments should already be clear.</p> <table class="example"> <tr><td><pre> gap> LN := NLinear(2,[0,1],[[1,2],[5,2]]); [ 0, 1 ] + [ 1, 2 ] N + [ 5, 2 ] N </pre></td></tr></table> <p><a name="s1ss2"></a></p> <h5>D.1-2 ZLinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ZLinear</code>( <var>arity, base\_point, vectors</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Returns a Bbb Z-linear set. The meaning of the arguments should already be clear.</p> <table class="example"> <tr><td><pre> gap> LZ := ZLinear(2,[0,1],[[1,2],[5,2]]); [ 0, 1 ] + [ 1, 2 ] Z + [ 0, 8 ] Z </pre></td></tr></table> <p>In the case of a Bbb Z-linear set the expression returned represents the same linear set than the expression given, but the vectors have changed: they are the nonzero rows of a matrix in Hermite Normal Form. Notice that a+b_1Bbb Z+ cdots +b_pBbb Z, with a, b_1, ..., b_pin Bbb Z^n, is a coset of the subgroup of Bbb Z^n generated by the vectors b_1, ..., b_pin Bbb Z^n. In general, when we give an expression for such a coset to \GAP\ an expression involving a basis for the subgroup consisting of the nonzero vectors of a matrix in HNF is returned.</p> <p><a name="s2ss0"></a></p> <h4>D.2 Operations with semilinear sets</h4> <p>We may compute expressions for the <code class="code">product</code>, <code class="code">union</code> and <code class="code">star</code> (i.e., submonoid generated by) of semilinear and Bbb Z-semilinear sets. In some cases, specially for Bbb Z-semilinear expressions, simpler expressions representing the same set are returned. Of course, these operations may be used to construct more complex expressions.</p> <p>For linear or semilinear expressions we have the following functions that return respectively semilinear expressions for the <code class="code">union</code> and <code class="code">sum</code> of the languages given by the semilinear expressions <code class="code">r</code> and <code class="code">s</code> and the <code class="code">star</code> of the language given by the semilinear expression <code class="code">r</code>.</p> <p><a name="s2ss1"></a></p> <h5>D.2-1 UnionNSemilinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UnionNSemilinear</code>( <var>r, s</var> )</td><td class="tdright">( function )</td></tr></table></div> <p><a name="s2ss2"></a></p> <h5>D.2-2 SumNSemilinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SumNSemilinear</code>( <var>r, s</var> )</td><td class="tdright">( function )</td></tr></table></div> <p><a name="s2ss3"></a></p> <h5>D.2-3 StarNSemilinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StarNSemilinear</code>( <var>r</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Some examples involving linear expressions:</p> <table class="example"> <tr><td><pre> gap> s1 := NLinear(2,[0,3],[[1,2],[5,2]]); [ 0, 3 ] + [ 1, 2 ] N + [ 5, 2 ] N gap> s2 := NLinear(2,[1,1],[[3,2],[0,3]]); [ 1, 1 ] + [ 3, 2 ] N + [ 0, 3 ] N gap> UnionNSemilinear(s1,s2); [ [ 0, 3 ] + [ 1, 2 ] N + [ 5, 2 ] N , [ 1, 1 ] + [ 3, 2 ] N + [ 0, 3 ] N ] gap> StarNSemilinear(s1); [ [ 0, 0 ], [ 0, 3 ] + [ 0, 3 ] N + [ 1, 2 ] N + [ 5, 2 ] N ] gap> SumNSemilinear(s1,s2); [ [ 1, 4 ] + [ 0, 3 ] N + [ 1, 2 ] N + [ 3, 2 ] N + [ 5, 2 ] N ] </pre></td></tr></table> <p>The analogous functions for Bbb Z-linear and Bbb Z-semilinear expressions follow:</p> <p><a name="s2ss4"></a></p> <h5>D.2-4 UnionZSemilinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UnionZSemilinear</code>( <var>r, s</var> )</td><td class="tdright">( function )</td></tr></table></div> <p><a name="s2ss5"></a></p> <h5>D.2-5 SumZSemilinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SumZSemilinear</code>( <var>r, s</var> )</td><td class="tdright">( function )</td></tr></table></div> <p><a name="s2ss6"></a></p> <h5>D.2-6 StarZSemilinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StarZSemilinear</code>( <var>r</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Now, some examples involving Bbb Z-linear expressions</p> <table class="example"> <tr><td><pre> gap> z1 := ZLinear(2,[0,3],[[1,2],[5,2]]); [ 0, 3 ] + [ 1, 2 ] Z + [ 0, 8 ] Z gap> z2 := ZLinear(2,[1,1],[[3,2],[0,3]]); [ 1, 1 ] + [ 3, 2 ] Z + [ 0, 3 ] Z gap> UnionZSemilinear(z1,z2); [ [ 0, 3 ] + [ 1, 2 ] Z + [ 0, 8 ] Z , [ 1, 1 ] + [ 3, 2 ] Z + [ 0, 3 ] Z ] gap> SumZSemilinear(z1,z2); [ [ 0, 0 ] + [ 1, 0 ] Z + [ 0, 1 ] Z ] gap> StarZSemilinear(z2); [ [ 0, 0 ] + [ 1, 0 ] Z + [ 0, 1 ] Z ] </pre></td></tr></table> <p>Let S be a subgroup of Bbb Z^n. An element xin Bbb Z^n belongs to a Bbb Z-semilinear set z+S if and only if the subgroup generated by x-z and S is equal to S. This test may be done computing basis for the subgroups < x-z,S> and S consisting of the nonzero vectors of a matrix in HNF and testing their equality. Recall that an integer matrix B is row equivalent over Bbb Z to a unique matrix A in Hermite normal form. (See, for example, <a href="chapBib.html#biBSims:94">[S94]</a> .)</p> <p><a name="s2ss7"></a></p> <h5>D.2-7 BelongsZLinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BelongsZLinear</code>( <var>x, L</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Tests if <var>x</var> belongs to the Bbb Z-linear set <var>L</var></p> <table class="example"> <tr><td><pre> gap> BelongsZLinear([5,27],z2); false </pre></td></tr></table> <p><a name="s2ss8"></a></p> <h5>D.2-8 BelongsZSemilinear</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> BelongsZSemilinear</code>( <var>x, L</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Tests if <var>x</var> belongs to the Bbb Z-semilinear set <var>L</var></p> <table class="example"> <tr><td><pre> gap> BelongsZSemilinear([5,29],UnionZSemilinear(z1,z2)); true </pre></td></tr></table> <div class="pcenter"> <table class="chlink"><tr><td><a href="chap0.html">Top of Book</a></td><td><a href="chapC.html">Previous Chapter</a></td><td><a href="chapE.html">Next Chapter</a></td></tr></table> <br> <div class="pcenter"><table class="chlink"><tr><td class="chlink1">Goto Chapter: </td><td><a href="chap0.html">Top</a></td><td><a href="chap1.html">1</a></td><td><a href="chap2.html">2</a></td><td><a href="chap3.html">3</a></td><td><a href="chap4.html">4</a></td><td><a href="chap5.html">5</a></td><td><a href="chapA.html">A</a></td><td><a href="chapB.html">B</a></td><td><a href="chapBib.html">Bib</a></td><td><a href="chapC.html">C</a></td><td><a href="chapD.html">D</a></td><td><a href="chapE.html">E</a></td><td><a href="chapInd.html">Ind</a></td></tr></table><br></div> </div> <hr> <p class="foot">generated by GAPDoc2HTML</p> </body> </html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
850
