chap0.txt

  
  
                                  PatternClass 
  
  
                      A permutation pattern class package 
  
  
                                      2.3
  
  
                                   05/07/2017
  
  
                                 Ruth Hoffmann
  
                                  Steve Linton
  
                                 Michael Albert
  
  
  
  Ruth Hoffmann
      Email:    mailto:[email protected]
      Homepage: TODO
      Address:  TODO
  
  
  Steve Linton
      Email:    mailto:[email protected]
      Homepage: http://sal.host.cs.st-andrews.ac.uk/
      Address:  Steve Linton
                School of Computer Science,
                University of St. Andrews,
                North Haugh,
                St. Andrews,
                Fife,
                KY16 9SS,
                SCOTLAND
  
  
  Michael Albert
      Email:    mailto:[email protected]
      Homepage: http://www.cs.otago.ac.nz/staff/michael.html
      Address:  Michael Albert
                Department of Computer Science,
                University of Otago,
                PO Box 56,
                DUNEDIN 9054,
                New Zealand,
  
  
  
  -------------------------------------------------------
  
  
  Contents (PatternClass)
  
  1 Introduction
  2 Token Passing Networks
    2.1 Specific TPN
      2.1-1 Parstacks
      2.1-2 Seqstacks
      2.1-3 BufferAndStack
  3 Permutation Encoding
    3.1 Encoding and Decoding
      3.1-1 RankEncoding
      3.1-2 RankDecoding
      3.1-3 SequencesToRatExp
  4 From Networks to Automata
    4.1 Functions
      4.1-1 GraphToAut
      4.1-2 ConstrainedGraphToAut
  5 From Automata to Networks
    5.1 Functions
      5.1-1 IsStarClosed
      5.1-2 Is2StarReplaceable
      5.1-3 IsStratified
      5.1-4 IsPossibleGraphAut
  6 Pattern Classes
    6.1 Transducers
      6.1-1 Transducer
      6.1-2 DeletionTransducer
      6.1-3 TransposedTransducer
      6.1-4 InvolvementTransducer
      6.1-5 CombineAutTransducer
    6.2 From Class to Basis and vice versa
      6.2-1 BasisAutomaton
      6.2-2 ClassAutomaton
      6.2-3 BoundedClassAutomaton
      6.2-4 ClassAutFromBaseEncoding
      6.2-5 ClassAutFromBase
      6.2-6 ExpandAlphabet
    6.3 Direct Sum of Regular Classes
      6.3-1 ClassDirectSum
    6.4 Statistical Inspections
      6.4-1 Spectrum
      6.4-2 NumberAcceptedWords
      6.4-3 AutStateTransitionMatrix
      6.4-4 AcceptedWords
      6.4-5 AcceptedWordsR
  7 Some Permutation Essentials
    7.1 Complement
      7.1-1 PermComplement
    7.2 Rank Encoding
      7.2-1 IsRankEncoding
  8 Properties of Permutations
    8.1 Intervals in Permutations
      8.1-1 IsInterval
    8.2 Simplicity
      8.2-1 IsSimplePerm
    8.3 Point Deletion in Simple Permutations
      8.3-1 OnePointDelete
      8.3-2 TwoPointDelete
      8.3-3 PointDeletion
    8.4 Block-Decomposition
      8.4-1 Inflation
      8.4-2 BlockDecomposition
    8.5 Plus-Decomposability
      8.5-1 IsPlusDecomposable
    8.6 Minus-Decomposability
      8.6-1 IsMinusDecomposable
    8.7 Sums of Permutations
      8.7-1 PermDirectSum
      8.7-2 PermSkewSum
  9 Regular Languages of Sets of Permutations
    9.1 Inversions in Permutations
      9.1-1 InversionAut
      9.1-2 InversionAutOfClass
    9.2 Plus- and Minus-(In)Decomposablilty
      9.2-1 PlusDecomposableAut
      9.2-2 PlusIndecomposableAut
      9.2-3 MinusDecomposableAut
      9.2-4 MinusIndecomposableAut
    9.3 Language of all non-simple permutations
      9.3-1 LengthBoundAut
      9.3-2 ShiftAut
      9.3-3 NextGap
      9.3-4 GapAut
      9.3-5 SumAut
      9.3-6 GapSumAut
      9.3-7 NonSimpleAut
    9.4 Simplicity
      9.4-1 SimplePermAut
    9.5 Exceptionality
      9.5-1 IsExceptionalPerm
      9.5-2 ExceptionalBoundedAutomaton
  10 Miscellaneous functions
    10.1 Permutation Inclusion Set
      10.1-1 InbetweenPermAutomaton
      10.1-2 InbetweenPermSet
      10.1-3 IsSubPerm
    10.2 Automaton Manipulation
      10.2-1 LoopFreeAut
      10.2-2 LoopVertexFreeAut