Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/sgpviz/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 30.7.2024 mit Größe 15 kB image not shown  

Quelle  chap2_mj.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/sgpviz/doc/chap2_mj.html


<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (SgpViz) - Chapter 2: Basics</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap2"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap1_mj.html">[Previous Chapter]</a>    <a href="chap3_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap2.html">[MathJax off]</a></p>
<p><a id="X868F7BAB7AC2EEBC" name="X868F7BAB7AC2EEBC"></a></p>
<div class="ChapSects"><a href="chap2_mj.html#X868F7BAB7AC2EEBC">2 <span class="Heading">Basics</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X7A489A5D79DA9E5C">2.1 <span class="Heading">Examples </span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X85134313846D1A8A">2.2 <span class="Heading">Some attributes</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7F7FAED380682973">2.2-1 HasCommutingIdempotents</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X83F1529479D56665">2.2-2 IsInverseSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X78CA2A0D869C51DC">2.3 <span class="Heading">Some basic functions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7A65787A83C0F8EF">2.3-1 PartialTransformation</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7EEED52C7D38E1CA">2.3-2 ReduceNumberOfGenerators</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7BBEBEE885D05208">2.3-3 SemigroupFactorization</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7FB7633483A45209">2.3-4 GrahamBlocks</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X789D5E5A8558AA07">2.4 <span class="Heading">Cayley graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X822983CD7F01B5EA">2.4-1 RightCayleyGraphAsAutomaton</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X82F7D3E485D615D8">2.4-2 RightCayleyGraphMonoidAsAutomaton</a></span>
</div></div>
</div>

<h3>2 <span class="Heading">Basics</span></h3>

<p>We give some examples of semigroups to be used later. We also describe some basic functions that are not directly available from <strong class="pkg">GAP</strong>, but are useful for the purposes of this package.</p>

<p><a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a></p>

<h4>2.1 <span class="Heading">Examples </span></h4>

<p>These are some examples of semigroups that will be used through this manual</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeMonoid("a","b");</span>
<free monoid on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := GeneratorsOfMonoid( f )[ 1 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := GeneratorsOfMonoid( f )[ 2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">r:=[[a^3,a^2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[a^2*b,a^2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[b*a^2,a^2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[b^2,a^2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[a*b*a,a],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[b*a*b,b] ];</span>
[ [ a^3, a^2 ], [ a^2*b, a^2 ], [ b*a^2, a^2 ], [ b^2, a^2 ], [ a*b*a, a ], 
  [ b*a*b, b ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">b21:= f/r;</span>
<fp monoid on the generators [ a, b ]>
      </pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g0:=Transformation([4,1,2,4]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g1:=Transformation([1,3,4,4]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g2:=Transformation([2,4,3,4]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">poi3:= Monoid(g0,g1,g2);</span>
<monoid with 3 generators>
     </pre></div>

<p><a id="X85134313846D1A8A" name="X85134313846D1A8A"></a></p>

<h4>2.2 <span class="Heading">Some attributes</span></h4>

<p>These functions are semigroup attributes that get stored once computed.</p>

<p><a id="X7F7FAED380682973" name="X7F7FAED380682973"></a></p>

<h5>2.2-1 HasCommutingIdempotents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HasCommutingIdempotents</code>( <var class="Arg">M</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Tests whether the idempotents of the semigroup <var class="Arg">M </var>commute.</p>

<p><a id="X83F1529479D56665" name="X83F1529479D56665"></a></p>

<h5>2.2-2 IsInverseSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsInverseSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Tests whether a finite semigroup <var class="Arg">S </var>is inverse. It is well-known that it suffices to test whether the idempotents of <var class="Arg">S </var>commute and <var class="Arg">S </var>is regular. The function <code class="code">IsRegularSemigroup </code>is part of <strong class="pkg">GAP</strong>.</p>

<p><a id="X78CA2A0D869C51DC" name="X78CA2A0D869C51DC"></a></p>

<h4>2.3 <span class="Heading">Some basic functions</span></h4>

<p><a id="X7A65787A83C0F8EF" name="X7A65787A83C0F8EF"></a></p>

<h5>2.3-1 PartialTransformation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PartialTransformation</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>A partial transformation is a partial function of a set of integers of the form <span class="SimpleMath">\(\{1,\dots, n\}\)</span>. It is given by means of the list of images <var class="Arg">L</var>. When an element has no image, we write 0. Returns a full transformation on a set with one more element that acts like a zero.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PartialTransformation([2,0,4,0]);</span>
Transformation( [ 2, 5, 4, 5, 5 ] )
      </pre></div>

<p><a id="X7EEED52C7D38E1CA" name="X7EEED52C7D38E1CA"></a></p>

<h5>2.3-2 ReduceNumberOfGenerators</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReduceNumberOfGenerators</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Given a subset <var class="Arg">L</var> of the generators of a semigroup, returns a list of generators of the same semigroup but possibly with less elements than <var class="Arg">L</var>.</p>

<p><a id="X7BBEBEE885D05208" name="X7BBEBEE885D05208"></a></p>

<h5>2.3-3 SemigroupFactorization</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SemigroupFactorization</code>( <var class="Arg">S</var>, <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">L</var> is an element (or list of elements) of the semigroup <var class="Arg">S</var>. Returns a minimal factorization on the generators of <var class="Arg">S</var> of the element(s) of <var class="Arg">L</var>. Works only for transformation semigroups.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">el1 := Transformation( [ 2, 3, 4, 4 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">el2 := Transformation( [ 2, 4, 3, 4 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f1 := SemigroupFactorization(poi3,el1);</span>
[ [ Transformation( [ 1, 3, 4, 4 ] ), Transformation( [ 2, 4, 3, 4 ] ) ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">f1[1][1] * f1[1][2] = el1;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">SemigroupFactorization(poi3,[el1,el2]);</span>
[ [ Transformation( [ 1, 3, 4, 4 ] ), Transformation( [ 2, 4, 3, 4 ] ) ],
  [ Transformation( [ 2, 4, 3, 4 ] ) ] ]
</pre></div>

<p><a id="X7FB7633483A45209" name="X7FB7633483A45209"></a></p>

<h5>2.3-4 GrahamBlocks</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GrahamBlocks</code>( <var class="Arg">mat</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">mat</var> is a matrix as displayed by <code class="code">DisplayEggBoxOfDClass(D);</code> of a regular D-class <code class="code">D</code>. This function outputs a list <code class="code">[gmat, phi]</code> where <code class="code">gmat</code> is <var class="Arg">mat</var> in Graham's blocks form and phi maps H-classes of gmat to the corresponding ones of mat, i.e., phi[i][j] = [i',j'] where mat[i'][j'] = gmat[i][j]. If the argument to this function is not a matrix corresponding to a regular D-class, the function may abort in error.




<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := PartialTransformation([6,2,0,0,2,6,0,0,10,10,0,0]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := PartialTransformation([0,0,1,5,0,0,5,9,0,0,9,1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p3 := PartialTransformation([0,0,3,3,0,0,7,7,0,0,11,11]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p4 := PartialTransformation([4,4,0,0,8,8,0,0,12,12,0,0]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">css3:=Semigroup(p1,p2,p3,p4);</span>
<transformation semigroup of degree 13 with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">el := Elements(css3)[8];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := GreensDClassOfElement(css3, el);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRegularDClass(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayEggBoxOfDClass(D);</span>
[ [  1,  1,  0,  0 ],
  [  1,  1,  0,  0 ],
  [  0,  0,  1,  1 ],
  [  0,  0,  1,  1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := [ [  1,  0,  1,  0 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">  [  0,  1,  0,  1 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">  [  0,  1,  0,  1 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">  [  1,  0,  1,  0 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">res := GrahamBlocks(mat);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintArray(res[1]);</span>
[ [  1,  1,  0,  0 ],
  [  1,  1,  0,  0 ],
  [  0,  0,  1,  1 ],
  [  0,  0,  1,  1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintArray(res[2]);</span>
[ [  [ 1, 1 ],  [ 1, 3 ],  [ 1, 2 ],  [ 1, 4 ] ],
  [  [ 4, 1 ],  [ 4, 3 ],  [ 4, 2 ],  [ 4, 4 ] ],
  [  [ 2, 1 ],  [ 2, 3 ],  [ 2, 2 ],  [ 2, 4 ] ],
  [  [ 3, 1 ],  [ 3, 3 ],  [ 3, 2 ],  [ 3, 4 ] ] ]
</pre></div>

<p><a id="X789D5E5A8558AA07" name="X789D5E5A8558AA07"></a></p>

<h4>2.4 <span class="Heading">Cayley graphs</span></h4>

<p><a id="X822983CD7F01B5EA" name="X822983CD7F01B5EA"></a></p>

<h5>2.4-1 RightCayleyGraphAsAutomaton</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightCayleyGraphAsAutomaton</code>( <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Computes the right Cayley graph of a finite monoid or semigroup <var class="Arg">S</var>. It uses the <strong class="pkg">GAP</strong> buit-in function <code class="code">CayleyGraphSemigroup</code> to compute the Cayley Graph and returns it as an automaton without initial nor final states. (In this automaton state <code class="code">i</code> represents the element <code class="code">Elements(S)[i]</code>.) The <strong class="pkg">Automata</strong> package is used to this effect.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">rcg := RightCayleyGraphAsAutomaton(b21);</span>
< deterministic automaton on 2 letters with 6 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(rcg);</span>
   |  1  2  3  4  5  6
-----------------------
 a |  2  4  6  4  2  4
 b |  3  5  4  4  4  3
Initial state:   [ ]
Accepting state: [ ]
      </pre></div>

<p><a id="X82F7D3E485D615D8" name="X82F7D3E485D615D8"></a></p>

<h5>2.4-2 RightCayleyGraphMonoidAsAutomaton</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightCayleyGraphMonoidAsAutomaton</code>( <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function is a synonym of <code class="func">RightCayleyGraphAsAutomaton</code> (<a href="chap2_mj.html#X822983CD7F01B5EA"><span class="RefLink">2.4-1</span></a>).</p>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap1_mj.html">[Previous Chapter]</a>    <a href="chap3_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>

99%


¤ Dauer der Verarbeitung: 0.19 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.