<?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>
<title>GAP (IdRel) - Chapter 3: Logged Rewriting Systems</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" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap2.html">Previous Chapter</a> <a href="chap4.html">Next Chapter</a> </div>
<p><a id="X7B8D727485966AF8" name="X7B8D727485966AF8"></a></p>
<div class="ChapSects"><a href="chap3.html#X7B8D727485966AF8">3 <span class="Heading">Logged Rewriting Systems</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X797732E87F1FE197">3.1 <span class="Heading">Logged Knuth-Bendix Completion</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X80075D5180A8F1A5">3.1-1 LoggedOnePassKB</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X87D1E3A578AAAFCB">3.1-2 LoggedKnuthBendix</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X831A93087918AA5D">3.2 <span class="Heading">Logged reduction of a word</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7C5094AF784A8BA7">3.2-1 LoggedReduceWordKB</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8652CEEF7802DA46">3.2-2 LoggedRewritingSystemFpGroup</a></span>
</div>
</div>
<h3>3 <span class="Heading">Logged Rewriting Systems</span></h3>
<p>A logged rewrite system is associated with a group presentation. Each logged rewrite rule contains, in addition to the standard rewrite rule, a record or log component which express the rule in terms of the original relators of the group. Here a logged rewrite rule is represented by a triple <code class="code">[ u, [L1,L2,..,Lk], v]</code>, where <code class="code">[u,v]</code> is a rewrite rule and L_i = [n_i,w_i] where n_i is a group relator and w_i is a word. These three components obey the identity u = n_1^w_1 ... n_k^w_k v.</p>
<p>Rules of the form g^+g^- are relevant to the monoid presentation, but not to the group presentation, so are not included in the logging.</p>
<p><a id="X797732E87F1FE197" name="X797732E87F1FE197"></a></p>
<h4>3.1 <span class="Heading">Logged Knuth-Bendix Completion</span></h4>
<p>The functions in this section are the logged versions of those in the previous chapter.</p>
<p><a id="X80075D5180A8F1A5" name="X80075D5180A8F1A5"></a></p>
<h5>3.1-1 LoggedOnePassKB</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LoggedOnePassKB</code>( <var class="Arg">loggedrules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Given a logged rewrite system, this function finds all the rules that would be added to complete the rewrite system in <code class="code">OnePassKB</code>, and also the logs which relate the new rules to the originals. The result of applying this function to loggedrules is to add new logged rules to the system without changing the monoid it defines.</p>
<p>In the example, we first convert the presentation for <code class="code">q8</code> into an initial set of logged rules, and then apply one pass of Knuth-Bendix.</p>
<table class="example">
<tr><td><pre>
gap> l0 := ListWithIdenticalEntries( 8, 0 );;
gap> for j in [1..8] do
r := r0[j];
if ( j<5 ) then
l0[j] := [ r[1], [ [j,id] ], r[2] ];
else
l0[j] := [ r[1], [ ], r[2] ];
fi;
od;
gap> l0;
[ [ q8_M1^4, [ [ 1, <identity ...>] ], <identity. ..> ],
[ q8_M2^4, [ [ 2, <identity ...>] ], <identity ...> ],
[ q8_M1*q8_M2*q8_M1*q8_M4, [ [ 3, <identity ...> ] ], <identity ...> ],
[ q8_M1^2*q8_M2^2, [ [ 4, <identity ...> ] ], <identity ...> ],
[ q8_M1*q8_M3, [ ], <identity ...> ], [ q8_M2*q8_M4, [ ], <identity ...> ],
[ q8_M3*q8_M1, [ ], <identity ...> ], [ q8_M4*q8_M2, [ ], <identity ...> ] ]
gap> l1 := LoggedOnePassKB( l0 );;
gap> Length( l1 );
</pre></td></tr></table>
<p><a id="X87D1E3A578AAAFCB" name="X87D1E3A578AAAFCB"></a></p>
<h5>3.1-2 LoggedKnuthBendix</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LoggedKnuthBendix</code>( <var class="Arg">loggedrules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LoggedRewriteReduce</code>( <var class="Arg">loggedrules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>The function <code class="code">LoggedRewriteReduce</code> removes unnecessary rules from a logged rewrite system. It works on the same principle as <code class="code">RewriteReduce</code>.</p>
<p>The function <code class="code">LoggedKnuthBendix</code> repeatedly applies <code class="code">LoggedOnePassKB</code> and <code class="code">LoggedRewriteReduce</code> until no new rules are added and no unnecessary ones are included. The output is a reduced complete logged rewrite system.</p>
<table class="example">
<tr><td><pre>
gap> l1 := LoggedRewriteReduce( l1 );
[ [ q8_M1*q8_M3, [ ], <identity ...> ],
[ q8_M2^2, [ [ -4, <identity ...> ], [ 2, q8_M1^-2 ] ], q8_M1^2 ],
[ q8_M2*q8_M4, [ ], <identity ...> ], [ q8_M3*q8_M1, [ ], <identity ...> ],
[ q8_M4*q8_M2, [ ], <identity ...> ],
[ q8_M1^3, [ [ 1, <identity. ..> ] ], q8_M3 ],
[ q8_M1^2*q8_M2, [ [ 4, <identity. ..> ] ], q8_M4 ],
[ q8_M1*q8_M2*q8_M1, [ [ 3, <identity ...> ] ], q8_M2 ],
[ q8_M2*q8_M1*q8_M4, [ [ 3, q8_M3^-1 ] ], q8_M3] ]
gap> l2 := LoggedKnuthBendix( l1 );
[ [ q8_M1*q8_M3, [ ], <identity ...> ],
[ q8_M2*q8_M1, [ [ 3, q8_M3^-1 ], [-1, <identity. ..> ], [ 4, q8_M1^-1 ] ],
q8_M1*q8_M4 ],
[ q8_M2^2, [ [ -4, <identity ...> ], [2, q8_M1^-2] ], q8_M1^2 ],
[ q8_M2*q8_M3, [ [ -3, <identity ...> ] ], q8_M1*q8_M2 ],
[ q8_M2*q8_M4, [ ], <identity ...> ], [ q8_M3*q8_M1, [ ], <identity ...> ],
[ q8_M3*q8_M2, [ [ -1, <identity ...>], [4, q8_M1^-1 ] ], q8_M1*q8_M4 ],
[ q8_M3^2, [ [ -1, <identity ...>] ], q8_M1^2 ],
[ q8_M3*q8_M4, [ [ -1, <identity ...>], [ -2, q8_M1^-2],
[ 4, <identity ...> ], [ 3, q8_M3^-1*q8_M2^-1 ],
[ -3, <identity. ..> ] ], q8_M1*q8_M2 ],
[ q8_M4*q8_M1, [ [ -4, <identity ...> ], [ 3, q8_M1^-1 ] ], q8_M1*q8_M2 ],
[ q8_M4*q8_M2, [ ], <identity ...> ],
[ q8_M4*q8_M3, [ [ -3, q8_M3^-1*q8_M4^-1] ], q8_M1*q8_M4 ],
[ q8_M4^2, [ [ -4, <identity. ..> ] ], q8_M1^2 ],
[ q8_M1^3, [ [ 1, <identity ...> ] ], q8_M3 ],
[ q8_M1^2*q8_M2, [ [4, <identity. ..> ] ], q8_M4 ],
[ q8_M1^2*q8_M4, [ [ -4, q8_M1^-2], [ 1, <identity ...> ] ], q8_M2 ] ]
</pre></td></tr></table>
<p><a id="X831A93087918AA5D" name="X831A93087918AA5D"></a></p>
<h4>3.2 <span class="Heading">Logged reduction of a word</span></h4>
<p><a id="X7C5094AF784A8BA7" name="X7C5094AF784A8BA7"></a></p>
<h5>3.2-1 LoggedReduceWordKB</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LoggedReduceWordKB</code>( <var class="Arg">word, loggedrules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LoggedOnePassReduceWord</code>( <var class="Arg">word, loggedrules</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ShorterLoggedRule</code>( <var class="Arg">logrule1, logrule2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Given a word and a logged rewrite system, the function <code class="code">LoggedOnePassReduceWord</code> makes one reduction of the word (as in <code class="code">OnePassReduceWord</code>) and records this, using the log part of the rule used and the position in the original word of the replaced part.</p>
<p>The function <code class="code">LoggedReduceWordKB</code> repeatedly applies <code class="code">OnePassLoggedReduceWord</code> until the word can no longer be reduced. Each step of the reduction is logged, showing how the original word can be expressed in terms of the original relators and the irreducible word. When <code class="code">loggedrules</code> is complete the reduced word is a unique normal form for that group element. The log of the reduction depends on the order in which the rules are applied.</p>
<p>The function <code class="code">ShorterLoggedrule</code> decides whether one logged rule is better than another, using the same criteria as <code class="code">ShorterRule</code>. In the example we perform logged reductions of <code class="code">w0</code> corresponding to the ordinary reductions performed in the previous chapter.</p>
<table class="example">
<tr><td><pre>
gap> w0;
q8_M2^9*q8_M1^9
gap> lw1 := LoggedOnePassReduceWord( w0, l0 );
[ [ [ 1, q8_M2^-9 ], [ 2, <identity ...> ] ], q8_M2^5*q8_M1^5 ]
gap> lw2 := LoggedReduceWordKB( w0, l0 );
[ [ [ 1, q8_M2^-9 ], [ 2, <identity ...> ], [ 1, q8_M2^-5 ],
[ 2, <identity ...> ] ], q8_M2*q8_M1 ]
gap> lw2 := LoggedReduceWordKB( w0, l2 );
[ [ [ 3, q8_M3^-1*q8_M2^-8 ], [ -1, q8_M2^-8 ], [ 4, q8_M1^-1*q8_M2^-8 ],
[ -4, <identity ...> ], [ 2, q8_M1^-2 ],
[ -4, q8_M1^-1*q8_M2^-6*q8_M1^-2 ], [ 3, q8_M1^-2*q8_M2^-6*q8_M1^-2 ],
[ 1, q8_M2^-1*q8_M1^-2*q8_M2^-6*q8_M1^-2 ], [ 4, <identity ...> ],
[ 3, q8_M3^-1*q8_M2^-4*q8_M4^-1 ], [ -1, q8_M2^-4*q8_M4^-1 ],
[ 4, q8_M1^-1*q8_M2^-4*q8_M4^-1 ], [ -4, q8_M4^-1 ],
[ 2, q8_M1^-2*q8_M4^-1 ],
[ -3, q8_M1^-1*q8_M4^-1*q8_M1^-1*q8_M2^-2*q8_M1^-2*q8_M4^-1 ],
[ -4, <identity ...> ], [ 3, q8_M1^-1 ],
[ 1, q8_M2^-1*q8_M1^-2*q8_M4^-1*q8_M1^-1*q8_M2^-2*q8_M1^-1*q8_M2^
-1*q8_M1^-1 ],
[ 4, q8_M4^-1*q8_M1^-1*q8_M2^-2*q8_M1^-1*q8_M2^-1*q8_M1^-1 ],
[ 3, q8_M3^-1*q8_M1^-1 ], [ -1, q8_M1^-1 ], [ 4, q8_M1^-2 ],
[ -4, q8_M4^-1*q8_M1^-2 ], [ 2, q8_M1^-2*q8_M4^-1*q8_M1^-2 ],
[ -4, q8_M1^-2 ], [ 3, q8_M1^-3 ], [ -4, q8_M1^-2*q8_M2^-1*q8_M1^-3 ],
[ 1, <identity ...> ], [ 3, q8_M3^-2 ], [ -1, q8_M3^-1 ],
[ 4, q8_M1^-1*q8_M3^-1 ], [ -4, <identity ...> ], [ 3, q8_M1^-1 ],
[ 3, q8_M3^-1*q8_M1^-1 ], [ -1, q8_M1^-1 ], [ 4, q8_M1^-2 ],
[ -4, q8_M1^-2 ], [ 3, q8_M1^-3 ], [ 1, <identity ...> ],
[ -1, <identity ...> ], [ 4, q8_M1^-1 ] ], q8_M1*q8_M4 ]
</pre></td></tr></table>
<p><a id="X8652CEEF7802DA46" name="X8652CEEF7802DA46"></a></p>
<h5>3.2-2 LoggedRewritingSystemFpGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LoggedRewritingSystemFpGroup</code>( <var class="Arg">loggedrules</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Given a group presentation, the function <code class="code">LoggedRewritingSystemFpGroup</code> determines a logged rewrite system based on the relators. The initial logged rewrite system associated with a group presentation consists of two types of rule. These are logged versions of the two types of rule in the monoid presentation. For each relator <code class="code">rel</code> of the group there is a logged rule <code class="code">[ rel, [ [ 1, rel] ], id]</code>. For each inverse relator there is a logged rule <code class="code">[gen*inv, [], id ]</code>. It then attempts a completion of the logged rewrite system. The rules in the final system are partially ordered by the function <code class="code">ShorterLoggedRule</code>.</p>
<table class="example">
<tr><td><pre>
gap> LoggedRewritingSystemFpGroup( q8 );
[ [ q8_M4*q8_M2, [ ], <identity ...> ], [ q8_M3*q8_Ml, [ ], <identity ...> ],
[ q8_M2*q8_M4, [ ], <identity ...> ],
[ q8_Ml*q8_M3, [ ], <identity ...> ],
[ q8_Ml^2*q8_M4, [ [ -8, q8_Ml^-2 ], [ 5, <identity ...> ] ], q8_M2 ],
[ q8_Ml^2*q8_M2, [ [ 8, <identity ...> ] ], q8_M4 ],
[ q8_Ml^3, [ [ 5, <identity ...> ] ], q8_M3 ],
[ q8_M4^2, [ [ -8, <identity ...> ] ], q8_Ml^2 ],
[ q8_M4*q8_M3, [ [ -7, q8_M3^-1*q8_M4^-1 ] ], q8_Ml*q8_M4 ],
[ q8_M4*q8_Ml, [ [ -8, <identity. ..> ], [ 7, q8_Ml^-1 ] ], q8_Ml*q8_M2 ],
[ q8_M3*q8_M4,
[ [ -5, <identity ...>], [ -6, q8_Ml^-2 ], [ 8, <identity ...> ],
[ 7, q8_M3^-1*q8_M2^-1 ], [ -7, <identity. ..> ] ], q8_Ml*q8_M2 ],
[ q8_M3^2, [ [ -5, <identity ...>] ], q8_Ml^2 ],
[ q8_M3*q8_M2, [ [ -5, <identity. ..> ], [ 8, q8_Ml^-1 ] ], q8_Ml*q8_M4 ],
[ q8_M2*q8_M3, [ [ -7, <identity ...> ] ], q8_M1*q8_M2 ],
[ q8_M2^2, [ [ -a, <identity ...> ], [ 6, q8_M1^-2 ] ], q8_M1^2 ],
[ q8_M2*q8_M1, [ [ 7, q8_M3^-1 ], [ -5, <identity ...> ], [ a, q8_M1^-1 ] ],
q8_M1*q8_M4 ] ]
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap2.html">Previous Chapter</a> <a href="chap4.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
1916
