<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html><head> <title>GAP (AutMan) - Chapter 9: Stallings foldings</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="chap6.html">6</a></td><td><a href="chap7.html">7</a></td><td><a href="chap8.html">8</a></td><td><a href="chap9.html">9</a></td><td><a href="chapBib.html">Bib</a></td><td><a href="chapInd.html">Ind</a></td></tr></table><br></div> <p><a name="s0ss0"></a></p> <h3>9. Stallings foldings</h3> <p><a name="s1ss0"></a></p> <h4>9.1 Some theory</h4> <p><a name="s2ss0"></a></p> <h4>9.2 Foldings</h4> <p>A finitely generated subgroup of a finitely generated free group is given through a list whose first element is the number of generators of the free group and the remaining elements are the generators of the subgroup.</p> <p>A generator of the subgroup may be given through a string of letters or through a list of positive integers as decribed in what follows.</p> <p>When the free group has n generators, the n+j^th letter of the alphabet should be used to represent the formal inverse of the j^th generator which is represented by the j^th letter. The number of generators of the free group must not exceed 7.</p> <p>For example, <code class="code">[2,"abc","bbabcd"]</code> means the subgroup of the free group on 2 generators generated by aba^-1 and bbaba^-1b^-1. The same subgroup may be given as <code class="code">[2,[1,2,3],[2,2,1,2,3,4]]</code></p> <p><a name="s2ss1"></a></p> <h5>9.2-1 FlowerAutomaton</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FlowerAutomaton</code>( <var>L</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>The argument <code class="code">L</code> is a subgroup of the free group given through any of the representations described above.</p> <p><a name="s2ss2"></a></p> <h5>9.2-2 FoldFlowerAutomaton</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FoldFlowerAutomaton</code>( <var>A</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Makes identifications on the flower automaton <code class="code">A</code></p> <div class="pcenter"> <table class="chlink"><tr><td><a href="chap0.html">Top of Book</a></td><td><a href="chap8.html">Previous Chapter</a></td><td><a href="chapBib.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="chap6.html">6</a></td><td><a href="chap7.html">7</a></td><td><a href="chap8.html">8</a></td><td><a href="chap9.html">9</a></td><td><a href="chapBib.html">Bib</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>