Quelle  chap0.html   Sprache: 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>
<title>GAP (PatternClass) - Contents</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="chap0"  onload="jscontent()">


<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="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</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="chap0.html#contents">[Contents]</a>    <a href="chap1.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap0_mj.html">[MathJax on]</a></p>
<p><a id="X7D2C85EC87DD46E5" name="X7D2C85EC87DD46E5"></a></p>
<div class="pcenter">

<h1>PatternClass</h1>


<h2>A permutation pattern class package</h2>

<p>
    2.4.5</p>

<p>
    30 August 2024
  </p>

</div>
<p><b>
    Ruth Hoffmann




  </b>
<br />Email: <span class="URL"><a href="mailto:rh347@st-andrews.ac.uk">rh347@st-andrews.ac.uk</a></span>
<br />Homepage: <span class="URL"><a href="https://www.st-andrews.ac.uk/computer-science/people/rh347/">https://www.st-andrews.ac.uk/computer-science/people/rh347/</a></span>
<br />Address: <br />School of Computer Science,<br /> University of St. Andrews,<br /> North Haugh,<br /> St. Andrews,<br /> Fife,<br /> KY16 9SS,<br /> SCOTLAND<br />
</p><p><b>
    Steve Linton




  </b>
<br />Email: <span class="URL"><a href="mailto:sl4@st-andrews.ac.uk">sl4@st-andrews.ac.uk</a></span>
<br />Homepage: <span class="URL"><a href="http://sal.host.cs.st-andrews.ac.uk/">http://sal.host.cs.st-andrews.ac.uk/</a></span>
<br />Address: <br />Steve Linton<br /> School of Computer Science,<br /> University of St. Andrews,<br /> North Haugh,<br /> St. Andrews,<br /> Fife,<br /> KY16 9SS,<br /> SCOTLAND<br />
</p><p><b>
    Michael Albert




  </b>
<br />Email: <span class="URL"><a href="mailto:malbert@cs.otago.ac.nz">malbert@cs.otago.ac.nz</a></span>
<br />Homepage: <span class="URL"><a href="https://www.otago.ac.nz/computer-science/people/Michael_Albert.html">https://www.otago.ac.nz/computer-science/people/Michael_Albert.html</a></span>
<br />Address: <br />Michael Albert<br /> Department of Computer Science,<br /> University of Otago,<br /> PO Box 56,<br /> DUNEDIN 9054,<br /> New Zealand,<br />
</p>

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

<div class="contents">
<h3>Contents<a id="contents" name="contents"></a></h3>

<div class="ContChap"><a href="chap1.html#X7DFB63A97E67C0A1">1 <span class="Heading">Introduction</span></a>
</div>
<div class="ContChap"><a href="chap2.html#X7C769071875E96B2">2 <span class="Heading">Token Passing Networks</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X80EE110279808BD3">2.1 <span class="Heading"> Specific TPN </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X85AFF5537F917AEB">2.1-1 Parstacks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7D6D07D980634845">2.1-2 Seqstacks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X81E3656E85CB6EB7">2.1-3 BufferAndStack</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap3.html#X8696E21E80C1AEC1">3 <span class="Heading">Permutation Encoding</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X793F8BF48048365F">3.1 <span class="Heading"> Encoding and Decoding </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8143AF3D79F4CC1D">3.1-1 RankEncoding</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7DA97A7B7C8EB18A">3.1-2 RankDecoding</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X832A1FEC7E5491EA">3.1-3 SequencesToRatExp</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap4.html#X84E9957A81BF938D">4 <span class="Heading">From Networks to Automata</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X86FA580F8055B274">4.1 <span class="Heading">Functions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7CFD21C47E43D8FF">4.1-1 GraphToAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7D457B517F2FDDA9">4.1-2 ConstrainedGraphToAut</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap5.html#X78223796785BC628">5 <span class="Heading">From Automata to Networks</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X86FA580F8055B274">5.1 <span class="Heading">Functions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X7E1DAEB979824B68">5.1-1 IsStarClosed</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X873324D67DC9DC41">5.1-2 Is2StarReplaceable</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X7FF528F784C9020B">5.1-3 IsStratified</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X7C3B9EB080F72043">5.1-4 IsPossibleGraphAut</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap6.html#X85A198CB7EBA4BDE">6 <span class="Heading">Pattern Classes</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X843CB33182B8E477">6.1 <span class="Heading">Transducers</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7A2DA7017E4F6BC4">6.1-1 Transducer</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7EB2EA8C78DA1F74">6.1-2 DeletionTransducer</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X85711F837F30E225">6.1-3 TransposedTransducer</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7BBBA46E84BDD089">6.1-4 InvolvementTransducer</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7E41CAC57CE71CB1">6.1-5 CombineAutTransducer</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7CFEC6DB7CA880CC">6.2 <span class="Heading">From Class to Basis and vice versa</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7FD8B2357CAAFC0B">6.2-1 BasisAutomaton</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X78BD24D7828004E8">6.2-2 ClassAutomaton</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X856A6F5085BAA7C3">6.2-3 BoundedClassAutomaton</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X82D67FC587793580">6.2-4 ClassAutFromBaseEncoding</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X80CBBEE08239B1B1">6.2-5 ClassAutFromBase</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X877C8457804E4B45">6.2-6 ExpandAlphabet</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X8218BF7787571EE0">6.3 <span class="Heading">Direct Sum of Regular Classes</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7DC869E27CC3BFE0">6.3-1 ClassDirectSum</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X80F7EB16817DDB99">6.4 <span class="Heading">Statistical Inspections</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X82004197784C17F8">6.4-1 Spectrum</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7E07D0B882DD9033">6.4-2 NumberAcceptedWords</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7BAE229C84A45841">6.4-3 AutStateTransitionMatrix</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7DF05204860111D5">6.4-4 AcceptedWords</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7C80854A872A5665">6.4-5 AcceptedWordsR</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap7.html#X81DB657E7FEF0295">7 <span class="Heading">Some Permutation Essentials</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X80E3E5BB8156C6A1">7.1 <span class="Heading"> Complement </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X820405DB787A5D32">7.1-1 PermComplement</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X8453836D83A63E54">7.2 <span class="Heading"> Rank Encoding </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7F1000E882050AFF">7.2-1 IsRankEncoding</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap8.html#X87A0210C7BCFBA99">8 <span class="Heading">Properties of Permutations </span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X85B2BC647868C9C4">8.1 <span class="Heading"> Intervals in Permutations </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X78D28CDF87CF35E4">8.1-1 IsInterval</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X7B82346E7E2C330C">8.2 <span class="Heading"> Simplicity </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X7ECAD3E4818C589D">8.2-1 IsSimplePerm</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X7A6836EC7E9CE3D8">8.3 <span class="Heading"> Point Deletion in Simple Permutations </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X877D962E7FBFB47E">8.3-1 OnePointDelete</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X787F62137E709A2C">8.3-2 TwoPointDelete</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X8696CBE580B27FE5">8.3-3 PointDeletion</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X87EB37927F40662B">8.4 <span class="Heading"> Block-Decomposition </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X8279728778F1F299">8.4-1 Inflation</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X7C07BE268055FEBD">8.4-2 BlockDecomposition</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X8278DD0F7F128656">8.5 <span class="Heading"> Plus-Decomposability </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X80CBC61C851B1D20">8.5-1 IsPlusDecomposable</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X801EF8FB79F18910">8.6 <span class="Heading"> Minus-Decomposability </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X87A6DF207B27C676">8.6-1 IsMinusDecomposable</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap8.html#X7B7C59AA84E3425C">8.7 <span class="Heading"> Sums of Permutations </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X7E0DD72F7F6E0440">8.7-1 PermDirectSum</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap8.html#X7CE8A32A78A4A6BB">8.7-2 PermSkewSum</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap9.html#X7E9C84807FCB6408">9 <span class="Heading"> Regular Languages of Sets of Permutations </span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9.html#X82F103DB7A446E7B">9.1 <span class="Heading"> Inversions in Permutations </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X79B3989A7D90B227">9.1-1 InversionAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X7C6166407D4A1798">9.1-2 InversionAutOfClass</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9.html#X8603B5A3872690FD">9.2 <span class="Heading"> Plus- and Minus-(In)Decomposablilty </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X7B43561F78C4C03C">9.2-1 PlusDecomposableAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X780030727DF57B1C">9.2-2 PlusIndecomposableAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X80F5A8AC8306FEE2">9.2-3 MinusDecomposableAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X8689DB147A7EE2C1">9.2-4 MinusIndecomposableAut</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9.html#X80E741077DE09F63">9.3 <span class="Heading"> Language of all non-simple permutations </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X7EE214F57A6350E0">9.3-1 LengthBoundAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X7B11C3137DEA8B4B">9.3-2 ShiftAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X864D53717A30C8EE">9.3-3 NextGap</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X7A660F527E913DB6">9.3-4 GapAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X809340BA7C999E86">9.3-5 SumAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X83BD683B7A92D492">9.3-6 GapSumAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X867C42167E943F94">9.3-7 NonSimpleAut</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9.html#X7B82346E7E2C330C">9.4 <span class="Heading"> Simplicity </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X7C7F3B6680370860">9.4-1 SimplePermAut</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9.html#X82CA692F808FA08F">9.5 <span class="Heading">Exceptionality</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X820901F881D220EE">9.5-1 IsExceptionalPerm</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9.html#X7B0086217E986ADA">9.5-2 ExceptionalBoundedAutomaton</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap10.html#X8308D685809A4E2F">10 <span class="Heading"> Miscellaneous functions </span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap10.html#X81D407EF82C4B194">10.1 <span class="Heading"> Permutation Inclusion Set </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap10.html#X7E83DB497CCB5CDC">10.1-1 InbetweenPermAutomaton</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap10.html#X7A07B52779B59271">10.1-2 InbetweenPermSet</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap10.html#X876ABC5F7822D768">10.1-3 IsSubPerm</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap10.html#X7A2B46957AB49125">10.2 <span class="Heading"> Automaton Manipulation </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap10.html#X85793D54837E38D5">10.2-1 LoopFreeAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap10.html#X8503A7707FA666C4">10.2-2 LoopVertexFreeAut</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chapBib.html"><span class="Heading">References</span></a></div>
<div class="ContChap"><a href="chapInd.html"><span class="Heading">Index</span></a></div>
<br />
</div>

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap1.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="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.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>