| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/patternclass/doc/ (GAP Algebra Version 4.15.1©) Datei vom 30.7.2024 mit Größe 108 kB |
|
Impressum PatternClass.tex Sprache: Latech |
|
|
% generated by GAPDoc2LaTeX from XML source (Frank Luebeck) \documentclass[a4paper,11pt]{report} \usepackage{graphicx} \usepackage{float} \usepackage[top=37mm,bottom=37mm,left=27mm,right=27mm]{geometry} \sloppy \pagestyle{myheadings} \usepackage{amssymb} \usepackage[utf8]{inputenc} \usepackage{makeidx} \makeindex \usepackage{color} \definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083} \definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179} \definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894} \definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894} \definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000} \definecolor{Black}{rgb}{0.0,0.0,0.0} \definecolor{linkColor}{rgb}{0.0,0.0,0.554} \definecolor{citeColor}{rgb}{0.0,0.0,0.554} \definecolor{fileColor}{rgb}{0.0,0.0,0.554} \definecolor{urlColor}{rgb}{0.0,0.0,0.554} \definecolor{promptColor}{rgb}{0.0,0.0,0.589} \definecolor{brkpromptColor}{rgb}{0.589,0.0,0.0} \definecolor{gapinputColor}{rgb}{0.589,0.0,0.0} \definecolor{gapoutputColor}{rgb}{0.0,0.0,0.0} %% for a long time these were red and blue by default, %% now black, but keep variables to overwrite \definecolor{FuncColor}{rgb}{0.0,0.0,0.0} %% strange name because of pdflatex bug: \definecolor{Chapter }{rgb}{0.0,0.0,0.0} \definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064} \usepackage{fancyvrb} \usepackage{mathptmx,helvet} \usepackage[T1]{fontenc} \usepackage{textcomp} \usepackage[ pdftex=true, bookmarks=true, a4paper=true, pdftitle={Written with GAPDoc}, pdfcreator={LaTeX with hyperref package / GAPDoc}, colorlinks=true, backref=page, breaklinks=true, linkcolor=linkColor, citecolor=citeColor, filecolor=fileColor, urlcolor=urlColor, pdfpagemode={UseNone}, ]{hyperref} \newcommand{\maintitlesize}{\fontsize{50}{55}\selectfont} % write page numbers to a .pnr log file for online help \newwrite\pagenrlog \immediate\openout\pagenrlog =\jobname.pnr \immediate\write\pagenrlog{PAGENRS := [} \newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}} %% were never documented, give conflicts with some additional packages \newcommand{\GAP}{\textsf{GAP}} %% nicer description environments, allows long labels \usepackage{enumitem} \setdescription{style=nextline} %% depth of toc \setcounter{tocdepth}{1} %% command for ColorPrompt style examples \newcommand{\gapprompt}[1]{\color{promptColor}{\bfseries #1}} \newcommand{\gapbrkprompt}[1]{\color{brkpromptColor}{\bfseries #1}} \newcommand{\gapinput}[1]{\color{gapinputColor}{#1}} \begin{document} \logpage{[ 0, 0, 0 ]} \begin{titlepage} \mbox{}\vfill \begin{center}{\maintitlesize \textbf{ PatternClass \mbox{}}}\\ \vfill \hypersetup{pdftitle= PatternClass } \markright{\scriptsize \mbox{}\hfill PatternClass \hfill\mbox{}} {\Huge \textbf{ A permutation pattern class package \mbox{}}}\\ \vfill {\Huge 2.4.5 \mbox{}}\\[1cm] { 30 August 2024 \mbox{}}\\[1cm] \mbox{}\\[2cm] {\Large \textbf{ Ruth Hoffmann\\ \mbox{}}}\\ {\Large \textbf{ Steve Linton\\ \mbox{}}}\\ {\Large \textbf{ Michael Albert\\ \mbox{}}}\\ \hypersetup{pdfauthor= Ruth Hoffmann\\ ; Steve Linton\\ ; Michael Albert\\ } \end{center}\vfill \mbox{}\\ {\mbox{}\\ \small \noindent \textbf{ Ruth Hoffmann\\ } Email: \href{mailto://rh347@st-andrews.ac.uk} {\texttt{rh347@st\texttt{\symbol{45 Homepage: \href{https://www.st-andrews.ac.uk/computer-science/people/rh347/} {\tex Address: \begin{minipage}[t]{8cm}\noindent School of Computer Science,\\ University of St. Andrews,\\ North Haugh,\\ St. Andrews,\\ Fife,\\ KY16 9SS,\\ SCOTLAND\\ \end{minipage} }\\ {\mbox{}\\ \small \noindent \textbf{ Steve Linton\\ } Email: \href{mailto://sl4@st-andrews.ac.uk} {\texttt{sl4@st\texttt{\symbol{45}}an Homepage: \href{http://sal.host.cs.st-andrews.ac.uk/} {\texttt{http://sal.host.cs. Address: \begin{minipage}[t]{8cm}\noindent Steve Linton\\ School of Computer Science,\\ University of St. Andrews,\\ North Haugh,\\ St. Andrews,\\ Fife,\\ KY16 9SS,\\ SCOTLAND\\ \end{minipage} }\\ {\mbox{}\\ \small \noindent \textbf{ Michael Albert\\ } Email: \href{mailto://malbert@cs.otago.ac.nz} {\texttt{malbert@cs.otago.ac.nz}}\\ Homepage: \href{https://www.otago.ac.nz/computer-science/people/Michael_Albert.ht Address: \begin{minipage}[t]{8cm}\noindent Michael Albert\\ Department of Computer Science,\\ University of Otago,\\ PO Box 56,\\ DUNEDIN 9054,\\ New Zealand,\\ \end{minipage} }\\ \end{titlepage} \newpage\setcounter{page}{2} \newpage \def\contentsname{Contents\logpage{[ 0, 0, 1 ]}} \tableofcontents \newpage \chapter{\textcolor{Chapter }{Introduction}}\logpage{[ 1, 0, 0 ]} \hyperdef{L}{X7DFB63A97E67C0A1}{} { Token passing networks (TPNs) are directed graphs with nodes that can hold at most one token. Also each graph has a designated input node, which generates an ordered sequence of numbered tokens and a designated output node that collects the tokens in the order they arrive at it. The input node has no incoming edges, whereas the output node has no outgoing edges. A token $t$ travels through the g the nodes, if the node the token is moving from is either the input node and the tokens $1, \ldots, t-1$ have been released or the node is not the output node, and lastly if th destination node contains no token or it is the output node. \cite{PermGenTPGraph} The set of permutations resulting from a TPN is closed under the property of containment. A permutation $a$ contains a permutation $b$ of shorter length if in $a$ there is a anti\texttt{\symbol{45}}chain, which in this context is called the basis. \cite{RegCloSet To enhance the computability of permutation pattern classes, each permutation can be encoded, using the so called rank encoding. For a permutation $p_{1} \ldots p_{n}$, it is basis, both are a rational languagesrational language as from automata. \cite{RegCloSetPerms} There is another approach to get from TPNs to their corresponding automata. Namely building equivalence classes from TPNs using the different dispositions of tokens within them. These equivalence classes of dispositions and the rank encoding of the permutations allow to build the same rational language as from the process above. \cite{PermGenTPGraph} } \chapter{\textcolor{Chapter }{Token Passing Networks}}\logpage{[ 2, 0, 0 ]} \hyperdef{L}{X7C769071875E96B2}{} { \label{tpn} A token passing network is a directed graph with a designated input node and a designated output node. The input node has no incoming edges whereas the output node has no outgoing edges. Also the input node generates a sequence of tokens, labelled 1, 2, 3, ... . These tokens are passed on to the nodes within the graph, where each node, apart from the input and output node, can hold at most one token at any time. The edges do not hold tokens but are there to pass them on. The following must hold if a token $t$ moves from the node $x$ to the node $y$. There is an edge from $x$ to $y$; $x$ is the input node, and the tokens 1, 2, 3, ... , $t-1$ have been m Token passing networks, or TPNs, are represented in \textsf{GAP} as a list. Each entry of the li contains a list of the "destinations", i.e. the end of the edge or arrow where it is directed to. Here is an example how the input of such a TPN looks in \textsf{GAP}: \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@hex:=[[2,3],[4],[5],[3,6],[6],[]];| [ [ 2, 3 ], [ 4 ], [ 5 ], [ 3, 6 ], [ 6 ], [ ] ] !gapprompt@gap>| !gapinput@| \end{Verbatim} This list represents the following directed graph: \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/hex.j From this it is visible that the input node is 1, as it has no other node pointing any arrows towards it, and the output node is 6, as it has no destinations (hence the empty list). \section{\textcolor{Chapter }{ Specific TPN }}\logpage{[ 2, 1, 0 ]} \hyperdef{L}{X80EE110279808BD3}{} { In \texttt{PatternClass} there are several functions that define different kinds of specifi passing networks. \subsection{\textcolor{Chapter }{Parstacks}} \logpage{[ 2, 1, 1 ]}\nobreak \hyperdef{L}{X85AFF5537F917AEB}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Parstacks({\mdse \label{Parstacks} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A list that represents the directed edges of a token passing network. \texttt{Parstacks} constructs a token passing network with 2 different sized stacks \texttt \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@Parstacks(2,2);| [ [ 2, 4 ], [ 3, 6 ], [ 2 ], [ 5, 6 ], [ 4 ], [ ] ] !gapprompt@gap>| !gapinput@| \end{Verbatim} \texttt{Parstacks(2,2)} can be visualised as the following directed graph: \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/ps22. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@Parstacks(4,3);| [ [ 2, 6 ], [ 3, 9 ], [ 2, 4 ], [ 3, 5 ], [ 4 ], [ 7, 9 ], [ 6, 8 ], [ 7 ], [ ] ] !gapprompt@gap>| !gapinput@| \end{Verbatim} The token passing network below represents the list that was output by \texttt{Parstacks(4,3 \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/ps43. } \subsection{\textcolor{Chapter }{Seqstacks}} \logpage{[ 2, 1, 2 ]}\nobreak \hyperdef{L}{X7D6D07D980634845}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Seqstacks({\mdse \label{Seqstacks} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A list that represents the directed edges of a token passing network. The token passing network build by \texttt{Seqstacks} contains a series of stacks (as many as y list) each of different length (each integer in the argument list). \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@Seqstacks(2,2);| [ [ 2 ], [ 3, 4 ], [ 2 ], [ 5, 6 ], [ 4 ], [ ] ] !gapprompt@gap>| !gapinput@| \end{Verbatim} \texttt{Seqstacks(2,2)} can be visualised as the following directed graph: \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/ss22. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@Seqstacks(3,1,4);| [ [ 2 ], [ 3, 5 ], [ 2, 4 ], [ 3 ], [ 4 ], [ 7, 10 ], [ 6, 8 ], [ 7, 9 ], [ 8 ], [ ] ] !gapprompt@gap>| !gapinput@| \end{Verbatim} The token passing network containing a series of stacks of length 3, 1 and 4 looks as follows: \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/ss314 } \subsection{\textcolor{Chapter }{BufferAndStack}} \logpage{[ 2, 1, 3 ]}\nobreak \hyperdef{L}{X81E3656E85CB6EB7}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{BufferAndStack({ \label{BufferAndStack} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A list that represents the directed edges of a token passing network. \texttt{BufferAndStack} is a token passing network that consists of a buffer of size \texttt{ \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@BufferAndStack(2,2);| [ [ 2, 3 ], [ 4 ], [ 4 ], [ 5, 6 ], [ 4 ], [ ] ] !gapprompt@gap>| !gapinput@| \end{Verbatim} \texttt{BufferAndStack(2,2)} is the following directed graph: \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/bs22. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@BufferAndStack(4,3);| [ [ 2 .. 5 ], [ 6 ], [ 6 ], [ 6 ], [ 6 ], [ 7, 9 ], [ 6, 8 ], [ 7 ], [ ] ] !gapprompt@gap>| !gapinput@| \end{Verbatim} The token passing network correlating to the list output by \texttt{BufferAndStack(4,3)} is \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/bs43. } } } \chapter{\textcolor{Chapter }{Permutation Encoding}}\logpage{[ 3, 0, 0 ]} \hyperdef{L}{X8696E21E80C1AEC1}{} { A permutation $\pi=\pi_{1} \ldots \pi_{n}$ has rank encoding $p_{1} \ldots p_{n}$ where $ p_{ The encoding of the permutation 3 2 5 1 6 7 4 8 9 is done as follows: \begin{center} \begin{tabular}{c|c|c}Permutation& Encoding& Assisting list\\ 325167489& $\emptyset$& 123456789\\ 25167489& 3& 12456789\\ 5167489& 32& 1456789\\ 167489& 323& 146789\\ 67489& 3231& 46789\\ 7489& 32312& 4789\\ 489& 323122& 489\\ 89& 3231221& 89\\ 9& 32312211& 9\\ $\emptyset$& 323122111& $\emptyset$\\ \end{tabular}\\[2mm] \end{center} Decoding a permutation is done in a similar fashion, taking the sequence $p_{1} \ldots p_{n}$ a The sequence 3 2 3 1 2 2 1 1 1 is decoded as: \begin{center} \begin{tabular}{c|c|c}Encoding& Permutation& Assisting list\\ 323122111& $\emptyset$& 123456789\\ 23122111& 3& 12456789\\ 3122111& 32& 1456789\\ 122111& 325& 146789\\ 22111& 3251& 46789\\ 2111& 32516& 4789\\ 111& 325167& 489\\ 11& 3251674& 89\\ 1& 32516748& 9\\ $\emptyset$& 325167489& $\emptyset$\\ \end{tabular}\\[2mm] \end{center} \section{\textcolor{Chapter }{ Encoding and Decoding }}\logpage{[ 3, 1, 0 ]} \hyperdef{L}{X793F8BF48048365F}{} { \subsection{\textcolor{Chapter }{RankEncoding}} \logpage{[ 3, 1, 1 ]}\nobreak \hyperdef{L}{X8143AF3D79F4CC1D}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RankEncoding({\m \label{RankEncoding} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A list that represents the rank encoding of the permutation \texttt{p}. Using the algorithm above \texttt{RankEncoding} turns the permutation \texttt{p} into a lis \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@RankEncoding([3, 2, 5, 1, 6, 7, 4, 8, 9]);| [ 3, 2, 3, 1, 2, 2, 1, 1, 1 ] !gapprompt@gap>| !gapinput@RankEncoding([ 4, 2, 3, 5, 1 ]); | [ 4, 2, 2, 2, 1 ] !gapprompt@gap>| !gapinput@| \end{Verbatim} } \subsection{\textcolor{Chapter }{RankDecoding}} \logpage{[ 3, 1, 2 ]}\nobreak \hyperdef{L}{X7DA97A7B7C8EB18A}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RankDecoding({\m \label{RankDecoding} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A permutation in list form. A rank encoded permutation is decoded by using the reversed process from encoding, which is also explained above. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@RankDecoding([ 3, 2, 3, 1, 2, 2, 1, 1, 1 ]);| [ 3, 2, 5, 1, 6, 7, 4, 8, 9 ] !gapprompt@gap>| !gapinput@RankDecoding([ 4, 2, 2, 2, 1 ]);| [ 4, 2, 3, 5, 1 ] !gapprompt@gap>| !gapinput@| \end{Verbatim} } \subsection{\textcolor{Chapter }{SequencesToRatExp}} \logpage{[ 3, 1, 3 ]}\nobreak \hyperdef{L}{X832A1FEC7E5491EA}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SequencesToRatEx \label{SequencesToRatExp} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A rational expression that describes all the words in \texttt{list}. A list of sequences is turned into a rational expression by concatenating each sequence and unifying all of them. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@SequencesToRatExp([[ 1, 1, 1, 1, 1 ],[ 2, 1, 2, 2, 1 ],[ 3, 2, 1, 2, 1 ], !gapprompt@>| !gapinput@[ 4, 2, 3, 2, 1 ]]);| 11111U21221U32121U42321 !gapprompt@gap>| !gapinput@| \end{Verbatim} } } } \chapter{\textcolor{Chapter }{From Networks to Automata}}\logpage{[ 4, 0, 0 ]} \hyperdef{L}{X84E9957A81BF938D}{} { It is known that the language of all encoded permutations of a TPN is rational, and thus is it indeed possible to turn a TPN into an automaton. The idea is to inspect all dispositions of tokens within the TPN and find equivalence classes of these dispositions, for more details consult \cite{PermGenTPGraph} the TPN, is also considered in this chapter. The algorithms featured in this chapter do not return the minimal automata representing the input TPN as they are exactly visualising the equivalence classes of the dispositions of the tokens in the TPN. The automaton can be minimalised by choice, as it simplifies future computations involving the automaton also is makes the automata more legible. \section{\textcolor{Chapter }{Functions}}\logpage{[ 4, 1, 0 ]} \hyperdef{L}{X86FA580F8055B274}{} { \subsection{\textcolor{Chapter }{GraphToAut}} \logpage{[ 4, 1, 1 ]}\nobreak \hyperdef{L}{X7CFD21C47E43D8FF}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{GraphToAut({\mds \label{GraphToAut} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } An automaton representing the input TPN. \texttt{GraphToAut} turns an array represented directed graph, with a distinct input node an distinct output node, into the corresponding automaton, that accepts the language build by the resulting rank encoded permutations of the directed graph. \begin{Verbatim}[commandchars=!@B,fontsize=\small,frame=single,label=Example] !gapprompt@gap>B !gapinput@x:=Seqstacks(2,2);B [ [ 2 ], [ 3, 4 ], [ 2 ], [ 5, 6 ], [ 4 ], [ ] ] !gapprompt@gap>B !gapinput@aut:=GraphToAut(x,1,6);B < epsilon automaton on 4 letters with 64 states > !gapprompt@gap>B !gapinput@aut:=MinimalAutomaton(aut);B < deterministic automaton on 3 letters with 3 states > !gapprompt@gap>B !gapinput@Display(aut);B | 1 2 3 -------------- a | 1 3 1 b | 3 3 3 c | 2 2 2 Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap>B !gapinput@B \end{Verbatim} The minimal automaton corresponding to \texttt{Seqstacks(2,2)} is: \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/ss22a \begin{Verbatim}[commandchars=!@B,fontsize=\small,frame=single,label=Example] !gapprompt@gap>B !gapinput@x:=Parstacks(2,2);B [ [ 2, 4 ], [ 3, 6 ], [ 2 ], [ 5, 6 ], [ 4 ], [ ] ] !gapprompt@gap>B !gapinput@aut:=GraphToAut(x,1,6);B < epsilon automaton on 5 letters with 66 states > !gapprompt@gap>B !gapinput@aut:=MinimalAutomaton(aut);B < deterministic automaton on 4 letters with 9 states > !gapprompt@gap>B !gapinput@Display(aut);B | 1 2 3 4 5 6 7 8 9 -------------------------------- a | 1 2 1 3 2 2 6 6 3 b | 3 2 3 3 4 3 6 9 3 c | 9 2 9 4 6 6 4 9 9 d | 8 2 8 7 5 5 7 8 8 Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap>B !gapinput@B \end{Verbatim} The rank encoded permutations of \texttt{Parstacks(2,2)} are accepted by the following auto \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/ps22a \begin{Verbatim}[commandchars=!@C,fontsize=\small,frame=single,label=Example] !gapprompt@gap>C !gapinput@x:=BufferAndStack(3,2);C [ [ 2 .. 4 ], [ 5 ], [ 5 ], [ 5 ], [ 6, 7 ], [ 5 ], [ ] ] !gapprompt@gap>C !gapinput@aut:=GraphToAut(x,1,7);C < epsilon automaton on 5 letters with 460 states > !gapprompt@gap>C !gapinput@aut:=MinimalAutomaton(aut);C < deterministic automaton on 4 letters with 4 states > !gapprompt@gap>C !gapinput@Display(aut);C | 1 2 3 4 ----------------- a | 1 4 1 3 b | 3 4 3 3 c | 4 4 4 4 d | 2 2 2 2 Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap>C !gapinput@C \end{Verbatim} The following automaton represents the language of rank encoded permutations that are output \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/bs32a \begin{Verbatim}[commandchars=!@B,fontsize=\small,frame=single,label=Example] !gapprompt@gap>B !gapinput@x:=[[2,3],[4],[5],[3,6],[6],[]];B [ [ 2, 3 ], [ 4 ], [ 5 ], [ 3, 6 ], [ 6 ], [ ] ] !gapprompt@gap>B !gapinput@aut:=GraphToAut(x,1,6);B < epsilon automaton on 4 letters with 80 states > !gapprompt@gap>B !gapinput@aut:=MinimalAutomaton(aut);B < deterministic automaton on 3 letters with 8 states > !gapprompt@gap>B !gapinput@Display(aut);B | 1 2 3 4 5 6 7 8 -------------- a | 1 3 1\hyperdef{L}{X7C}java.lang.StringIndexOutOfBoundsException: Index 33 out of b | 3 8 3 4 4 6 the correspondingautomaton that the c | 2 2 2 4 5 5 7 7 Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap>B !gapinput@B \end{Verbatim} The input TPN here is the first network described in Chapter \ref{tpn}. The language of rank java.lang.StringIndexOutOfBoundsException: Range [0, 34) out of \begin{figure}[H] \begin{ gapprompt@B gapinput@aut:GraphToAut(16);java.lang.StringI } \subsection{\textcolor{Chapter }{ConstrainedGraphToAut}} \logpage{[ 4, 1, 2 ]}\nobreak \hyperdef{L}{X7D457B517F2FDDA9}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ConstrainedGraph \label{ConstrainedGraphToAut} }\hfill{\scriptsize (function)}}\\ \textbf{\indent 1 3 1 An automaton representing the input TPN with bounded capacity. \texttt{ConstrainedGraphToAut} builds an epsilon automaton based on the same idea b 333java node and a distinct output node, but Accepting [1] there can be at most \texttt{capacity} tokens in the graph, at any timejava.lang.StringIndex \begin{Verbatim}[commandchars=!@B,fontsize=\small,frame=single,label=Example] !gapprompt@gap>B ! \begin{figure}[H] \begin{center} \eavevmode \includegraphicsscale=0 ]3 ][2] 5 ,[4], java.lang.StringIndexOutOfBoundsException: Index 51 out of bounds fo gapprompt@> !gapinput@:=(,,,)B < epsilon automaton on 6 letters with 21 states > !gapprompt@gap>B !gapinput@aut [ , 4] 6 ],[4] java.lang.StringIndexOutOfBoundsException: < deterministic automaton on 5 letters with 3 states > !gapprompt@gap>B !gapinput@Display(aut); B | 1 2 3 -------------- a | 1 2 1 b | 3 2 3 c | 2 2 2 d | 2 2 2 e | 2 2 2 Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap>B !gapinput@B \end{Verbatim} The rank encoded permutations of \texttt{Seqstacks(2,2)}, where at any time there are at most the following automaton: \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/ss22c \begin{Verbatim}[commandchars=!@E,fontsize=\small,frame=single,label=Example] !gapprompt@gap>E !gapinput@x:=BufferAndStack(3,2); E [ [ 2 .. 4 ], [ 5 ], [ 5 ], [ 5 ], [ 6, 7 ], [ 5 ], [ ] ] !gapprompt@gap>E !gapinput@aut:=ConstrainedGraphToAut(x,1,6,3);E < epsilon automaton on 7 letters with 112 states > !gapprompt@gap>E !gapinput@aut:=MinimalAutomaton(aut);E < deterministic automaton on 6 letters with 4 states > !gapprompt@gap>E !gapinput@Display(aut);E | 1 2 3 4 ----------------- a | 1 2 1 3 b | 3 2 3 3 c | 4 2 4 4 d | 2 2 2 2 e | 2 2 2 a|12 java.lang.StringIndexOutOfBoundsException: Index 17 out of bounds for f | 2 2 2 2 Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap>E !gapinput@E \end{Verbatim} The automaton corresponding to \texttt{BufferAndStack(3,2)} with limited capacity of 3 tok \ the following automaton: \begin{Verbatim}[commandchars=!@B,fontsize=\small,frame=single,label=Example] > !gapinput@:[2][[],36][][] [ java.lang.StringIndexOutOfBoundsException: Index 6 out of bounds for length 6 !gapprompt@gap>B !gapprompt@ap gapinput@:BufferAndStack(32;E < psilonautomaton on 6 letters with 48 states > !gapprompt@gap>B !gapinput@aut:=MinimalAutomaton(aut !appromptgapE!apinput@:Constra <java.lang.StringIndexOutOfBoundsException: Range [28, 27) out of bounds for leng !@B!Displayaut;B | 1 2 3 4 5 6 7 8 -- gapprompt@> gapinput(;java.lang.StringIndexOutOfBoundsException: Range [43, 44) a | --------- b | 3 8 3 4 4 6 6 6 |2 2455 d | 4 b 233java.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for le e |123 678 Initial state: [ 1 ] Accepting state: [ 1 ] gapprompt@> gB endVerbatimjava.lang.StringIndexOutOfBoundsException: Index 14 out of bounds for The automaton that accepts the |22 5577 with at most 3 tokens in java.lang.StringIndexOutOfBoundsException: Index 34 out of bo \begin{ state:[1] } } } java.lang.StringIndexOutOfBoundsException: Index 1 out of bounds for length 1 chapter{{ }FromtoNetworks}\{ ,0 } \hyperdef{L}{java.lang.StringIndexOutOfBoundsException: Index 28 out of bounds f { It is notjava.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for leng automaton alsoifan automaton represent the language java.lang.StringIndexOutOfBoundsEx ofaTPN. \PatternClass} only to whetherdeterministicautomata possible It is not see acan interpretedas finite \Chapter{}logpage[5, ,0]java.lang.StringIndexOutOfBoundsException: Index 62 out o hyperdefL{}} { \subsection{\textcolor{Chapter }{IsStarClosed}} { ,1 }nobreak \hyperdef{L}{X7E1DAEB979824B68}{} \oindent\extcolor{uncColor}\riangleright\t{IsStarClosed({mdseries\ aut}\indexIsSt \label{IsStarClosed} }\java.lang.StringIndexOutOfBoundsException: Index 6 out of bounds for length 0 \textbf{\\logpage{[ 5 1 }nobreak \texttt{true} if the start and accept states in \texttt{aut} java.lang.StringIndexOutOfBo This has label{IsStarClosed b{Verbatim}commandchars!|fontsize\,frame=single,abel=xamplejava.lang.StringIndex !gapprompt@gap>| !gapinput@x:=Automaton("det",4,2,[[3,4,2,4],[2,2,2,4]],[1],[2]);| < deterministic automaton on 2 letters with 4 states > !gapprompt@gap>| !gapinput@IsStarClosed(x); | false !gapprompt@gap>| !gapinput@AutToRatExp(x); | (a(aUb)Ub)b* !gapprompt@gap>| !gapinput@y:=Automaton("det",3,2,[[3,2,1],[2,3,1]],[1],[1]);| < deterministic automaton on 2 letters with 3 states > !gapprompt@gap>| !gapinput@IsStarClosed(y);| true !gapprompt@gap>| !gapinput@AutToRatExp(y);| ((ba*bUa)(aUb))* !gapprompt@gap>| !gapinput@| \end{Verbatim} } \subsection{\textcolor{Chapter }{Is2StarReplaceable}} \logpage{[ 5, 1, 2 ]}\nobreak \hyperdef{L}{X873324D67DC9DC41}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Is2StarReplaceab \label{Is2StarReplaceable} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } \texttt{true} if none of the states in the automaton \texttt{aut}, which are not the initial st labelled with the first letter of the alphabet. It also returns \texttt{true} if there is at lea \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@x:=Automaton("det",3,2,[[1,2,3],[2,2,3]],[1],[2]);| < deterministic automaton on 2 letters with 3 states > !gapprompt@gap>| !gapinput@Is2StarReplaceable(x);| true !gapprompt@gap>| !gapinput@y:=Automaton("det",4,2,[[4,1,1,2],[1,3,3,2]],[1],[1]);| < deterministic automaton on 2 letters with 4 states > !gapprompt@gap>| !gapinput@Is2StarReplaceable(y);| true !gapprompt@gap>| !gapinput@z:=Automaton("det",4,2,[[4,1,1,2],[1,4,2,2]],[1],[4]);| < deterministic automaton on 2 letters with 4 states > !gapprompt@gap>| !gapinput@Is2StarReplaceable(z);| false !gapprompt@gap>| !gapinput@| \end{Verbatim} } \subsection{\textcolor{Chapter }{IsStratified}} \logpage{[ 5, 1, 3 ]}\nobreak \hyperdef{L}{X7FF528F784C9020B}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{IsStratified({\m \label{IsStratified} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } \texttt{true} if \texttt{aut} has a specific "layered" form. A formal description of the most basic stratified automaton is: $(S,Q,f,q_{0},A)$ with $S:=\{1,...,n\},\,\, Q:=\{1,...,m\},\,\, n<m,\,\, q_{0}:=1,\,\, \{n+1\},\,\, f: Q \times S \rightarrow Q $ and $n+1$ is a sink state. If $i,j \in Q \setminus \{ n+1 \}$,with $i < j$, and $i',j' \in S$, $i=i',\,\, j=j'$ then \[f(i,i')=i,\,\, f(i,j')=j,\,\, f(j,j')=j,\,\, f(j,i')=j-1 \,\, or \,\, n+1.\] \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@x:=Automaton("det",4,2,[[1,3,1,4],[2,2,4,4]],[1],[2]);| < deterministic automaton on 2 letters with 4 states > !gapprompt@gap>| !gapinput@IsStratified(x); | true !gapprompt@gap>| !gapinput@y:=Automaton("det",4,2,[[1,3,2,4],[2,4,1,4]],[1],[2]);| < deterministic automaton on 2 letters with 4 states > !gapprompt@gap>| !gapinput@IsStratified(y); | false !gapprompt@gap>| !gapinput@| \end{Verbatim} } \subsection{\textcolor{Chapter }{IsPossibleGraphAut}} \logpage{[ 5, 1, 4 ]}\nobreak \hyperdef{L}{X7C3B9EB080F72043}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{IsPossibleGraphA \label{IsPossibleGraphAut} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } \texttt{true} if \texttt{aut} returns \texttt{true} in \texttt{IsStratified}, \texttt{I An automaton that fulfils the three functions above has the right form to be an automaton representing rank encoded permutations, which are output from a TPN. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@x:=Automaton("det",2,2,[[1,2],[2,2]],[1],[1]);| < deterministic automaton on 2 letters with 2 states > !gapprompt@gap>| !gapinput@IsPossibleGraphAut(x);| true !gapprompt@gap>| !gapinput@y:=Automaton("det",2,2,[[1,2],[1,2]],[1],[1]);| < deterministic automaton on 2 letters with 2 states > !gapprompt@gap>| !gapinput@IsPossibleGraphAut(y); | false !gapprompt@gap>| !gapinput@IsStarClosed(y);| true !gapprompt@gap>| !gapinput@Is2StarReplaceable(y);| true !gapprompt@gap>| !gapinput@IsStratified(y);| false !gapprompt@gap>| !gapinput@| \end{Verbatim} } } } \chapter{\textcolor{Chapter }{Pattern Classes}}\logpage{[ 6, 0, 0 ]} \hyperdef{L}{X85A198CB7EBA4BDE}{} { Permutation pattern classes can be determined using their corresponding basis. The basis of a pattern class is the anti\texttt{\symbol{45}}chain of the class, under the order of containment. A permutation $\pi$ contains another permutation $\si With the rational language of the rank encoded class, it is also possible to find the rational language of the basis and vice versa. Several specific kinds of transducers are used in this process. \cite{RegCloSetPerms} \section{\textcolor{Chapter }{Transducers}}\logpage{[ 6, 1, 0 ]} \hyperdef{L}{X843CB33182B8E477}{} { \subsection{\textcolor{Chapter }{Transducer}} \logpage{[ 6, 1, 1 ]}\nobreak \hyperdef{L}{X7A2DA7017E4F6BC4}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Transducer({\mds \label{Transducer} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A record that represents a transducer. A transducer is essentially an automaton, where running through the process does not determine whether the input is accepted, but the input is translated to another language, over a different alphabet. Formally a transducer is a six\texttt{\symbol{45}}tuple with: $Q$ being the set of states, $S In this function the transducer is stored by defining how many states there are, which one (by index) is the start or initial state, the transitions are of the form \texttt{[inputletter,outputletter,fromstate,tostate]} and a list of accept st the input and output letters on the transitions. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@trans:=Transducer(3,1,[[1,2,1,2],[1,2,2,2],[2,2,1,3],[2 !gapprompt@>| !gapinput@[1,1,3,3],[2,2,3,3]],[2]);| rec( accepting := [ 2 ], initial := 1, states := 3, transitions := [ [ 1, 2, 1, 2 ], [ 1, 2, 2, 2 ], [ 2, 2, 1, 3 ], [ 2, 2, 2, 3 ], [ 1, 1, 3, 3 ], [ 2, 2, 3, 3 ] ] ) !gapprompt@gap>| !gapinput@| \end{Verbatim} This transducer can be visualised as the following graph: \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/trans } \subsection{\textcolor{Chapter }{DeletionTransducer}} \logpage{[ 6, 1, 2 ]}\nobreak \hyperdef{L}{X7EB2EA8C78DA1F74}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{DeletionTransduc \label{DeletionTransducer} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A transducer over \texttt{k}+1 states. A deletion transducer is a transducer that deletes one letter of a rank encoded permutation and returns the correct rank encoding of the new permutation. The deletion transducer over \texttt{k} deletes letters over the set of all rank rank \texttt{k}. Specifically, running through a deletion transducer with a rank encoded permutation, of highest rank \texttt{k}, will lead to the set of all rank encoded permutations of the initial permutation removed. It is important to note that computing these shorter permutations with the transducer, is done by reading the input permutation from right to left. For example the deletion transducer with \texttt{k}=3, looks \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@DeletionTransducer(3);| rec( accepting := [ 1 .. 3 ], initial := 4, states := 4, transitions := [ [ 1, 1, 4, 4 ], [ 1, 0, 4, 1 ], [ 2, 1, 1, 1 ], [ 1, 1, 1, 2 ], [ 3, 2, 1, 1 ], [ 1, 1, 2, 3 ], [ 1, 1, 3, 3 ], [ 2, 2, 4, 4 ], [ 2, 0, 4, 2 ], [ 3, 2, 2, 2 ], [ 2, 2, 2, 3 ], [ 2, 2, 3, 3 ], [ 3, 3, 4, 4 ], [ 3, 0, 4, 3 ], [ 3, 3, 3, 3 ] ] ) !gapprompt@gap>| !gapinput@| \end{Verbatim} \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/dt3.j } \subsection{\textcolor{Chapter }{TransposedTransducer}} \logpage{[ 6, 1, 3 ]}\nobreak \hyperdef{L}{X85711F837F30E225}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{TransposedTransd \label{TransposedTransducer} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A new transducer with interchanged input and output letters on each transition. A transducer is transposed when all origins and destinations of transitions are left the same as before but the input and output letters on each transition are interchanged. Taking the deletion transducer from above, its transpose looks as follows: \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@TransposedTransducer(DeletionTransducer(3));| rec( accepting := [ 1 .. 3 ], initial := 4, states := 4, transitions := [ [ 1, 1, 4, 4 ], [ 0, 1, 4, 1 ], [ 1, 2, 1, 1 ], [ 1, 1, 1, 2 ], [ 2, 3, 1, 1 ], [ 1, 1, 2, 3 ], [ 1, 1, 3, 3 ], [ 2, 2, 4, 4 ], [ 0, 2, 4, 2 ], [ 2, 3, 2, 2 ], [ 2, 2, 2, 3 ], [ 2, 2, 3, 3 ], [ 3, 3, 4, 4 ], [ 0, 3, 4, 3 ], [ 3, 3, 3, 3 ] ] ) !gapprompt@gap>| !gapinput@| \end{Verbatim} \begin{figure}[H] \begin{center} \leavevmode \includegraphics[scale=0.75]{img/dtt3. } \ {java.lang.StringIndexOutOfBoundsException: Range [55, 54) out of bounds for le gapprompt@> y; \ !gapprompt> !gapinputy;java.lang.StringIndexOutOfBoundsException: Index 45 out of {\noindentendV} \label{InvolvementTransducer} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A transducer over \texttt{k}+1 states, with a \texttt{k} sized alphabet. isa over\{k}+ anynumberoflettersin rankencoded permutation,of rank at most \texttt{k}. \begin{Verbatim\logpage{[ , ,2]\nobreak !gap|!@InvolvementTransducer(3);| ( accepting :=[1. ],initial = 4 states:4 =[[1 1 ,2] [ 1,0 1 3] [ ,1 1,1]java.lang.StringIndexOutOfBoundsException: Index 69 out of [ 2, 0, 1, 3 ], [ 3, 2, 1, 1 ], [ 3}h\scriptsize (unction)}\ [1 0,2 ],[ ,2 ,4] 2,0 2, 2] 3 ,2, 2] [ 3, 0, 2, 2 ], [ 1, 1, 3, 2 ], [ 1, 0, 3, 3 ], [ 2, 1, 3, 1 ], [2 0 3 ,[ 3 ,3 ] [,0, , 3 ,[1 ,4 4 ,java.lang.StringIndexOutOfBoundsException: Index 72 out [ 1, 0, java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length [ 3, 0, 4, 4 ] ] ) !gapprompt@gap>| !gapinput@| end{erbatim} \begin{figure < java.lang.StringIndexOutOfBoundsException: Range [28, 27) out of bo java.lang.StringIndexOutOfBoundsException: Index 7 out of bounds for length 7 subsectionChapter{}java.lang.StringIndexOutOfBoundsException: Index 55 out of bo ,1 }nobreak \!gapprompt> gapinputz);| {\ gappromptgap|!| \label{CombineAutTransducer }\hfill{\scriptsize \textbf{\indent Returns:\ } of a combination textttaut}and texttttrans. Combining automata and transducers is done over the natural "translation\abelIsStratified the by the automaton accepted language}{ function}\\ uildinga thataccepts newlanguage.Thefunction\ thisprocess andreturnsthe new \{symbol45 utomaton \begin{Verbatim}[commandchars=!@B,fontsize=\small,frame=java.lang.StringIndexOut !gapprompt@gap>B !gapinput@a:java.lang.StringIndexOutOfBoundsException: Index 0 ou <java.lang.StringIndexOutOfBoundsException: Range [28, 27) out of bounds for leng !gapB!gapinput@()B java.lang.StringIndexOutOfBoundsException: Index 1 out of bounds for length 0 !gapB!t:Transducer21,[1212],2,11,2]java.lang.StringIndexOutOfBoundsException: Ra !gapprompt@>B !gapinput@[1,1,2,1],[2,2,2,1]],[1]);B rec( \begin{Verbatim[=@,=small,framesinglelabeljava.lang.StringIndexOutOfBoundsEx transitions := [ [ 1, 2, 1, 2 ], [ 2, 1, 1, 2 ], [ 1, 1, 2, 1 ], [ 2, 2, 2, 1 ] ] ) !gapprompt@gap>B !gapinput@res:=CombineAutTransducer(a,t);B < non deterministic automaton on 2 letters with 2 states > !gapprompt@gap>B !gapinput@AutToRatExp(res);B (ba)* !gapprompt@gap>B !gapinput@Display(res);B | 1 2 ------------------- a | [ 1 ] b | [ 2 ] Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap>B !gapinput@B \end{Verbatim} } } \section{\textcolor{Chapter }{From Class to Basis and vice versa}}\logpage{[ 6, 2, 0 ]} \hyperdef{L}{X7CFEC6DB7CA880CC}{} { \subsection{\textcolor{Chapter }{BasisAutomaton}} \logpage{[ 6, 2, 1 ]}\nobreak \hyperdef{L}{X7FD8B2357CAAFC0B}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{BasisAutomaton({ \label{BasisAutomaton} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } An automaton that accepts the rank encoded permutations of the basis of the input automaton \texttt{a}. Every pattern class has a basis that consists of the smallest set of permutations which do not belong to the class. Using \[B(L)=(L^{r} D^{t})^{r} \cap L^{c}\] it is possible using the deletion transducer $D$ and the language of rank encoded permutations \begin{Verbatim}[commandchars=!CF,fontsize=\small,frame=single,label=Example] !gappromptCgap>F !gapinputCx:=Parstacks(2,2);F [ [ 2, 4 ], [ 3, 6 ], [ 2 ], [ 5, 6 ], [ 4 ], [ ] ] !gappromptCgap>F !gapinputCxa:=GraphToAut(x,1,6);F < epsilon automaton on 5 letters with 66 states > !gappromptCgap>F !gapinputCma:=MinimalAutomaton(xa);F < deterministic automaton on 4 letters with 9 states > !gappromptCgap>F !gapinputCDisplay(ma);F | 1 2 3 4 5 6 7 8 9 -------------------------------- a | 1 2 1 3 2 2 6 6 3 b | 3 2 3 3 4 3 6 9 3 c | 9 2 9 4 6 6 4 9 9 d | 8 2 8 7 5 5 7 8 8 Initial state: [ 1 ] Accepting state: [ 1 ] !gappromptCgap>F !gapinputCba:=BasisAutomaton(ma);F < deterministic automaton on 4 letters with 9 states > !gappromptCgap>F !gapinputCDisplay(ba);F | 1 2 3 4 5 6 7 8 9 -------------------------------- a | 2 2 1 3 4 2 2 2 2 b | 2 2 2 2 2 4 1 2 8 c | 2 2 2 2 2 2 1 2 2 d | 2 2 2 9 2 2 5 6 2 Initial state: [ 7 ] Accepting states: [ 1, 5 ] !gappromptCgap>F !gapinputCAutToRatExp(ba);F d(a(dbdb)*aaU@)UbUc !gappromptCgap>F !gapinputCF \end{Verbatim} Ignoring the trailingjava.lang.StringIndexOutOfBoundsException: Index 0 out of bou permutations are avoided in this particular class. The shortest permutation in the basis, looking at the rational expression, is $daaa$, which can be translated to 4111 and de \subsection{\textcolor{Chapter }{ClassAutomaton}} \logpage{[ 6, 2, 2 ]}\nobreak \hyperdef{L}{X78BD24D7828004E8}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassAutomaton({ \label{ClassAutomaton} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } The automaton that accepts permutations of the class in their rank encoding. The function \texttt{ClassAutomaton} does the reverse process of \texttt{BasisAutomaton} encoded basis of a permutation class, and using the formula \[L=B_{k} \cap ((B(L)^{r} I^{t})^{c} )^{r}\] returns the automaton that accepts the rank encoded permutations of the class. In the formula, $B_{k}$ is the automaton that accepts all permutations of any length with highe begin{[=@,fontsize=small=l=] !gapprompt@gap>B !java.lang.StringIndexOutOfBoundsException: Index 26 out of bound !gapprompt@>B !gapinput@[2,2,2,2,2,2,1,2,2],[2,2,2,9,2,2,5,6,2]],[7],[1,5]); B < deterministic automaton on 4 letters with 9 states > !gapprompt@gap>B !gapinput@ca:=ClassAutomaton(xa); B < An automaton that three abovehas form be !gapprompt@gap>B !gapinput@Display(ca);B | 1 2 3 4 5 6 7 8 9 -------------------------------- a | 1 2 1 3 2 2 6 6 3 b | 3 2 3 3 4 3 6 9 3 4 d | 8 2 8 7 5 5 7 8 8 Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap>B !gapinput@IsPossibleGraphAut(ca);B !gap|!@:Automaton(det,,,[1,][,] true !g> g@java.lang.StringIndexOutOfBoundsException: Index 30 out of bounds for length \end{Verbatim} } \subsection{\textcolor{Chapter }{BoundedClassAutomaton}} \logpage{[ 6, 2, 3 ]}\nobreak \hyperdef{L}{X856A6F5085BAA7C3}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{BoundedClassAuto \label{BoundedClassAutomaton} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } An automaton that accepts all rank encoded permutations, with highest rank being \texttt{k}. The bounded class automaton, is an automaton that accepts all rank encoded permutations, of any length, with highest rank \texttt{k}. \begin{Verbatim}[commandchars=!@E,fontsize=\small,frame=single,label=Example] !gapprompt@gap>E !gapinput@BoundedClassAutomaton(3);E < deterministic automaton on 3 letters with 3 states > !gapprompt@gap>E !gapinput@Display(last);E | 1 2 3 -------------- a | 1 1 2 b | 2 2 2 c | 3 3 3 Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap> !gapinputjava.lang.StringIndexOutOfBoundsException: Index 30 out o \end{Verbatim} } subsection{\textcolor{Chapter }{ClassAutFromBaseEncoding}} \logpage{[ 6, 2, 4 ]}\nobreak \hyperdef{L \textcolorFuncColor{\$enspace\{ClassAutFromBaseEncoding(\slshape, }\C@textttClass \label{ClassAutFromBaseEncoding} }\hfill{\scriptsize (function)}}\\ textbf\indent Returns: } The class automaton from a list of rank encoded basis permutations. Given the permutations in the basis, in their rank encoded form, and the bound of the rank of the permutations of the class, \texttt{ClassAutFromBaseEncoding} builds the a \begin{Verbatim}[commandchars=!@G,fontsize=\small,frame=single,label=Example] !gapprompt@gap>G !gapinput@ClassAutFromBaseEncoding([[4,1,1,1]],4); G < deterministic automaton on 4 letters with 7 states > !gapprompt@gap>G !gapinput@Display(last);G | 1 2 3 4 5 6 7 -------------------------- a | 1 2 1 3 2 2 6 b | 3 2 3 3 4 3 4 c | 4 2 4 4 6 6 false d | 7 2 7 7 5 5 7 Initial [1] Accepting state: [ 1 ] !gapprompt@gap>G !gapinput@G java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0 } \subsection{\textcolor{Chapter }{ClassAutFromBase}} \logpage{[ 6, 2, 5 ]}\nobreak \hyperdef{L}{X80CBBEE08239B1B1}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassAutFromBase \label{ClassAutFromBase} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } The class automaton from a list of permutations of the basis. Taking \texttt{perms} which is the list of permutations in the basis and \texttt{k} an integer class, \texttt{ClassAutFromBase} constructs the automaton that accepts the language of ran permutations of the class. \begin{Verbatim}[commandchars=!@E,fontsize=\small,frame=single,label=Example] !gapprompt@gap>E !gapinput@ClassAutFromBase([[4,1,2,3]],4);E < deterministic automaton on 4 letters !gappromptgapE!apinput@l)E | 1 2 3 4 5 6 7 ----------------Thebasisof pattern isthe \{symbol45}ofthe 2 6java.lang.StringIndexOutOfBoundsException: Index 29 out of bounds for length 2 b|3233434 42446 java.lang.StringIndexOutOfBoundsException: Index 29 out of bounds for lengt d | 7 2 7 7 5 5 7 Initial state: [ 1 ] Accepting state: [ 1 ] !gapprompt@gap>E !gapinput@E \end{Verbatim} } subsection{textcolorChapter {}} \logpage{ 6,2 ]\obreak \hyperdef{L}{X877C8457804E4B45 {\noindent\java.lang.StringIndexOutOfBoundsException: Index 14 out of bounds for \label{ExpandAlphabet} }hfill{scriptsize (}\java.lang.StringIndexOutOfBoundsException: Index 34 out of b \textbf{\indent Returns:\ } Formally isasix{symbol45}tuple : Q setof ,$$the ,$$the I$thestart ,$\Q ofacceptstates,and Given an automaton)is orinitial ,thetransitionsare in\{},\exttt{xpandAlphabet texttta}tocontain ofsize textttnewAlphabet} haveno transit =\small,=single,abelExample] !gapprompt@gap>B !gapinput@aut:=\begin{Verbatim}[commandchars=!@|,fontsize,singlel <deterministicon with states java.lang.StringIndexOutOfBoundsException: Index 56 out !gapprompt@gap>B !gapinput@Display(aut);B |123java.lang.StringIndexOutOfBoundsException: Index 17 out of bounds for length --------- a | 2 2 3 b | 3 3 3 Initial state: [ 1 ] Accepting state: [ 3 ] !gapprompt@gap>B !gapinput@ExpandAlphabet(aut,4);B < deterministic automaton on 4 letters gappromptgap> gapinput@(last;java.lang.StringIndexOutOfBoundsException: Index 44 o | 1 2 3 --\beginfigure[]\{center}\\s=.75]{img/trans.jpg} \end{center} \end{figure} 2 \label{DeletionTransducer} b | 3 3 3 c | d| ] java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0 putB \encoded permutation and returns the correct rank encoding of the new } } \section{\textcolor{Chapter }{Direct Sum of Regular Classes}}\logpage{[ 6, 3, 0 ]} \hyperdef{L}{X8218BF7787571EE0}{} { It is obvious that the direct sum of two rational pattern classes is also rational. But the skew sum of two rational pattern classes does not imply that the resulting pattern class is rational, because if the second class in the sum has infinitely many permutations, the alphabet of the skew sum class will be infinite and thusly the resulting class will not be rational. \subsection{\textcolor{Chapter }{ClassDirectSum}} \logpage{[ 6, 3, 1 ]}\nobreak \{L}{7DC869E27CC3BFE0}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ClassDirectSum({ {\scriptsize (function)}\ \textbf{\indent Returns:\ } An these shorterpermutations with the transducer, is done by reading the input \texttt{ClassDirectSum\{Verbatim}[commandchars!|,fontsize=\small,frame=single,la \begin{Verbatim}[commandchars=!|F,fontsize=\small,frame=single,label=Example] !gapprompt|gap>F !gapinput|a:=BasisAutomaton(GraphToAut(Parstacks(2,2),1,6)); F < deterministic automaton on 4 with states > !gapprompt|gap>F !gapinput|AutToRatExp(a); F d(a(dbdb)*aaU@)UbUc !gapprompt|gap>F !gapinput|b:=MinimalAutomaton(GraphToAut(Seqstacks(2,2),1,6));F < deterministic automaton on 3 letters with 3 states > !gapprompt|gap>F !gapinput|AutToRatExp(b); F ((cc*(aUb)Ub)(cc*(aUb)Ub)*aUa)* !gapprompt|gap>F !gapinput|ab:=ClassDirectSum(a,b); F < deterministic automaton on 4 letters with 11 states > !gapprompt|gap>F !gapinput|AutToRatExp(ab); F ((d(acUc)c*(aUb)Ud(abUb))(cc*(aUb)Ub)*aUda(d(bdbd)*bdbaaUa)UbUc)((cc*(aUb)U\ b)(cc*(aUb)Ub)*aUa)*Ud(aU@) !gapprompt|gap>F !gapinput|F \end{Verbatim} } } \section{\textcolor{Chapter }{Statistical Inspections}}\logpage{[ 6, 4, 0 ]} \hyperdef{L}{X80F7EB16817DDB99}{} { It is of interest to see what permutations and how many of different length are accepted by the class, respectively the basis. In this section, the examples will be inspecting the basis automaton of the token passing network containing 2 stacks of capacity 2, !gapprompt@gap>|!gapinput@Deletio parallel to each other. \begin{Verbatim}[commandchars=!|C,fontsize=\small,frame=single,label=Example] !gapprompt|gap>C gapinputx=arstacks(,2)C [ [ 2, 4 ], [ 3, 6 ], [ 2 ], [ 5, 6 ], [ 4 ], [ ] ] !gapprompt|gap>C !gapinput|xa:=GraphToAut(x,1,6);C < epsilon automaton on 5 letters with 66 states > !gapprompt|gap>C !gapinput|ma:=MinimalAutomaton(xa);C < deterministic automaton on 4 letters with 9 states > !gapprompt|gap>C !gapinput|ba:=BasisAutomaton(ma);C < deterministic automaton on 4 letters with 9 states > !gapprompt|gap>C !gapinput|AutToRatExp(ba);C d(a(dbdb)*aaU@)UbUc !gapprompt|gap>C !gapinput|C \end{Verbatim} \subsection{\textcolor{Chapter }{Spectrum}} \logpage{[ 6, 4, 1 ]}\nobreak \hyperdef{L}{X82004197784C17F8}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{3,3] labelSpectrum} }\hfill{\ [ 2, 2,,3 ,[3 \textbf{\indent Returns:\{} A list indicating how many words of each length from 1 to \texttt{int} or 15 (default) are accept Eachentry thereturned indicateshowmanywordsoflengththeindex of the entry are accepted by the automaton \texttt{aut}. The length of the list is by default 15, little the second optional argument regulates the length of the list. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0 java.lang.StringIndexOutOfBoundsException: Range [29, 2) out of bounds for lengt !gapprompt@gap>| !gapinput@Spectrum(ba,20);| [ 3, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1 ] !gapprompt@gap>| !gapinput@| \end{Verbatim} } \subsection{\textcolor{Chapter }{NumberAcceptedWords}} \are left thesameasbefore the inputandoutputletters on each hyperdef{}X7E07D0B882DD9033{java.lang.StringIndexOutOfBoundsException: Index 33 {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{NumberAcceptedWo \label{NumberAcceptedWords} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } The number of words of length \texttt{len} accepted by the automaton \texttt{aut}. Given the automaton \texttt{aut} and the integer \texttt{len}, \texttt{java.lang.StringI \begin{Verbatim}[commandchars=!@|fontsize\small,frame=ingle,abel=] @gap|!@NumberAcceptedWords(,1;java.lang.StringIndexOutOfBoundsException: Index 5 3 !gapprompt@gap>| !gapinput@NumberAcceptedWords(ba,16);| 1 !gapprompt@gap>| !gapinput@| endVerbatim} } \subsection{\textcolor{Chapter }{AutStateTransitionMatrix}} \logpage{[ 6, 4, 3 ]}\nobreak \hyperdef{L}{X7BAE229C84A45841}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{AutStateTransiti \abelAutStateTransitionMatrix} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A matrix 2 2 3 3] 3 3 ,4] ,3 4,3 ,[3 3, 3, 3 ] ] ) In the matrix computed by \texttt{AutStateTransitionMatrix} the rows are indexed by the stat columnns are indexed by the states the transitions are ending at. Each entry $a_{i,j}$ of the ma \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@AutStateTransitionMatrix(ba);| [ [ 0, 4, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 4, 0, 0, 0, 0, 0, 0, 0 ], \V} [ 0, 3, 0, 1, 0, 0, 0, 0, 0 ], [ 0, 3, 0, [ 0, 3 0,0,0,1 0 00] [ 0, 3, 0, 0, 0, 0, 0, 1, 0 ] ] !gapprompt@gap>| !java.lang.StringIndexOutOfBoundsException: Index 1 out of bounds \end{Verbatim} } \subsection{\textcolor{Chapter }{AcceptedWords}} \logpage{[ 6{ntF{\triangleright\nspace\{InvolvementTransducer{\dseriesslshape })i{ \hyperdef{L\\Returns: java.lang.StringIndexOutOfBoundsException: Index 27 out of \\{{\$enspacetexttt{cceptedWords{mdseriesslshape ,int)indexAcceptedWords\exttt{} \label{AcceptedWords} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } All words of length \texttt{int} that are accepted by the automaton \texttt{aut}. \texttt{AcceptedWords} outputs all permutations accepted by the automaton \texttt{aut}, w \begin{Verbatim}[java.lang.StringIndexOutOfBoundsException: Index 20 out of boun gappromptgap>| !gapinput@AcceptedWords(ba,1);| [ [ 2 ], [ 3 ], [ 4 ] ] gg> !AcceptedWords(,)| [[4 4,2 ,2 ,2 ,2 4 2,1 1]] !gapprompt@gap>| !gapinput@| end{erbatim} java.lang.StringIndexOutOfBoundsException: Index 2 out of bounds for length 2 \{textcolor}AcceptedWordsR}} logpage{ ,4,5 }\obreak 2 ,3 3 ] 3 1, 3 3 ,[3 , 3,3 ,[1 ,4,4 ] {\noindent\textcolor{FuncColor}{$\triangleright$\enspace ,0,4 ,[2,2 ,4] 2 0 2] 3 3 4] \label{AcceptedWordsR} hfillscriptsize function)\java.lang.StringIndexOutOfBoundsException: Index 34 out \figureH begin l\[=.75{/.}\{}endfigure} \label{AcceptedWordsReversed} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } The list of all by the automaton accepted words of length \texttt{int1}, where each word is writ \{}and\{}are and thefollowingarguments;an t{} integer\int1}which thelengthofthe wordst of length \texttt{int1} that are accepted by \texttt{aut}. The permutations are rank encoded {noindenttextcolor{}$triangleright$enspace\{CombineAutTransducer{mdseriesslshape !@ap> gapinput@cceptedWordsRba1);| [ [ 2 ], [ 3 ], [ 4 ] ] !gapprompt@gap>| !gapinput@AcceptedWordsReversed(ba,16); | [ [ 1, 1, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 1, 4 ] ] !gapprompt@gap>| !gapinput@| \end{Verbatim} } } } c\{}{Permutation}}logpage[7,0,0]java.lang.StringIndexOutOfBoundsException: Index \hyperdef{L}{X81DB657E7FEF0295}{} { In this chapter we mention a couple functions that are fairly basic but useful tools to work with. \section{\textcolor{Chapter }{ Complement }}\logpage{[ 7, 1, 0 ]} \hyperdef{L}{X80E3E5BB8156C6A1}{} { !@gapB!@=21[121,][,,,]B {Chapter}{ermComplement} \logpage{[ 7, 1, 1 ]}\nobreak \hyperdef{L}{X820405DB787A5D32}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{(\s )indexPermCom \label{PermComplement} }\hfill{\scriptsize (function)}}\\ \ transitions := [ [ 1, 2, 1, 2 ], [ 2, 1, 1, 2 ], [ 1, 1, 2, 1 ], permutation isthecomplement of textttperm. The complement of a permutation $\tau=\ ba* \[\tau^{ gapprompt@> gapinputDisplayres)B . \begin{Verbatim}[commandchars=!@|,fontsize=\small, |[ 1 ]java.lang.StringIndexOutOf !gapprompt@gap>| !gapinput@PermComplement([3,2,8,6,7,1,5,4]);| [ 6, 7, 1, 3, 2, 8, 4, 5 ] gapprompt@> gapinput@java.lang.StringIndexOutOfBoundsException: Index 30 out of bo \end gappromptgap g@java.lang.StringIndexOutOfBoundsException: Index 30 out of bou } } \section{\textcolor{Chapter }{ Rank Encoding }}\logpage{[ 7, 2, 0 ]} \{ { \subsection{\textcolor{Chapter }{IsRankEncoding}} \logpage{[ 7, 2, 1 ]}\nobreak \hyperdef{L}{X7F1000E882050AFF}{} {\noindent\textcolor{\abel{ \{} }\hfill{\scriptsize (function)}}\\ \textbf{\indentAnautomaton therankencoded of of \texttt{true} if \texttt{perm} is a java.lang.StringIndexOutOfBoundsException: Index \texttt{IsRankEncoding} checkes whether the\BL=L{}D{}^r cap^{c\java.lang.StringIndex class automaton,withthehighestrankbeing bythe highest in \texttt{perm}. \\begin{Verbatim[commandchars=!CF,fontsize=\mallframesinglelabelExample] gappromptgap|!IsRankEncoding(3,,,,412,];java.lang.StringIndexOutOfBoundsExceptio true !gapprompt@gap>| !gapinput@IsRankEncoding([3,2,6,4,5,1,2,1]);| !gapprompt@gap>| !gapinput@| \end{Verbatim} } } } \chapter{\textcolor{Chapter }{Properties of Permutations }}\logpage{[ 8, 0, 0 ]} \hyperdef{L}{X87A0210C7BCFBA99}{} { It has been of interest 2 8755 java.lang.StringIndexOutOfBoundsException: Index 35 out .include plus\{\ymbol{}and minus\texttt{\symbol{45}}decomposable permutations, block\texttt\{45} permutations well direct sum permutations acoupleof definitions on which some of the properties are based on: An interval of a permutation $\sigma$ is a set of contiguous values which in $\sigma$ have conse permutation oflength$$ iscalled simple if it only containsthe intervals oflength 0 1and$$. hapter}Intervals }\ogpage{ , 1,0 } \hyperdef{L}{X85B2BC647868C9C4}{} { |22 2 56 java.lang.StringIndexOutOfBoundsException: Index 35 out of bounds for le \subsection{\textcolor{Chapter }{IsInterval}} \logpage{[ 8, 1, 1 ]}\nobreak \hyperdef{ gappromptCgap>F!gapinputCF {\noindent Ignoring trailing textttUbUc}which noise thebasis pattern indicates which {} \\(}\\ \textbf{\indent Returns:\ java.lang.StringIndexOutOfBoundsException: Index 1 out o \{ 6 ,2]\ IsInterval takes in any list\{ClassAutomaton} lexicographically and checkes whether it is an interval. beginVerbatim[commandchars=!|,fontsize\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@IsInterval([3,6,9,2]);| false !@gap> !@IsInterval([2,6,5,,4]);| true !gapprompt@gap>| !gapinput endVerbatim } } section{textcolor{Chapter}{ Simplicity }}\logpage{[ 8, 2, 0 ]} \hyperdef{L}{X7B82346E7E2C330C}{} { Asmentioned apermutation tobesimple only intervals\{[=@,=smallframes,labelExamplejava.lang.StringIndexOutOfBoundsExceptio \subsection{\textcolor{Chapter }{ gapprompt> gapinput@2,,2,,122][,,,,,,,,],7,15) B \logpage{[ 8, 2, 1 ]}\nobreak \hyperdef{L}{X7ECAD3E4818C589D}{} {noindenttextcolor{FuncColor}$\riangleright$\enspace\texttt{IsSimplePerm({\mdser <deterministicautomatonon4 > }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } \texttt{true} if \texttt{perm} is simple. To check whether \texttt{perm} (length of \texttt{perm} = $n$) is a simple permutation \textt \begin{Verbatim} | 1 2345 6 89java.lang.StringIndexOutOfBoundsException: Index 35 out gapprompt@gap>| !gapinput@IsSimplePerm([2,3,4,5,1,1,1,1]);| true !gapprompt@ 8 2 8 7 5 5 7 8 8 true !gapprompt@gap>| !gapinput@IsSimplePerm([3,2,8,6,7,1,5,4]);| false !gapprompt@gap>| !gapinput@| \end{Verbatim} } } \section{\textcolor{ java.lang.StringIndexOutOfBoundsException: Index 2 out of bo \hyperdef{L}{X7A6836EC7E9CE3D8}{} { In \cite{SimpPermsPosetjava.lang.StringIndexOutOfBoundsException: Index 0 out of permutation and then \logpage{[ 6, 2, 3 ]}\nobreak resulting permutation would still be\hyperdef{}X856A6F5085BAA7C3{ functions such that the set of simple permutations of shorter length, by one deletion, can be found. \subsection{\textcolor{Chapter }{OnePointDelete}} \logpage{[ 8, 3, 1 ]}\nobreak \hyperdef{L}{X877D962E7FBFB47E}{} {\noindent\textcolor{FuncColor}{$\triangleright$\\{indentReturns: java.lang.Strin \label{OnePointDelete} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A list of simple permutations with one point less than \texttt{perm}. \texttt{OnePointDelete} removes single points in the simple permutation and returns a list o resulting simple permutations, in their rank The bounded class automaton, is an automaton tha \{[=@,=\small,=singlelabelExample] !gapprompt@gap>| !gapinput@OnePointDelete([5,2,3,1,2,1]);| [[2,,1 2 1 ] 4 1 2,1 !gapprompt@gap gappromptgap> gapinput@()E [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ] !| \end{Verbatim} } \subsection{\ Accepting state \logpage{[ 8, 3, 2 ]}\nobreak \hyperdef{L}{X787F62137E709A2C}{} {\noindent\textcolor{ } \label{TwoPointDelete} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } The exceptional permutation with two point less than \texttt{perm}. \texttt{TwoPointDelete} removes two points of the input exceptional permutation and return of the unique resulting permutation, in its rank encoding. \smallf=inglelabel=Examplejava.lang.StringIndexOutOfBoundsException: Index 77 ou gapprompt@ap|!T(24681,,,]; [ [ 2, 3, 4, 1, 1, 1 ] ] !gapprompt@gap>| !gapinput@java.lang.StringIndexOutOfBoundsException: Index 31 out [ [ 2, 3, 4, 1, 1, 1 ] ] !gapprompt@gap>| !gapinput@| eV} } \subsection{\textcolor{Chapter }{PointDeletion}} \logpage{[ 8, 3, 3 ]}\nobreak \hyperdef{L}{X8696CBE580B27FE5}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{PointDeletion({\ \label{PointDeletion} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A list of simple permutations with of shorter length than \texttt{perm}. \texttt{PointDeletion} takes any simple permutation does not matter whether exceptional or removes the right number of points. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@PointDeletion([5,2,3,1,2,1]);| [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ] !gapprompt@gap>| !gapinput@PointDeletion([5,2,4,1,6,3]);| [ [ 2, 3, 1, 2, 1 ], [ 4, 1, 2, 2, 1 ] ] !gapprompt@gap>| !gapinput@PointDeletion([2,4,6,8,1,3,5,7]);| [ [ 2, 3, 4, 1, 1, 1 ] ] !gapprompt@gap>| !gapinput@PointDeletion([2,3,4,5,1,1,1,1]);| [ [ 2, 3, 4, 1, 1, 1 ] ] !gapprompt@gap>| !gapinput@| \end{Verbatim} } } \section{\textcolor{Chapter }{ Block\texttt{\symbol{45}}Decomposition }}\logpage{[ 8 \hyperdef{L}{X87EB37927F40662B}{} { Given a permutation $\pi$ of length $m$ and nonempty permutations $\alpha_{1},\ldots,\alph For example the inflation of $25413[21,1,1,1,2413]=3 2 8 9 1 5 7 4 6$, written in \textsf{GAP} th above, for $3 2 8 9 1 5 7 4 6=2413[21,12,1,2413]$ or in \textsf{GAP} notation \texttt{[3,2,8,9, \subsection{\textcolor{Chapter }{Inflation}} \logpage{[ 8, 4, 1 ]}\nobreak \hyperdef{L}{X8279728778F1F299}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{Inflation({\mdse \label{Inflation} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A permutation that represents the inflation of the list of permutations, taking the first permutation to be $\pi$, as described in the definition of inflation. Inflation takes the list of permutations that stand for a box decomposition of a permutation, and calculates that permutation by replacing each entry $i$ in the first permut index $i+1$. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@Inflation([[3,2,1],[1],[1,2],[1,2,3]]);| [ 6, 4, 5, 1, 2, 3 ] !gapprompt@gap>| !gapinput@Inflation([[1,2],[1],[4,2,1,3]]);| [ 1, 5, 3, 2, 4 ] !gapprompt@gap>| !gapinput@Inflation([[2,4,1,3],[2,1],[3,1,2],[1],[2,4,1,3]]);| [ 3, 2, 10, 8, 9, 1, 5, 7, 4, 6 ] !gapprompt@gap>| !gapinput@| \end{Verbatim} } \subsection{\textcolor{Chapter }{BlockDecomposition}} \logpage{[ 8, 4, 2 ]}\nobreak \hyperdef{L}{X7C07BE268055FEBD}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{BlockDecompositi \label{BlockDecomposition} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A list of permutations, representing the block\texttt{\symbol{45}}decomposition of \texttt{perm}. In the list the first permutati above. \texttt{BlockDecomposition} takes a plus\texttt{\symbol{45}} and minus\texttt{\symbol permutation and decomposes it into its maximal maximal intervals, which are preceded by the simple permutation that represents the positions of the intervals. If a plus\texttt{\symbol{45}} or minus\texttt{\symbol{45}}decomposable permutation is input, then the decomposition will not be the unique decomposition, by the definition of plus\texttt{\symbol{45}} or minus\texttt{\symbol{45}} decomposable permutations, see below. \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@BlockDecomposition([3,2,10,8,9,1,5,7,4,6]);| [ [ 2, 4, 1, 3 ], [ 2, 1 ], [ 3, 1, 2 ], [ 1 ], [ 2, 4, 1, 3 ] ] !gapprompt@gap>| !gapinput@BlockDecomposition([1,2,3,4,5]); | [ [ 1, 2 ], [ 1, 2, 3, 4 ], [ 1 ] ] !gapprompt@gap>| !gapinput@BlockDecomposition([5,4,3,2,1]);| [ [ 2, 1 ], [ 4, 3, 2java.lang.StringIndexOutOfBoundsException: Index 30 out of bounds f !gapprompt@gap>| !gapinput@ | \end{Verbatim} } } \section\{[ 6, ,5]\ \hyperdef{L}{X8278DD0F7F128656}{} { A permutation $\sigma$ is said to be plus\texttt{\symbol{45}}decomposable if it can be writt uniquely in the following form, \[\sigma = 12 [\alpha_{1},\alpha_{2}] \] where $\alpha_{1}$ is not plus\texttt{\symbol{45}}decomposable. The subset of a rational class, containing all permutations that are plus\texttt{\symbol{45}}decomposable and in the class, has been found to be also rational under the rank encoding. \subsection{\textcolor{Chapter }{IsPlusDecomposable}} \logpage{[ 8, 5, 1 ]}\nobreak \hyperdef{L}{X80CBC61C851B1D20}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{IsPlusDecomposab \label{IsPlusDecomposable} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } \texttt{true} if \texttt{perm} is plus\texttt{\symbol{45}}decomposable. To check whether \texttt{perm} is a plus\texttt{\symbol{45}}decomposable permutation \te \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@IsPlusDecomposable([3,3,2,3,2,2,1,1]);| true !gapprompt@gap>| !gapinput@IsPlusDecomposable([3,4,2,6,5,7,1,8]);| true !gapprompt@gap>| !gapinput@IsPlusDecomposable([3,2,8,6,7,1,5,4]);| false !gapprompt@gap>| !gapinput@| \end{Verbatim} } } \section{\textcolor{Chapter }{ Minus\texttt{\symbol{45}}Decomposability }}\logpage{ \hyperdef{L}{X801EF8FB79F18910}{} { Minus\texttt{\symbol{45}}decomposability is essentially the same as plus\texttt{\symbol{45}}decomposability, the difference is that if a permutation $\sigma$ is minus\texttt{\symbol{45}}decomposable, it can be written uniquel following form, \[\sigma = 21 [\alpha_{1},\alpha_{2}] \] where $\alpha_{1}$ is not minus\texttt{\symbol{45}}decomposable. Here also, the subset of a rational class, containing all permutations that are minus\texttt{\symbol{45}}decomposable and in the class, has been found to be rational under the rank encoding. \subsection{\textcolor{Chapter }{IsMinusDecomposable}} \logpage{[ 8, 6, 1 ]}\nobreak \hyperdef{L}{X87A6DF207B27C676}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{IsMinusDecomposa \label{IsMinusDecomposable} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } \texttt{true} if \texttt{perm} is minus\texttt{\symbol{45}}decomposable. To check whether \texttt{perm} (length of \texttt{perm} = $n$) is a minus\texttt{\symbol{45 \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@IsMinusDecomposable([3,3,3,3,3,3,2,1]);| true !gapprompt@gap>| !gapinput@IsMinusDecomposable([3,4,5,6,7,8,2,1]);| true !gapprompt@gap>| !gapinput@IsMinusDecomposable([3,2,8,6,7,1,5,4]);| false !gapprompt@gap>| !gapinput@| \end{Verbatim} } } \section{\textcolor{Chapter }{ Sums of Permutations }}\logpage{[ 8, 7, 0 ]} \hyperdef{L}{X7B7C59AA84E3425C}{} { The direct sum of two \hyperdef{L}}} \[\sigma \oplus \tau = \sigma_{1}\ \ \sigma_{2}\ldots\sigma_{k}\ \ \tau_{1}+k\ \ t{}kldots\tau_{l}+k\ .\] In a similar fashion the skew sum of $\sigma, \tau$ is \[\sigma \ominus \tau = \sigma_{1}+l\ \ \sigma_{2}+l\ldots\sigma_{k}+l\ \ \tau_{1}\ \tau_{2}\ldots\tau_{l}\ .\] The calculation of the direct and skew sums of permutations using the rank encoding is also straight forward and is used in the functions described below. The direct sum of two permutations $\sigma,\tau$ represented as their rank encoded seq rank encoding that is the concatention of the rank encoding of $\sigma$ and $\tau$. The skew sum \subsection{\textcolor{Chapter }{PermDirectSum}} \logpage{[ 8, 7, 1 ]}\nobreak \hyperdef{L}{X7E0DD72F7F6E0440}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{PermDirectSum({\ \label{PermDirectSum} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A permutation resulting from \texttt{perm1} $\oplus$ \texttt{perm2}. \texttt{PermDirectSum} returns the permutation corresponding to \texttt{perm1} $\oplus$ \begin{Verbatim[=!@,=small,=] !gapprompt@gap>| !gapinput@PermDirectSum([2,4,1,3],[2,5,4,1,3]);| [ 2, 4, 1, 3, 6, 9, 8, 5, 7 ] !gapprompt@gap>| !gapinput@PermDirectSum([2,3,1,1],[2,4,3,1,1]);| [ 2, 3, 1, 1, 2, 4, 3, 1, 1 ] !gapprompt@gap>| !gapinput@| \end{Verbatim} } \subsection{\textcolord| 7 java.lang.StringIndexOutOfBoundsException: Index 24 out \logpage{[ 8, 7, 2 ]}\nobreak \hyperdef{L}{X7CE8A32A78A4A6BB}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{PermSkewSum({\md \label{PermSkewSum} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } A permutation resulting from \texttt{perm1} $\ominus$ \texttt{perm2}. \texttt{PermSkewSum} returns the permutation corresponding to \texttt{perm1} $\ominus$ \ \begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] !gapprompt@gap>| !gapinput@PermSkewSum([2,4,1,3],[2,5,4,1,3]);| [ 7, 9, 6, 8, 2, 5, 4, 1, 3 ] !gapprompt@gap>| !gapinput@PermSkewSum([2,3,1,1],[2,4,3,1,1]);| [ 7, 8, 6, 6, 2, 4, 3, 1, 1 ] !gapprompt@gap>| !gapinput@| \end{Verbatim} } } } \chapter{\textcolor{Chapter }{ Regular Languages of Sets of Permutations }}\logpage{[ 9, 0 \hyperdef{L}{X7E9C84807FCB6408}{} { This chapter is dedicated to the different sets of permutations with the same properties. \section{\textcolor{Chapter }{ Inversions in Permutations }}\logpage{[ 9, 1, 0 ]} \hyperdef{L}{X82F103DB7A446E7B}{} { An inversion in a permutation $\tau=\tau_{1}\ldots\tau_{n}$ is a pair $(i,j)$ such that $1\l \subsection{\textcolor{Chapter }{InversionAut}} \logpage{[ 9, 1, 1 ]}\nobreak \hyperdef{L}{X79B3989A7D90B227}{} {\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{InversionAut({\m \label{InversionAut} }\hfill{\scriptsize (function)}}\\ \textbf{\indent Returns:\ } An automaton that accepts all permutations with exactly \texttt{k} inversions. The rational language of all permutations with a given number , \texttt{k}, of inversions is co |