(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 122494, 4265]*) (*NotebookOutlinePosition[ 124439, 4330]*) (* CellTagsIndexPosition[ 124276, 4321]*) (*WindowFrame->Normal*) Notebook[{ Cell["\[Copyright] 2003 K. Sutner ", "SmallText"], Cell[TextData[StyleBox["Transformation Semigroups", FontFamily->"Charter"]], "Title", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:1"], Cell[CellGroupData[{ Cell["Transformation Semigroups", "Section"], Cell[CellGroupData[{ Cell["Transformations", "Subsection"], Cell[TextData[{ "A ", StyleBox["semigroup", FontColor->RGBColor[0, 0, 1]], " is a set together with an associative operation. If there is an identity \ element we have a ", StyleBox["monoid", FontColor->RGBColor[0, 0, 1]], ". A group is a monoid where every element has an inverse. One can show \ that every semigroup can already be represented as a set of maps ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\ \[RightArrow] \ \([n]\)\)]], " where the operation is composition of functions (much as every group \ can be represented as a group of permutations). We will refer to such \ semigroups as ", StyleBox["transformation semigroups", FontColor->RGBColor[0, 0, 1]], ". The elements are transformations and are represented by terms of the \ form \n\t", Cell[BoxData[ \(TraditionalForm\`T[\ a\_1, \ a\_2, \ \[Ellipsis], \ a\_n\ ]\)]], "\nwhere ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ a\_i \[LessEqual] \ n\)]], ". Thus, 1 is mapped to ", Cell[BoxData[ \(TraditionalForm\`a\_1\)]], ", 2 to ", Cell[BoxData[ \(TraditionalForm\`a\_2\)]], " and so forth. Composition is implemented using ", ButtonBox["NonCommutativeMultiply", ButtonStyle->"RefGuideLink"], ". Note that ", StyleBox["x**y", FontFamily->"Courier"], " is composition in diagrammatic order: apply ", Cell[BoxData[ \(TraditionalForm\`x\)]], " first, then apply ", Cell[BoxData[ \(TraditionalForm\`y\)]], " (as opposed to ", ButtonBox["Composition", ButtonStyle->"RefGuideLink"], " in ", StyleBox["Mathematica", FontSlant->"Italic"], ")." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(x = T[2, 3, 4, 5, 6, 1]\), "\n", \(y = T[2, 2, 5, 6, 5, 6]\), "\n", \(x ** y\), "\n", \(y ** x\)}], "Input", AspectRatioFixed->True], Cell["The corresponding diagrams.", "Text"], Cell[BoxData[{ \(\(\(PlotT[#, DisplayFunction \[Rule] Identity, PlotStyle \[Rule] {0.03, 0.03}, LabelGrid \[Rule] Automatic] &\)\ /@ \ {{x, y}, {y, x}};\)\), "\[IndentingNewLine]", \(\(ShowArray[%];\)\)}], "Input"], Cell[TextData[{ "Products of the same transformation can be expressed as powers. Note that \ in the example ", Cell[BoxData[ \(TraditionalForm\`x = \ x\^7\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(x\^Range[0, 8]\ // \ ColumnForm\), "\n", \(x === x\^7\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Since transformations are maps ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\ \[RightArrow] \ \([n]\)\)]], " we can associate a range and a kernel to each transformation. The \ cardinality of the range is the ", StyleBox["rank", FontColor->RGBColor[0, 0, 1]], " of the transformation. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(y\), "\n", \(\(ker = KernelT[y];\)\), "\n", \(\(im = ImageT[y];\)\), "\n", \(Thread[{ker, im}] // \ \(Curry[TableForm]\)[ TableDepth \[Rule] 2]\)}], "Input"], Cell[TextData[{ "Since lists are automatically ordered in ", StyleBox["Mathematica", FontSlant->"Italic"], " we can reconstruct a transformation from its kernel and range." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(KernelImageToT[ker, im]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "A transformation ", Cell[BoxData[ \(TraditionalForm\`x\)]], " induces a map from the kernel classes to the kernel classes, or, by \ renumbering, a new transformation ", Cell[BoxData[ \(TraditionalForm\`\([r]\)\ \[RightArrow] \ \([r]\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`r\)]], " is the rank of ", Cell[BoxData[ \(TraditionalForm\`x\)]], ". This map is the collapse of ", Cell[BoxData[ \(TraditionalForm\`x\)]], ". In the next example, the collapse is a permutation. As a result, there \ is some exponent ", Cell[BoxData[ \(TraditionalForm\`p > 1\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`x\ = \ x\^\(\(\ \)\(p\)\)\)]], " and the powers of ", Cell[BoxData[ \(TraditionalForm\`x\)]], " form a group. The identity of this group is idempotent (i.e., ", Cell[BoxData[ FormBox[Cell[TextData[Cell[BoxData[ \(TraditionalForm\`e\^2 = \ e\)]]]], TraditionalForm]]], ") and we can compute inverses." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(x = T[2, 3, 1, 8, 8, 5, 5, 5];\)\), "\n", \(Thread[{ImageT[x], KernelT[x]}] // \ \(Curry[TableForm]\)[ TableDepth \[Rule] 2]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(kx = CollapseT[x]\), "\n", \(OrderT[kx]\), "\n", \(xx = InverseT[x]\), "\n", \(e = x ** xx\), "\n", \(e ** e \[Equal] e\)}], "Input", AspectRatioFixed->True], Cell["\<\ Of course, in general the collapse fails to be a permutation. \ However, a sufficiently high power of any transformation always has a \ permutation as collapse. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(y = T[2, 3, 4, 5, 6, 7, 7]\), "\n", \(CollapseT /@ \(y\^Range[6]\)\ // \ ColumnForm\)}], "Input", AspectRatioFixed->True], Cell["\<\ Iterating the collapse provides an alternative way to compute \ powers of a transformation (alternative to the standard divide-and-conquer \ fast exponentiation algorithm).\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(z\ = \ T[13, 14, 10, 7, 7, 2, 4, 9, 10, 15, 8, 12, 7, 6, 14];\)\), "\[IndentingNewLine]", \(Kz\ = \ KernelT[z]\), "\[IndentingNewLine]", \(Iz\ = \ ImageT[z]\)}], "Input"], Cell[BoxData[ \(Table[\ KernelImageToT[Kz, \ ActionT[\ Iz, \ CollapseT[z]^i\ ]], \ {i, 0, 10}] === z^Range[11]\)], "Input"], Cell[TextData[{ "A semigroup ", Cell[BoxData[ \(TraditionalForm\`S\)]], " is ", StyleBox["generated", FontColor->RGBColor[0, 0, 1]], " by some of its elements iff every element in ", Cell[BoxData[ \(TraditionalForm\`S\)]], " can be written as a product of these elements (but not necessarily in a \ unique way). The semigroup generated by any single element thus has the form \ of a lasso: there is a transient part that leads to a cycle. If the transient \ part has length 0 the transformation generates a group. In the other extreme, \ if the cycle has length 1, the transformation is said to be aperiodic. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(TransientPeriodicT[x]\), "\n", \(TransientPeriodicT[y]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Graphically we can display the powers of transformations using the command \ ", StyleBox["PlotT", "Commentary"], ". It is clear from the pictures that ", Cell[BoxData[ \(TraditionalForm\`y\)]], " is ", StyleBox["aperiodic: ", FontColor->RGBColor[0, 0, 1]], "for some exponent ", Cell[BoxData[ \(TraditionalForm\`k\)]], ": ", Cell[BoxData[ \(TraditionalForm\`x\^\(k + 1\) = \ x\^\(\(\ \)\(k\)\)\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotT[x];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotT[y];\)\)], "Input", AspectRatioFixed->True], Cell["\<\ The same analysis for a random transformation. Execute the next \ cell several times to see the various patterns. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(z = RandomT[12]\), "\n", \(Thread[{KernelT[z], ImageT[z]}]\ // \ \(Curry[TableForm]\)[ TableDepth \[Rule] 2]\), "\n", \(TransientPeriodicT[z]\), "\n", \(\(PlotT[z];\)\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "The semigroup generated by a transformation always ", Cell[BoxData[ \(TraditionalForm\`z\)]], " contains an idempotent element. In the orbit of the map ", Cell[BoxData[ \(TraditionalForm\`x\ \[RightTeeArrow] \ x ** \ z\)]], " on 1 the idempotent element appears inside the periodic part. Here is an \ example." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(z\ = T[13, 14, 10, 7, 7, 2, 4, 9, 10, 15, 8, 12, 7, 6, 14];\)\), "\[IndentingNewLine]", \({t, p}\ = \ AnalyzeOrbit[\ # ** z &, \ OneT[15]]\)}], "Input"], Cell[BoxData[ \(NestList[\ # ** z &, \ OneT[15], \ t + p\ ]\ // EnumForm0\)], "Input"], Cell[BoxData[ \(IdemSG[z^Range[t, t + p - 1]]\)], "Input"], Cell["\<\ The periodic part forms a cyclic group which can be seen (more or \ less) from the multiplication table.\ \>", "Text"], Cell[BoxData[{ \(\(S\ = \ z^Range[t, t + p - 1];\)\), "\[IndentingNewLine]", \(\(Partition[\ AllTimes[S, S], \ Length[S]\ ]\ /. \ RankingRules[S];\)\), "\[IndentingNewLine]", \(\(PlotMatrix[%];\)\)}], "Input"], Cell["\<\ Here is a better test using the kernel/image decomposition of the \ transformations.\ \>", "Text"], Cell[BoxData[ \(InGroupSG[S]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Witnesses and Equations", "Subsection", CellTags->"c:4"], Cell[CellGroupData[{ Cell["Full Transformation Semigroups", "Subsubsection"], Cell[TextData[{ "The full transformation semigroup of all maps ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\ \[RightArrow] \ \([n]\)\)]], " is generated by the three transformations produced by commands ", ButtonBox["ShiftT", ButtonStyle->"AddOnsLink"], ", ", ButtonBox["TranspositionT", ButtonStyle->"AddOnsLink"], " and ", ButtonBox["Merge12T", ButtonStyle->"AddOnsLink"], ". The first two are permutations and together they generate the symmetric \ group on ", Cell[BoxData[ \(TraditionalForm\`n\)]], " points. For example, for ", Cell[BoxData[ \(TraditionalForm\`n\ = \ 8\)]], " these transformations are as follows:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \({ShiftT[8], TranspositionT[8], Merge12T[8]} // \ ColumnForm\)], "Input",\ AspectRatioFixed->True], Cell[TextData[{ "Since ", Cell[BoxData[ \(TraditionalForm\`T\_n\)]], " has ", Cell[BoxData[ \(TraditionalForm\`n\^\(\(\ \)\(n\)\)\)]], " elements we have to confine ourselves to a smaller example." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(T3 = TransformationSG[3]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "The full semigroup ", Cell[BoxData[ \(TraditionalForm\`T\_3\)]], " contains the identity map ", Cell[BoxData[ \(TraditionalForm\`T[1, 2, 3]\)]], ", so we have a monoid. There are 16 aperiodic elements in ", Cell[BoxData[ \(TraditionalForm\`T\_3\)]], ", 10 of which are idempotents. Three of them are right nulls (the constant \ functions ", Cell[BoxData[ \(TraditionalForm\`T[i, i, i]\)]], "). 21 elements belong to a group in ", Cell[BoxData[ \(TraditionalForm\`T\_3\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(aper = AperiodicSG[T3]\), "\n", \(Length[aper]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(idem = IdemSG[T3]\), "\n", \(Length[idem]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(null = RightNullSG[T3]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Length[IngroupSG[T3]]\)], "Input", AspectRatioFixed->True], Cell["\<\ We can verify that these transformations are indeed aperiodic and \ idempotent.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(aper\^3 === aper\^2\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(idem\ idem === idem\)], "Input", AspectRatioFixed->True], Cell["The pictures for the aperiodic elements.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(\(PlotT[#, 5, \ PlotStyle \[Rule] {0.05, 0.05}, DisplayFunction \[Rule] Identity] &\) /@ aper;\)\), "\n", \(\(ShowArray[%];\)\)}], "Input"], Cell["\<\ The elements of rank 3 form a group, the symmetric group on three \ points. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(S3 = Select[T3, RankT[#] == 3 &]\)], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\(\(PlotT[#, PlotStyle \[Rule] {0.05, 0.05}, DisplayFunction \[Rule] Identity] &\) /@ ToList[S3];\)\), "\n", \(\(ShowArray[%];\)\)}], "Input"], Cell[TextData[{ "If we associate the three generators with symbols ", Cell[BoxData[ \(TraditionalForm\`a\)]], ", ", Cell[BoxData[ \(TraditionalForm\`b\)]], " and ", Cell[BoxData[ \(TraditionalForm\`c\)]], ", we can write each element in ", Cell[BoxData[ \(TraditionalForm\`T\_n\)]], " as a word over the alphabet ", Cell[BoxData[ \(TraditionalForm\`{a, b, c}\)]], ". The minimal such word (in the length-lex order) is the witness for the \ transformation. As we will see later, it is often convenient to replace the \ elements of a transformation semigroup by their witnesses. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\({T3, W, eq} = TransformationSG[3, Equations \[Rule] True];\)\), "\n", \(PrintWitnesses[T3, W]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "The relations between these words are captured in the list of equations \ produced by the command ", ButtonBox["GenerateSG", ButtonStyle->"AddOnsLink"], ". The semigroup is isomorphic to the quotient of ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^+\)/\[Theta]\)]], " where \[Theta] is the congruence induced by the equations. For any \ congruence of finite index there exists a suitable finite system of \ equations. Note that the equations are actually implemented as directed \ rewrite rules ", Cell[BoxData[ \(TraditionalForm\`u \[Rule] v\)]], " suitable as input for ", ButtonBox["WordReduce", ButtonStyle->"AddOnsLink"], ". We always have ", Cell[BoxData[ \(TraditionalForm\`v\ \( < \_\(l\[InvisibleComma]l\)\)\ u\)]], " where ", Cell[BoxData[ \(TraditionalForm\`\( < \_\(l\[InvisibleComma]l\)\)\)]], " indicates length-lex order. Hence the corresponding rewrite system must \ be terminating. Nonetheless, we will often use the algebraic terminology \ instead and speak about equations. For example, ", Cell[BoxData[ \(TraditionalForm\`c\)]], " corresponds to the idempotent element ", Cell[BoxData[ \(TraditionalForm\`T[1, 1, 3]\)]], ", so there is an equation", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ StyleBox["cc", FontSlant->"Italic"], " ", "=", " ", "c"}]}], TraditionalForm]]], ", implemented as the rule ", Cell[BoxData[ \(TraditionalForm\`\(c\[InvisibleComma]c \[Rule] \(\(c\)\(.\)\)\)\)]] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(PrintEquations[eq]\)], "Input", AspectRatioFixed->True], Cell["\<\ These equations can be simplified considerably without changing the \ corresponding quotient structure. Note that the left-hand-sides and \ right-hand-sides of the new set of rewrite rules are irreducible with respect \ to the rules (both the old and the new).\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(seq\ = \ SimplifyEquations[T3, W, eq];\)\), "\n", \(PrintEquations[seq]\)}], "Input"], Cell[TextData[{ "One can see clearly now that the generators corresponding to ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " have orders 2 and 3, respectively. The generator for ", Cell[BoxData[ \(TraditionalForm\`c\)]], " is idempotent. By repeated application of these rewrite rules we can \ simplify any word to the corresponding witness. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(WordReduce[caacbcaaca, eq, DoTrace \[Rule] True]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Going in the opposite direction, one can also construct a semigroup from a \ set of equations. For example, over the alphabet ", Cell[BoxData[ \(TraditionalForm\`{a}\)]], " the equation ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["a", FontSlant->"Italic"], "4"], " ", "=", " ", "a"}], TraditionalForm]]], " defines the semigroup ", Cell[BoxData[ FormBox[ RowBox[{"{", RowBox[{"a", ",", StyleBox["aa", FontSlant->"Italic"], ",", StyleBox["aaa", FontSlant->"Italic"]}], "}"}], TraditionalForm]]], " where the operation is concatenation and subsequent reduction according \ to the equation. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(EquationsToWitnesses[{{aaaa, a}}, {a}]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Command ", StyleBox["EquationsToWitnesses", "MR"], " has a default bound of 500 for the number of witnesses generated since it \ is undecidable whether the corresponding semigroup is finite for larger \ alphabets. The bound can be changed by setting, say, ", StyleBox["BoundETW->1000", "MR"], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(red = {{aaaaa, a}, {bbb, bb}, {ba, ab}};\)\), "\n", \(S = EquationsToWitnesses[red, {a, b}]\)}], "Input"], Cell[BoxData[ \(WordReduce[aaabbbaaabbb, red]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "We can translate ", Cell[BoxData[ \(TraditionalForm\`S\)]], " into a transformation semigroup by converting the the right translations \ \[RightTeeArrow] ", Cell[BoxData[ \(TraditionalForm\`x\ \[RightTeeArrow] \ x\[VeryThinSpace]a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`x\ \[RightTeeArrow] \ x\[VeryThinSpace]b\)]], " into transformations: " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Ta = T @@ PositionList[ S, \((WordReduce[Concatenate[#1, a], red] &)\) /@ S]\), "\n", \(Tb = T @@ PositionList[ S, \((WordReduce[Concatenate[#1, b], red] &)\) /@ S]\)}], "Input"], Cell[BoxData[{ \(\({SS, W, eq} = GenerateSG[GEN[14, 2, {Ta, Tb}], Equations \[Rule] True];\)\), "\n", \(Length[SS]\), "\n", \(S === W\), "\n", \(PrintWitnesses[SS, W]\)}], "Input"], Cell[TextData[{ "The equations produced by ", StyleBox["EquationsToWitnesses", "MR"], " are not simplified." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(PrintEquations[eq]\)], "Input", AspectRatioFixed->True], Cell["\<\ But once we simplify them, we are back to our original set of \ rewrite rules, up to order.\ \>", "Text"], Cell[BoxData[ \(SimplifyEquations[SS, W, eq]\ \ // \ PrintEquations\)], "Input"], Cell[BoxData[ \(red\ \ // \ PrintEquations\)], "Input"], Cell["\<\ Here is an example of a set of equations that do not produce a \ finite semigroup. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(red = {{aaaa, 1}, {bbb, bb}, {bbaa, 1}}\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(EquationsToWitnesses[red, {a, b}, BoundETW \[Rule] 100]\)], "Input", AspectRatioFixed->True], Cell["Add some more equations:", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(red\ = \ Join[red, {{baab, a}, {baba, bb}, {bbabb, bb}}]; EquationsToWitnesses[\ red, {a, b}, BoundETW \[Rule] 100]\)], "Input"], Cell[TextData[{ "Still no good, all words in ", Cell[BoxData[ FormBox[ SuperscriptBox[ RowBox[{"(", StyleBox["baaa", FontSlant->"Italic"], ")"}], "*"], TraditionalForm]]], " are still irreducible. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(red\ = \ Join[red, {{baaa, a}}]; EquationsToWitnesses[red, {a, b}, BoundETW \[Rule] 100]\)], "Input"], Cell["That looks more promising. Let's increase the bound. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(EquationsToWitnesses[red, {a, b}, BoundETW \[Rule] 500]\)], "Input"], Cell["\<\ Same as before. Hence the last set of equations really defines a \ finite semigroup. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(red\ // \ WordSort\)\ // \ PrintEquations\)], "Input"], Cell["For the suspicious, here is a computational proof.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(WordReduce[\ Words[8], \ red\ ]\ // \ Union\)\ // \ Length\), "\[IndentingNewLine]", \(\(WordReduce[\ Words[9], \ red\ ]\ // \ Union\)\ // \ Length\), "\[IndentingNewLine]", \(\(WordReduce[\ Words[10], \ red\ ]\ // \ Union\)\ // \ Length\)}], "Input"], Cell["\<\ Hence all words already reduce to a word of length at most 9. The \ longest irreducible word is\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(\(WordReduce[\ Words[9], \ red\ ]\ // \ Union\)\ \ // \ WordSort\)\ \ // \ Last\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Other Transformation Semigroups", "Subsubsection"], Cell["\<\ One can specify generators of a transformation semigroup directly \ as follows.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(gen\ = \ GEN[8, 3, {T[1, 2, 3, 4, 5, 6, 7, 8], T[3, 1, 2, 5, 4, 3, 8, 7], T[4, 1, 2, 3, 4, 5, 2, 8]}]\)], "Input"], Cell[BoxData[ \(gen\ = \ GEN[6, 2, {T[3, 1, 2, 5, 4, 3], T[4, 1, 2, 3, 4, 5]}]\)], "Input"], Cell["\<\ The length specification 8 and the alphabet size 3 are redundant, \ but it is often useful to have this information easily available. Here is an \ example of a somewhat larger semigroup. On a modern PC this should take about \ half a second (without the external code).\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(S\ = \ GenerateSG[gen];\)\ // \ Timing\), "\[IndentingNewLine]", \(S\ // \ Length\)}], "Input"], Cell[BoxData[ \(IdemSG[S]\ // \ Length\)], "Input"], Cell[BoxData[ \(\(\(RightNullSG[S]\)\(\ \)\)\)], "Input"], Cell["\<\ Computing witnesses and the canonical rewrite rules slows things \ down quite a bit to some 13 seconds.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\({S, W, eq}\ = \ GenerateSG[gen, Equations \[Rule] True];\)\ // \ Timing\)], "Input"], Cell["Even after simplification there are 229 equations left.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(seq\ = \ SimplifyEquations[S, W, eq];\)\), "\[IndentingNewLine]", \(PrintEquations[seq]\)}], "Input"], Cell["\<\ Here is an example over the Boolean matrix semiring. We start with \ 5 Boolean matrices.\ \>", "Text"], Cell[BoxData[ \(\(mats\ = \ {{{0, 1, 0}, {0, 0, 1}, {1, 0, 0}}, {{0, 1, 0}, {1, 0, 0}, {0, 0, 1}}, {{1, 0, 0}, {1, 0, 0}, {0, 0, 1}}, {{0, 0, 0}, {0, 1, 0}, {0, 0, 1}}};\)\)], "Input"], Cell[BoxData[{ \(\(\(PlotMatrix[#, GridLines \[Rule] True, DisplayFunction \[Rule] Identity] &\)\ /@ \ mats;\)\), "\[IndentingNewLine]", \(\(ShowArray[%];\)\)}], "Input"], Cell[BoxData[{ \(\(gen\ = \ GEN[\ 3, 4, \ mats\ ];\)\), "\n", \(\(S\ = \ GenerateSG[\ gen, \ \[IndentingNewLine]\tMatrix \[Rule] True, \ Unit \[Rule] IdentityMatrix, \ Filter \[Rule] Sign\ ];\)\), "\n", \(S\ // \ Length\)}], "Input"], Cell["\<\ The semigroup generated by these four matrices has size 64 and \ contains the null-matrix.\ \>", "Text"], Cell[BoxData[{ \(\(\(PlotMatrix[#, GridLines \[Rule] True, DisplayFunction \[Rule] Identity] &\)\ /@ \ ToList[S];\)\), "\[IndentingNewLine]", \(\(ShowArray[%];\)\)}], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Green's Relations", "Subsection", CellTags->"c:4"], Cell[CellGroupData[{ Cell["Definitions", "Subsubsection"], Cell[TextData[{ "A classical decomposition method for finite semigroups is based on Green's \ relations. Assume that ", Cell[BoxData[ \(TraditionalForm\`S\)]], " is a monoid (if not, adjoin a 1). Define a number of equivalence \ relations on ", Cell[BoxData[ \(TraditionalForm\`S\)]], " by comparing the left, right and two-sided ideals generated by the \ elements of the semigroup as follows.\n\t", Cell[BoxData[ \(TraditionalForm\`a\ R\ b\ \[DoubleLeftRightArrow] \ \ a\ S\ = \ b\ S\)]], ", \n\t", Cell[BoxData[ \(TraditionalForm\`a\ L\ b\ \[DoubleLeftRightArrow] \ \ S\ a\ = S\ b\)]], ", \n\t", Cell[BoxData[ \(TraditionalForm\`a\ J\ b\ \[DoubleLeftRightArrow] \ \ S\ a\ S\ = \ S\ b\ S\)]], ". \nAlso let ", Cell[BoxData[ \(TraditionalForm\`H\ = \ R\ \[SquareIntersection] \ L\)]], " and ", Cell[BoxData[ \(TraditionalForm\`D\ = \ R\ \[SquareUnion] \ L\)]], ". It is well-known that for finite semigroups ", Cell[BoxData[ \(TraditionalForm\`D\ = \ J\)]], ".\nHere are some pictures of these relations for ", Cell[BoxData[ \(TraditionalForm\`T\_3\)]], ". " }], "Text"], Cell[BoxData[{ \(\(T3\ = \ TransformationSG[3];\)\), "\[IndentingNewLine]", \(\(TT\ = \ CartesianProduct[\ ToList[T3], ToList[T3]];\)\)}], "Input"], Cell[BoxData[ \(\(PlotMatrix[ RelationToMatrix[ToList[T3], GreenRQT[#1, #2, T3] &]];\)\)], "Input"], Cell[BoxData[ \(\(PlotMatrix[ RelationToMatrix[ToList[T3], GreenLQT[#1, #2, T3] &]];\)\)], "Input"], Cell[BoxData[ \(\(PlotMatrix[ RelationToMatrix[ToList[T3], GreenHQT[#1, #2, T3] &]];\)\)], "Input"], Cell["\<\ The next computation uses a brute-force comparison based on \ generating the two-sided ideals and is thus painfully slow.\ \>", "Text"], Cell[BoxData[ \(\(PlotMatrix[ RelationToMatrix[ToList[T3], GreenJQT[#1, #2, T3] &]];\)\)], "Input"], Cell[TextData[{ "A better description of ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes is based on the fact that ", Cell[BoxData[ \(TraditionalForm\`R\)]], " and ", Cell[BoxData[ \(TraditionalForm\`L\)]], " commute whence\n\t", Cell[BoxData[ \(TraditionalForm\`a\ \ D\ b\ \[DoubleLeftRightArrow] \ \(\[Exists] \ c\ \((\ a\ R\ c\ \[And] \ c\ L\ b)\)\)\)]], ". \nThus, we can arrange ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes as rectangular grids whose points are ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-classes. Each row corresponds to an ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-class and each column to an ", Cell[BoxData[ \(TraditionalForm\`L\)]], "-class. Green's lemma states that the right translations associated with \ two elements of an ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-class induce inverse bijections on the ", Cell[BoxData[ \(TraditionalForm\`L\)]], "-classes of the elements. Thus, if ", Cell[BoxData[ \(TraditionalForm\`x\ u\ = \ y\)]], " we have ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\_\(u\ : \ L\_x\[LongRightArrow]\ L\_y\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`\(\[Rho]\_u\)(z)\ = \ z\ u\)]], ". These bijections preserve ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-classes. \nLet's verify Green's lemma for ", Cell[BoxData[ \(TraditionalForm\`T\_3\)]], ". Here is a ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class of ", Cell[BoxData[ \(TraditionalForm\`T\_3\)]], ", see below for methods to compute this class. " }], "Text"], Cell[BoxData[{ \(\(dc\ = \ {{{T[1, 1, 3], T[3, 3, 1]}, {T[2, 2, 1], T[1, 1, 2]}, {T[3, 3, 2], T[2, 2, 3]}}, {{T[1, 3, 1], T[3, 1, 3]}, {T[2, 1, 2], T[1, 2, 1]}, {T[3, 2, 3], T[2, 3, 2]}}, {{T[3, 1, 1], T[1, 3, 3]}, {T[1, 2, 2], T[2, 1, 1]}, {T[2, 3, 3], T[3, 2, 2]}}};\)\), "\[IndentingNewLine]", \(dc\ // MatrixForm\)}], "Input"], Cell[TextData[{ "We can find right multipliers by solving equations in ", Cell[BoxData[ \(TraditionalForm\`T\_3\)]], ". We choose two elements in the second ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-class \"at random\"." }], "Text"], Cell[BoxData[{ \(x\ = \ dc[\([2, 1, 1]\)]\), "\[IndentingNewLine]", \(y\ = \ dc[\([2, 3, 2]\)]\)}], "Input"], Cell[BoxData[{ \(SolveSG[\ x, \ y, \ T3\ ]\), "\[IndentingNewLine]", \(\(u\ = \ First[%];\)\), "\[IndentingNewLine]", \(SolveSG[\ y, \ x, \ T3\ ]\), "\[IndentingNewLine]", \(\(v\ = \ First[%];\)\)}], "Input"], Cell["Sanity check:", "Text"], Cell[BoxData[{ \(x\ ** \ u\ \[Equal] \ y\), "\[IndentingNewLine]", \(y\ ** \ v\ \[Equal] \ x\)}], "Input"], Cell[TextData[{ "We extract two of the ", Cell[BoxData[ \(TraditionalForm\`L\)]], "-classes." }], "Text"], Cell[BoxData[{ \(L1\ = \ \(Thread[dc]\)[\([1]\)]\), "\[IndentingNewLine]", \(L3\ = \ \(Thread[dc]\)[\([3]\)]\)}], "Input"], Cell[TextData[{ "Since ", ButtonBox["NonCommutativeMultiply", ButtonStyle->"RefGuideLink"], " distributes properly over lists in ", StyleBox["Automata", "MR"], ", we can simply multiply these matrices by ", Cell[BoxData[ \(TraditionalForm\`u\)]], " and ", Cell[BoxData[ \(TraditionalForm\`v\)]], ". " }], "Text"], Cell[BoxData[{ \(L1\ ** \ u\), "\[IndentingNewLine]", \(L3\)}], "Input"], Cell[BoxData[{ \(L3\ ** \ v\), "\[IndentingNewLine]", \(L1\)}], "Input"], Cell[TextData[{ "Correct (note that the order of elements in the ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-classes is reversed). Another well-known result is that ", Cell[BoxData[ \(TraditionalForm\`x\ y\ \[Element] \ R\_x \[Intersection] \ L\_y\)]], " if and only if ", Cell[BoxData[ \(TraditionalForm\`R\_y \[Intersection] \ L\_x\)]], " contains an idempotent. We can verify this for the last ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class. First, we determine the positions of the idempotents." }], "Text"], Cell[BoxData[ \(ids\ = \ Select[\ Flatten[dc], IdemSG\ ]\)], "Input"], Cell[BoxData[ \(pos\ = \ FlattenOne[\(Position[\ dc, \ #] &\)\ /@ \ ids]\)], "Input"], Cell[BoxData[ \(\(Fold[\ \ ReplacePart[#1, 1, #2] &, Array[0 &, {3, 3}], Most /@ pos]\ // \ \(Curry[PlotMatrix]\)[ GridLines \[Rule] True];\)\)], "Input"], Cell[TextData[{ "We check the whole ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-class rather than just individual elements. First, multiply ", Cell[BoxData[ \(TraditionalForm\`H\_11\)]], " by ", Cell[BoxData[ \(TraditionalForm\`H\_33\)]], " which multiplication should produce ", Cell[BoxData[ \(TraditionalForm\`H\_13\)]], ". " }], "Text"], Cell[BoxData[{ \(AllTimes[\ dc[\([1, 1]\)], \ dc[\([3, 3]\)]]\ \ // \ Union\), "\[IndentingNewLine]", \(dc[\([1, 3]\)]\)}], "Input"], Cell[TextData[{ "But ", Cell[BoxData[ \(TraditionalForm\`H\_11\)]], " by ", Cell[BoxData[ \(TraditionalForm\`H\_23\)]], " should lead outside of the ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class." }], "Text"], Cell[BoxData[{ \(AllTimes[\ dc[\([1, 1]\)], \ dc[\([2, 3]\)]]\ \ // \ Union\), "\[IndentingNewLine]", \(Intersection[%, Flatten[dc]]\)}], "Input"], Cell[TextData[{ "At any rate, a reasonable datastructure for a ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class is consists of \n\t- a list of right multipliers that translate the \ ", Cell[BoxData[ \(TraditionalForm\`L\)]], "-classes, \n\t- a list of left multipliers that translate the ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-classes, and\n\t- one of the ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-classes.\nThis is the format of the output produced by ", ButtonBox["GenerateSG", ButtonStyle->"AddOnsLink"], " and ", ButtonBox["DClassDecomposition", ButtonStyle->"AddOnsLink"], ". Note that only regular ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes are generated by these commands." }], "Text"], Cell[BoxData[ \(\({S, W, eq, dcl}\ = \ TransformationSG[3, DClasses \[Rule] True];\)\)], "Input"], Cell[TextData[{ "The dimensions of all 3 ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes." }], "Text"], Cell[BoxData[ \(DClassSize[\ dcl, \ Full \[Rule] True\ ]\)], "Input"], Cell[TextData[{ "In multiplier-representation a ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class uses a special constructor ", ButtonBox["DC", ButtonStyle->"AddOnsLink"], ". " }], "Text"], Cell[BoxData[ \(dcl[\([1]\)]\)], "Input"], Cell["It is usually more interesting to look at the expanded form.", "Text"], Cell[BoxData[ \(\(dcl[\([1]\)]\ // \ DClassToBlocks\)\ // \ MatrixForm\)], "Input"], Cell[TextData[{ "In this case all ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes are regular. The last consists of a single ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-class which is isomorphic to the symmetric group on 3 points. Here are \ the other two. The right nulls form the second ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class." }], "Text"], Cell[BoxData[ \(\(dcl[\([2]\)]\ // \ DClassToBlocks\)\ // \ MatrixForm\)], "Input"], Cell["\<\ It may be more convenient to replace the transformations by their \ witnesses.\ \>", "Text"], Cell[BoxData[{ \(WitnessFunction[h, S, W]\), "\[IndentingNewLine]", \(\(\(dcl[\([1]\)]\ // \ DClassToBlocks\)\ // \ h\)\ // \ MatrixForm\)}], "Input"], Cell["The multipliers here are", "Text"], Cell[BoxData[ \({lm, rm, hc} = \ h /@ \ ToList@dcl[\([1]\)]\)], "Input"], Cell[TextData[{ "After concatenation and suitable simplification we obtain the first ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-class." }], "Text"], Cell[BoxData[ \(WordReduce[\ Concatenate[\ hc, \ rm], \ eq\ ]\)], "Input"], Cell[TextData[{ "Likewise for the first ", Cell[BoxData[ \(TraditionalForm\`L\)]], "-class." }], "Text"], Cell[BoxData[ \(WordReduce[\ Concatenate[\ lm, \ hc], \ eq\ ]\)], "Input"], Cell[TextData[{ "The ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-class in the middle of the last row." }], "Text"], Cell[BoxData[ \(WordReduce[\ Concatenate[\ a, \ hc, aa], \ eq\ ]\)], "Input"], Cell["\<\ For the right-nulls one can read the right-multipliers off the \ table of rewrite rules.\ \>", "Text"], Cell[BoxData[ \(\(\(dcl[\([2]\)]\ // \ DClassToBlocks\)\ // \ h\)\ // \ MatrixForm\)], "Input"], Cell[BoxData[{ \(\(seq\ = \ SimplifyEquations[S, W, eq];\)\), "\n", \(PrintEquations[seq]\)}], "Input"], Cell[TextData[{ "Of course, for the full transformation semigroup there is a much simpler \ description of Green's relations: ", Cell[BoxData[ \(TraditionalForm\`x\ R\ y\ \[DoubleLeftRightArrow] \ ker(x)\ = \ ker(y)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`x\ L\ y\ \[DoubleLeftRightArrow] \ im(x)\ = \ im(y)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`x\ D\ y\ \[DoubleLeftRightArrow] \ rk(x)\ = \ rk(y)\)]], ". In general, though, only the implications from left to right are valid. \ Note that we really need the classical, unordered versions. " }], "Text"], Cell[BoxData[{ \(\(d1\ = \ dcl[\([1]\)]\ // \ DClassToBlocks;\)\), "\n", \(Map[\ Sort, \ KernelT[d1], {3}]\ // \ MatrixForm\)}], "Input"], Cell[BoxData[ \(ImageT[d1]\ // \ MatrixForm\)], "Input"], Cell[BoxData[ \(RankT[d1]\ // \ MatrixForm\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Another Example", "Subsubsection"], Cell["A semigroup with 3 generators.", "Text"], Cell[BoxData[{ \(\(t1\ = \ T[2, 3, 4, 5, 5];\)\), "\[IndentingNewLine]", \(\(t2\ = \ T[3, 1, 4, 5, 5];\)\), "\[IndentingNewLine]", \(\(t3\ = \ T[2, 1, 4, 3, 5];\)\)}], "Input"], Cell[BoxData[{ \(\({S, W, eq, dcl}\ = \ GenerateSG[GEN[5, 3, {t1, t2, t3}], DClasses \[Rule] True];\)\), "\[IndentingNewLine]", \(S\ // \ Length\)}], "Input"], Cell[TextData[{ "There are 6 regular ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes, and all the ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-classes are trivial." }], "Text"], Cell[BoxData[ \(DClassSize[dcl, Full \[Rule] True]\)], "Input"], Cell[TextData[{ "But all together there are 14 ", " ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes." }], "Text"], Cell[BoxData[{ \(\(dclall\ = \ DClassDecomposition[S, RegularOnly \[Rule] False];\)\), "\[IndentingNewLine]", \(DClassSize[dclall, Full \[Rule] True]\)}], "Input"], Cell["After simplification 38 equations remain.", "Text"], Cell[BoxData[{ \(\(seq\ = \ SimplifyEquations[S, W, eq\ ];\)\), "\n", \(PrintEquations[seq]\)}], "Input"], Cell["Random words of length 20 here tend to reduce to 0.", "Text"], Cell[BoxData[ \(WordReduce[\ RandomWord[20, 3], eq, DoTrace \[Rule] True\ ]\)], "Input"], Cell[TextData[{ "To see why, construct a machine that accepts all words which fail to \ reduce to 0 under ", StyleBox["eq", "MR"], "." }], "Text"], Cell[BoxData[ \(all\ = \ Table[\ DFA[\ 5, 3, \ ToList\ /@ \ {t1, t2, t3}, \ p, \ {5}\ ], \ {p, 4}]\)], "Input"], Cell[BoxData[ \(m\ = \ ComplementFA[\ MinimizeFA[IntersectionFA @@ all]]\)], "Input"], Cell["A sanity check for words of length 8.", "Text"], Cell[BoxData[ \(WordReduce[\ LanguageFA[m, 8], \ eq\ ]\ \ // \ Union\)], "Input"], Cell[TextData[{ "A numerical look at the growth rate of the language of ", StyleBox["m", "MR"], " shows that only about a third of one percent of all words of length 20 \ will not reduce to 0." }], "Text"], Cell[BoxData[{ \(LanguageFA[\ m, \ \(-20\), \ SizeOnly \[Rule] True\ ]\), "\[IndentingNewLine]", \(%\ /\ 3^Range[0, 20]\ // \ N\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["A J-Trivial Semigroup", "Subsubsection"], Cell[TextData[{ "A well-known example for a ", Cell[BoxData[ \(TraditionalForm\`J\)]], "-trivial semigroup is the collection of all transformations ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(t\ : \ \([n]\)\ \[LongRightArrow]\ \ \([n]\)\)\)\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`t\)]], " is non-decreasing and inflationary (i.e., ", Cell[BoxData[ \(TraditionalForm\`i\ \[LessEqual] \ t(i)\)]], "). " }], "Text"], Cell[BoxData[ \(S\ = \ JTrivialSG[5]\)], "Input"], Cell[BoxData[{ \(\(\(PlotT[#, 4, PlotStyle \[Rule] {0.05, 0.05}, DisplayFunction \[Rule] Identity] &\)\ /@ \ ToList[S];\)\), "\[IndentingNewLine]", \(\(ShowArray[%];\)\)}], "Input"], Cell[TextData[{ "The algorithm used in Automata will produce ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes whose left- and right-multipliers are 1. The ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-classes consist of the idempotents. " }], "Text"], Cell[BoxData[ \(dcl\ = DClassDecomposition[S]\)], "Input"], Cell[BoxData[ \(Sort[Flatten[Last\ /@ \ dcl]]\ === \ Sort[IdemSG[S]]\)], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Cayley Graphs", "Subsection"], Cell[TextData[{ "Algorithmically one can think about Green's relations also in a more \ combinatorial way. Consider the right Cayley graph of ", Cell[BoxData[ \(TraditionalForm\`S\)]], " with respect to a given set of generators. Clearly, a strongly connected \ component in this graph corresponds to an ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-class in the semigroup. Here is the example of ", Cell[BoxData[ \(TraditionalForm\`T\_3\)]], " again." }], "Text"], Cell[BoxData[{ \(ClearAll[dot, a, b, c]\), "\[IndentingNewLine]", \(\(dot[\ x_, "\"] := \ x\ ** \ T[2, 3, 1];\)\), "\n", \(\(dot[\ x_, "\"] := \ x\ ** \ T[2, 1, 3];\)\), "\n", \(\(dot[\ x_, "\"] := \ x\ ** \ T[1, 1, 3];\)\), "\n", \(Gr\ = \ GenerateCayleyGraph[\ T[1, 2, 3], dot, {a, b, c}]\)}], "Input"], Cell[TextData[{ "There are 5 strongly connected components just as there are 5 classes for \ ", Cell[BoxData[ \(TraditionalForm\`R\)]], "." }], "Text"], Cell[BoxData[{ \(\(sccr\ = \ StronglyConnectedComponents[Gr];\)\), "\[IndentingNewLine]", \(Length\ /@ \ sccr\)}], "Input"], Cell[BoxData[{ \(\(S3\ = \ TransformationSG[3];\)\), "\[IndentingNewLine]", \(\(V\ = \ VertexSet[Gr];\)\), "\[IndentingNewLine]", \(\(cls\ = \ ToClasses[\ V, GreenRQT[#1, #2, S3] &];\)\), "\[IndentingNewLine]", \(Length\ /@ \ cls\)}], "Input"], Cell["The corresponding sets of transformations are the same. ", "Text"], Cell[BoxData[ \(V[\([sccr[\([1]\)]]\)]\)], "Input"], Cell[BoxData[ \(Sort\ /@ \ \((\ \(V[\([#]\)] &\)\ /@ \ sccr\ \ === cls\ )\)\)], "Input"], Cell["Now for the left Cayley graph.", "Text"], Cell[BoxData[{ \(ClearAll[dot]\), "\n", \(\(dot[\ "\", x_] := \ \ T[2, 3, 1] ** x;\)\), "\n", \(\(dot[\ "\", x_] := \ \ T[2, 1, 3] ** x;\)\), "\n", \(dot[\ "\", x_] := \ \ T[1, 1, 3] ** x; Gl\ = \ GenerateCayleyGraph[\ T[1, 2, 3], dot, {a, b, c}, Direction \[Rule] Left]\)}], "Input"], Cell[BoxData[ \(sccl\ = StronglyConnectedComponents[Gl]\)], "Input"], Cell[TextData[{ "Note that the enumeration of ", Cell[BoxData[ \(TraditionalForm\`T\_3\)]], " differs in the two Cayley graphs" }], "Text"], Cell[BoxData[ \(VertexSet[Gl]\ === \ VertexSet[Gr]\)], "Input"], Cell[TextData[{ "We compensate by applying an appropriate permutation. The non-empty \ intersections correspond to the ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-classes." }], "Text"], Cell[BoxData[{ \(\(pos\ = \ PositionList[\ VertexSet[Gl], \ VertexSet[Gr]\ ];\)\), "\n", \(\(AssignFunction[\ \ P, \ Range[27], \ ToList[InverseT[T @@ pos]], \ Opts \[Rule] Listable\ ];\)\)}], "Input"], Cell[BoxData[ \(Apply[\ Intersection, \ CartesianProduct[\ sccr, \ \ P[sccl]\ ], \ {1}\ ]\ // \ Union\)], "Input"], Cell[BoxData[ \(\(Length\ /@ \ DeleteCases[%, {}]\ // \ Frequencies\)\ // \ TableForm\)], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Syntactic Semigroups", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Syntactic semigroups", "c:5"}], Cell[CellGroupData[{ Cell["Syntactic Semigroups", "Subsection"], Cell[TextData[{ "Any language ", Cell[BoxData[ \(TraditionalForm\`L\ \[SubsetEqual] \ \[CapitalSigma]\^\(\(\ \ \)\(+\)\)\)]], " induces a congruence ", Cell[BoxData[ \(TraditionalForm\`\(~\_L\)\)]], ", the syntactic congruence of ", Cell[BoxData[ \(TraditionalForm\`L\)]], ", on the semigroup of all (nonempty) words ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\^\(\(\ \)\(+\)\)\)]], " as follows:\n\t", Cell[BoxData[ \(TraditionalForm\`x\ \(~\_L\)\ y\ \ \[DoubleLeftRightArrow] \ \(\[ForAll] \ u\), \ v\ \[Element] \ \(\[CapitalSigma]\^\(\(\ \)\(*\)\)\)(\ \ \ u\ x\ v\ \ \[Element] \ L\ \ \[LeftRightArrow] \ u\ y\ v\ \[Element] \ L)\)]], ".\nThe quotient semigroup ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\^\(\(\ \)\(+\)\)/\(~\_L\)\)]], " is the syntactic semigroup of ", Cell[BoxData[ \(TraditionalForm\`L\)]], ". On occasion it is more convenient to consider all words and to deal \ with the quotient monoid ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\^\(\(\ \)\(*\)\)/\(~\_L\)\)]], " . Note that ", Cell[BoxData[ \(TraditionalForm\`\(~\_L\)\)]], " saturates ", Cell[BoxData[ \(TraditionalForm\`L\)]], ". In fact, ", Cell[BoxData[ \(TraditionalForm\`\(~\_L\)\)]], " is the coarsest congruence that saturates ", Cell[BoxData[ \(TraditionalForm\`L\)]], ". \nFor example, ", Cell[BoxData[ \(TraditionalForm\`L\ = \ \(a\^*\) \(b\^*\)\)]], " produces the 5 equivalence classes ", Cell[BoxData[ \(TraditionalForm\`\([\[Epsilon]]\)\ = \ \[Epsilon]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\([a]\)\ = \ \(a\^+\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\([b\[VeryThinSpace]]\)\ = \ \(b\^+\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\([a\[InvisibleComma] b]\)\ = \ \(a\^+\) \(b\^+\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\([b\[VeryThinSpace]a]\)\ = \(\(\((a + b)\)\^*\)\ - \ \(a\^*\) \(b\^*\)\ = \(\((a + b)\)\^*\) b\)\[InvisibleComma]\ a\ \(\((a + b)\)\^*\)\)\)]], ".\nFor regular languages we can use the minimal DFA for ", Cell[BoxData[ \(TraditionalForm\`L\)]], " to determine some words in the classes of the syntactic congruence as \ follows." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(m\ = \ MinimizeFA[\ RegularExpressionToFA[RET[RES[a], RES[b]], 2]]\)], "Input"], Cell[BoxData[ \(SyntacticCongruence[m, \(-4\)]\ // \ ColumnForm\)], "Input"], Cell[TextData[{ "To compute with the syntactic congruence or a regular language one \ exploits a representation of the syntactic semigroup in terms of the \ transition semigroup of a DFA accepting the language. A deterministic finite \ automaton over state set ", Cell[BoxData[ \(TraditionalForm\`Q\)]], " and alphabet ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], " can be construed as a collection of transition functions\n\t\t", Cell[BoxData[ \(TraditionalForm\`\[Tau]\_s\)]], Cell[BoxData[ \(TraditionalForm\`\(\(\ \ \)\(\(:\)\(\ \)\(Q\ \[LongRightArrow] Q\)\)\)\)]], "\nfor ", Cell[BoxData[ \(TraditionalForm\`s\ \[Element] \ \[CapitalSigma]\)]], ". These functions generate a finite semigroup, a subsemigroup of the \ full monoid ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]Q \[Rule] Q, \[CenterDot]\[RightAngleBracket]\)]], " of endofunctions on ", Cell[BoxData[ \(TraditionalForm\`Q\)]], " under composition. In particular for ", Cell[BoxData[ \(TraditionalForm\`Q\ = \ \([n]\)\)]], " we can express a transition function ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\_s\)]], StyleBox[" ", FontVariations->{"CompatibilityType"->"Subscript"}], "as a vector of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", with values in ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\)]], ". In ", StyleBox["Automata", "MR"], ", such functions are represented by expressions\n\t\t", Cell[BoxData[ \(TraditionalForm\`T[a\_1, \ \(a\_\(\(2\)\(,\)\)\) \[Ellipsis], a\_n]\)]], "\nwhere ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ a\_i \[LessEqual] \ n\)]], ". The semigroup generated by the transformations ", Cell[BoxData[ \(TraditionalForm\`\[Tau]\_s\)]], ", ", Cell[BoxData[ \(TraditionalForm\`s\ \[Element] \ \[CapitalSigma]\)]], ", is the transition semigroup of the automaton. If we start from the \ minimal automaton, we obtain the syntactic semigroup of the corresponding \ language. There is a natural homomorphism\n\t\t ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \[CapitalSigma]\^\(\(\ \)\(*\)\)\ \[LongRightArrow]\ \ S\)]], StyleBox["\n", FontFamily->"Symbol"], "where ", Cell[BoxData[ \(TraditionalForm\`S\)]], " is the syntactic semigroup of the machine, which homomorphism induces the \ syntactic congruence relation. Since \t\t", Cell[BoxData[ \(TraditionalForm\`L\ = \ \(f\^\(-1\)\)(\ S\_0)\)]], "\nfor some ", Cell[BoxData[ \(TraditionalForm\`S\_0 \[SubsetEqual] \ S\)]], " one says that ", Cell[BoxData[ \(TraditionalForm\`S\)]], " recognizes ", Cell[BoxData[ \(TraditionalForm\`L\)]], ". The regular languages are precisely the languages recognized by finite \ semigroups.\nWe now give a few examples that show how to compute (the and in \ the) syntactic semigroup. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Singletons and Stars", "Subsection"], Cell[CellGroupData[{ Cell[TextData[{ " ", Cell[BoxData[ \(TraditionalForm\`L\ = \ w\)]] }], "Subsubsection"], Cell[TextData[{ "What is the syntactic semigroup of a singleton language ", Cell[BoxData[ \(TraditionalForm\`L = {w}\)]], "?\nWe construct a DFA for ", Cell[BoxData[ \(TraditionalForm\`L\)]], " by taking the complement of a machine recognizing all words of length \ exactly 2 or 4." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(m\ = \ BuildDFA[aabbaa, {a, b}]\)], "Input"], Cell["The DFA m is already minimal:", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Hence we can compute the syntactic semigroup of L as follows.\ \>", \ "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(gen = ToGeneratorsFA[m]\), "\n", \(S = GenerateSG[gen]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Since ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is a finite complement language, S must contain a null, the constant map \ associated with the trap state in ", Cell[BoxData[ \(TraditionalForm\`m\)]], ". This is the only idempotent element of the semigroup." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(TrapStatesFA[m]\), "\[IndentingNewLine]", \(NullSG[S]\), "\[IndentingNewLine]", \(IdemSG[S]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "We recompute ", Cell[BoxData[ \(TraditionalForm\`S\)]], " together with a list of witnesses and equations. Note that all non-empty \ factors of ", Cell[BoxData[ \(TraditionalForm\`w\)]], " appear as witnesses of non-zero elements of ", Cell[BoxData[ \(TraditionalForm\`S\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\({S, W, eq} = GenerateSG[gen, Equations \[Rule] True];\)\), "\n", \(PrintWitnesses[S, W]\)}], "Input"], Cell[TextData[{ "The equations are all of the form ", Cell[BoxData[ \(TraditionalForm\`u\ \[Rule] \ 0\)]], "." }], "Text"], Cell[BoxData[ \(PrintEquations[eq]\)], "Input", AspectRatioFixed->True], Cell["The equations can be simplified quite a bit as follows.", "Text"], Cell[BoxData[{ \(\(seq\ = \ SimplifyEquations[S, W, eq];\)\), "\[IndentingNewLine]", \(PrintEquations[seq]\)}], "Input"], Cell[TextData[{ "As expected, the only words of length up to 6 that are not rewritten to 0 \ are the factors of ", Cell[BoxData[ \(TraditionalForm\`w\)]], ". " }], "Text"], Cell[BoxData[ \(WordReduce[\ Flatten@Words[\(-6\)], seq]\)], "Input"], Cell["All words of length up to 7 or higher simplify to 0.", "Text"], Cell[BoxData[ \(WordReduce[\ \ Words[7], seq]\ // \ Union\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ " ", Cell[BoxData[ \(TraditionalForm\`L\ = \ \(w\^*\)\)]] }], "Subsubsection"], Cell[TextData[{ "Here is the analogous computation for the language L = ", Cell[BoxData[ \(TraditionalForm\`\(w\^*\)\)]], ". " }], "Text"], Cell[BoxData[ \(ms\ = \ MinimizeFA[RegularExpressionToFA[RES["\<01234\>"], \(-5\)]]\)], "Input",\ AspectRatioFixed->True], Cell[BoxData[ \(S = SyntacticSG[ms]\)], "Input", AspectRatioFixed->True], Cell["\<\ Again there is a null, but this time there are other idempotents as \ well. One can more or less read off the loop in the minimal DFA. \ \>", \ "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(NullSG[S]\), "\[IndentingNewLine]", \(\(IdemSG[S]\ // \ Sort\)\ // \ TableForm\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "We recompute ", Cell[BoxData[ \(TraditionalForm\`S\)]], " together with a list of witnesses and equations. Note that all non-empty \ factors of ", Cell[BoxData[ \(TraditionalForm\`w\)]], " appear as witnesses of non-zero elements of ", Cell[BoxData[ \(TraditionalForm\`S\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\({S, W, eq, dcl} = SyntacticSG[ms, DClasses \[Rule] True];\)\), "\[IndentingNewLine]", \(S\ // \ Length\)}], "Input"], Cell[TextData[{ "There are two regular ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes, comprising all the elements of ", Cell[BoxData[ \(TraditionalForm\`S\)]], ". The first consists of the null." }], "Text"], Cell[BoxData[ \(DClassSize[dcl, Full \[Rule] True]\)], "Input"], Cell[BoxData[{ \(WitnessFunction[h, S, W]\), "\[IndentingNewLine]", \(\(d1\ = \ dcl[\([1]\)]\ // \ DClassToBlocks;\)\), "\[IndentingNewLine]", \(\(d1\ // \ h\)\ // \ MatrixForm\)}], "Input"], Cell[TextData[{ "The witnesses in the second ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes are particularly simple. The diagonal consists of the idempotents \ (other than the null)." }], "Text"], Cell[BoxData[{ \(\(d2\ = \ dcl[\([2]\)]\ // \ DClassToBlocks;\)\), "\[IndentingNewLine]", \(\(d2\ \ // \ h\)\ // \ MatrixForm\)}], "Input"], Cell[BoxData[ \(IdemSG[S]\ // \ h\)], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Finite and Cofinite Languages", "Subsection"], Cell[TextData[{ "Consider the following cofinite language ", Cell[BoxData[ \(TraditionalForm\`L\)]], ":\n ", Cell[BoxData[ \(TraditionalForm\`\(\(L\)\(\ \)\(=\)\(\ \)\)\)]], "all words over ", Cell[BoxData[ \(TraditionalForm\`{a, b}\)]], " of length different from 2 and 4.\nSince the syntactic semigroup does not \ distinguish between a language and its complement we construct instead the \ minimal DFA for the complement." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(m\ = \ LengthDFA[{2, 4}, {a, b}]\)], "Input"], Cell[BoxData[{ \(\(L = LanguageFA[m, \(-5\)];\)\), "\n", \(L\ // \ EnumForm0\)}], "Input"], Cell["The DFA m is already minimal:", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(MinimizeFA[m]\ // \ Size\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Hence we can compute the syntactic semigroup of ", Cell[BoxData[ \(TraditionalForm\`L\)]], " as follows." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(gen = ToGeneratorsFA[m]\), "\n", \(S = GenerateSG[gen]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Since ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is a finite complement language, S must contain a null." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(NullSG[S]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Indeed, ", Cell[BoxData[ \(TraditionalForm\`S\)]], " is ", StyleBox["nilpotent", FontColor->RGBColor[0, 0, 1]], ": there are no idempotents other than the null (which is no surprise since \ Nil is the variety corresponding exactly to finite-cofinite languages)." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(NilpotentQSG[S]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "We recompute ", Cell[BoxData[ \(TraditionalForm\`S\)]], " together with a list of witnesses and equations. Since the acceptance \ language ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is defined solely in terms of the lengths of words we get an equation ", Cell[BoxData[ \(TraditionalForm\`a\ = \ b\)]], " (both symbols induce the same transition behavior) and", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(a\^\(\(\ \)\(5\)\)\ = \ a\^\(\(\ \)\(4\)\)\)\)\)]], ", since all words of length at least 4 are indistinguishable in m. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\({S, W, eq} = GenerateSG[gen, Equations \[Rule] True];\)\), "\n", \(PrintWitnesses[S, W]\)}], "Input"], Cell[BoxData[ \(PrintEquations[eq]\)], "Input", AspectRatioFixed->True], Cell["The equations can be simplified quite a bit as follows.", "Text"], Cell[BoxData[{ \(\(seq\ = \ SimplifyEquations[S, W, eq];\)\), "\[IndentingNewLine]", \(PrintEquations[seq]\)}], "Input"], Cell[BoxData[ \(WordReduce[RandomWord[10, {a, b}], eq]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "The complement of ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is recognized by ", Cell[BoxData[ \(TraditionalForm\`S\_0 = \ {a\^2, a\^4}\)]], "." }], "Text"], Cell[BoxData[{ \(SyntacticHomomorphism[f, m]\), "\[IndentingNewLine]", \(f[Words[2]]\ // \ Union\), "\[IndentingNewLine]", \(f[Words[4]]\ // \ Union\)}], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Mod-Counters", "Subsection"], Cell[TextData[{ "Below we define ", StyleBox["m5", "MR"], " to be the minimal automaton for words over alphabet ", Cell[BoxData[ \(TraditionalForm\`{a, b, c}\)]], " containing a number of b's that is congruent 0 modulo 5. As in the last \ section, we compute the syntactic semigroup (which turns out to be a group in \ this case) and the syntactic congruence." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m5 = CounterDFA[b, 0, {a, b, c}, Modulus \[Rule] 5];\)\), "\n", \(\({S5, wit, eqn} = SyntacticSG[m5, Equations \[Rule] True];\)\), "\n", \(S5\ // \ ColumnForm\)}], "Input"], Cell[BoxData[ \(InGroupSG[S5]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "There is exactly one idempotent element in ", Cell[BoxData[ \(TraditionalForm\`S\_\(\(\ \)\(5\)\)\)]], ", namely the unit element. Its ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-class is the whole group. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(IdemSG[S5]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(HClassT[OneT[5], S5]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(PrintWitnesses[S5, wit]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "From the equations we see that inputs ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`c\)]], " are ignored and ", Cell[BoxData[ \(TraditionalForm\`b\)]], "'s are counted modulo 5, as expected. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(PrintEquations[eqn]\)], "Input", AspectRatioFixed->True], Cell["This becomes clear when the equations are simplified.", "Text"], Cell[BoxData[ \(PrintEquations[SimplifyEquations[S5, wit, eqn]]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[Cell[BoxData[ \(TraditionalForm\`L \((a, i)\)\)]]], "Subsection"], Cell[TextData[{ "For the next example let us again consider all words that have a symbol ", Cell[BoxData[ \(TraditionalForm\`b\)]], " in position ", Cell[BoxData[ \(TraditionalForm\`\(-3\)\)]], ". " }], "Text"], Cell[BoxData[{ \(\(Mb3 = ToDFA[IthSymbolFA[\ b, \(-3\), {a, b}]];\)\), "\n", \(\({S, wit, eqn} = SyntacticSG[Mb3, Equations \[Rule] True];\)\), "\n", \(Length[S]\), "\n", \(S\ // \ ColumnForm\)}], "Input"], Cell[TextData[{ "Thus, the syntactic monoid has size 14 and contains all the constant \ functions ", Cell[BoxData[ \(TraditionalForm\`T[i, i, ... , i]\)]], ". The constants are exactly the idempotents in ", Cell[BoxData[ \(TraditionalForm\`S\)]], ", or, equivalently, the right nulls in ", Cell[BoxData[ \(TraditionalForm\`S\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(idem = IdemSG[S]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(RightNullSG[S] == idem\)], "Input"], Cell["\<\ To see where these constant functions come from let us generate the \ corresponding witnesses.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(PrintWitnesses[S, wit]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Thus, for all words ", Cell[BoxData[ \(TraditionalForm\`w\)]], " of length at least 3 the syntactic homomorphism ", Cell[BoxData[ \(TraditionalForm\`f[w]\)]], " is a constant function. More precisely, ", Cell[BoxData[ \(TraditionalForm\`f[w]\ = \ f[u]\)]], " where ", Cell[BoxData[ \(TraditionalForm\`u\)]], " is the suffix of ", Cell[BoxData[ \(TraditionalForm\`w\)]], " of length 3. Such machines are referred to as definite." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(DefiniteQFA[Mb3]\), "\[IndentingNewLine]", \(DefiniteQFA[Mb3, Full \[Rule] True]\)}], "Input"], Cell[TextData[{ "Indeed, the machine can be reset into any state ", Cell[BoxData[ \(TraditionalForm\`q\)]], " by a suitable input ", Cell[BoxData[ \(TraditionalForm\`w\ = \ w(q)\)]], " of length 3, regardless of the current state. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(TransitionFunctionFA[Mb3, del];\)\), "\n", \(Function[\ w, Union[\(del[#, w] &\) /@ Range[8]]]\ /@ \ Words[3]\)}], "Input"], Cell["\<\ This effect is also visible in the defining equations for the \ syntactic monoid. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(PrintEquations[eqn]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Plainly, ", Cell[BoxData[ \(TraditionalForm\`S\)]], " must be aperiodic." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(AperiodicQSG[S]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "More convincing is perhaps a plot of the transformations in ", Cell[BoxData[ \(TraditionalForm\`S\)]], ". The following pictures show the first 5 powers of ", Cell[BoxData[ \(TraditionalForm\`t\)]], " for each ", Cell[BoxData[ \(TraditionalForm\`t\ \[Element] \ S\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(pt\ = \(PlotT[#, 5, PlotStyle \[Rule] {0.04, 0.04}, \[IndentingNewLine]DisplayFunction \[Rule] Identity] &\) /@ ToList[S];\)\), "\n", \(\(ShowArray[pt];\)\)}], "Input"], Cell[TextData[{ "The only regular D-class in ", Cell[BoxData[ \(TraditionalForm\`S\)]], " consists of the right nulls in ", Cell[BoxData[ \(TraditionalForm\`S\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(dc = DClassDecomposition[S];\)\), "\n", \(DClassSize[dc, Full \[Rule] True]\ // \ ColumnForm\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(DClassToBlocks[dc\[LeftDoubleBracket]1\[RightDoubleBracket]]\)], "Input",\ AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Star-free Languages", "Subsection"], Cell[TextData[{ "A language is star-free if it is contained in the closure of the finite \ languages under concatenation and Boolean operations union and complement. \ For an alternative characterization, define the extended star height of a \ regular language by induction on regular operations as follows.\n\t\t", Cell[BoxData[ \(TraditionalForm\`h(\[EmptySet])\ = \ \(h(a)\ \ = \ 0\)\)]], "\n\t\t", Cell[BoxData[ \(TraditionalForm\`h(X + Y)\ = \ \(h(X\[VeryThinSpace]Y)\ = \ max(\ h(X), \ h(Y)\ )\)\)]], "\n\t\t", Cell[BoxData[ \(TraditionalForm\`h(\(A\^*\) - X)\ = \ h(X)\)]], "\n \t\t", Cell[BoxData[ \(TraditionalForm\`h(\(X\^*\))\ = \ \(\(h( X)\)\(\ \)\(+\)\(\ \)\(1\)\(\ \ \)\)\)]], " \nThen ", Cell[BoxData[ \(TraditionalForm\`X\)]], " is star-free if and only if ", Cell[BoxData[ \(TraditionalForm\`X\)]], " has extended star height 0. Note that according to the definition ", Cell[BoxData[ \(TraditionalForm\`\(a\^*\)\)]], " is star-free since ", Cell[BoxData[ \(TraditionalForm\`\(a\^*\) = \ \({a, b}\^*\) - \(\({a, b}\^*\) \(b\)\(\ \)\({a, b}\^*\)\(\ \)\)\)]], ".\nBy a theorem of Schutzenberger the syntactic monoid of a regular \ language is aperiodic and only if the language is star-free. Here a semigroup \ is aperiodic if it satisfies an equation ", Cell[BoxData[ \(TraditionalForm\`x\^\(\(\ \)\(n\)\) = x\^\(\(\ \)\(n + 1\)\)\)]], " for some ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". This condition can be tested using the command ", ButtonBox["AperiodicQSG", ButtonStyle->"AddOnsLink"], ".\n\nWe will see that the following language ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is star-free, though this fact is less than obvious from the rational \ expression that defines it:\n\t", Cell[BoxData[ \(TraditionalForm\`L\ \ = \ \ \(\((\ a\[VeryThinSpace]b\ + \ b\[VeryThinSpace]a\ )\)\^*\)\)]], ".\nWe compute the minimal automaton for L, the syntactic semigroup and the \ defining relations." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m = MinimizeFA[RegularExpressionToFA[RES[ab + ba], {a, b}]];\)\), "\n", \(\({S, wit, eqn} = SyntacticSG[m, Equations \[Rule] True];\)\), "\n", \(S\ // \ Length\), "\n", \(PrintWitnesses[S, wit]\)}], "Input"], Cell[TextData[{ "The constant function with witness ", Cell[BoxData[ FormBox[ StyleBox["aaa", FontSlant->"Italic"], TraditionalForm]]], " is a null in ", Cell[BoxData[ \(TraditionalForm\`S\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(NullSG[S]\)], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\(dc = DClassDecomposition[S];\)\), "\n", \(DClassSize[dc, Full \[Rule] True]\ // \ ColumnForm\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "To display the ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes as a set of words rather than their images in the syntactic \ semigroup we can use the list of witnesses produced by command ", StyleBox["SyntacticSG", "MR"], ". Note that the order of ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes as well as their internal order depends on the algorithm used to \ generate them. You may have to adjust the number of the ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class if the implementation of the algorithms changes. Pick the ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class with dimensions ", Cell[BoxData[ \(TraditionalForm\`3\[Cross]3\[Cross]1\)]], " and display it in witness form. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(WitnessFunction[h, S, wit];\)\), "\[IndentingNewLine]", \(\(DClassToBlocks[dc\[LeftDoubleBracket]2\[RightDoubleBracket]]\ // \ h\)\ // \ MatrixForm\)}], "Input", AspectRatioFixed->True], Cell["\<\ To transform the first row into the third we can use the following \ left multipliers:\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(h[SolveSG[T[1, 3, 3, 3], T[3, 1, 3, 3], S, Where \[Rule] Left]]\), "\n", \(h[SolveSG[T[2, 3, 3, 3], T[3, 2, 3, 3], S, Where \[Rule] Left]]\), "\n", \(h[SolveSG[T[4, 3, 3, 3], T[3, 4, 3, 3], S, Where \[Rule] Left]]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "To see that both ", Cell[BoxData[ \(TraditionalForm\`b\)]], " and ", Cell[BoxData[ FormBox[ StyleBox["bba", FontSlant->"Italic"], TraditionalForm]]], " work properly we have to consider the defining relations for ", Cell[BoxData[ \(TraditionalForm\`S\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(PrintEquations[eqn]\)], "Input", AspectRatioFixed->True], Cell["Thus, for example, ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(WordReduce[babba, eqn]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "For the opposite direction, multiply by ", Cell[BoxData[ \(TraditionalForm\`a\)]], " or ", Cell[BoxData[ FormBox[ StyleBox["baa", FontSlant->"Italic"], TraditionalForm]]], " on the left:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(h[SolveSG[T[3, 1, 3, 3], T[1, 3, 3, 3], S, Where \[Rule] Left]]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(WordReduce[baabba, eqn]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Similarly, multiplication by ", Cell[BoxData[ \(TraditionalForm\`a\)]], " on the right transforms column three into column one and so on. The \ command ", StyleBox["AperiodicQSG", "MR"], " tests whether a given semigroup is aperiodic. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(\(m\ // \ ToGeneratorsFA\)\ // \ GenerateSG\)\ // \ AperiodicQSG\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "As an example for a language that fails to be aperiodic let us return to \ the even-even language over alphabet ", Cell[BoxData[ \(TraditionalForm\`{a, b}\)]], " from above. As we have seen, the product machine of two mod-counters is \ the minimal automaton. Let us compute an initial segment of the syntactic \ congruence relation. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(M = IntersectionFA[\[IndentingNewLine]\t CounterDFA[a, 0, 2, Modulus \[Rule] 2], CounterDFA[b, 0, 2, Modulus \[Rule] 2]]; cong = LanguageSort[SyntacticCongruence[M, \(-5\)]];\), "\n", \(cong\ // \ ColumnForm\)}], "Input", AspectRatioFixed->True], Cell["\<\ The congruence classes are determined by the parity of the words.\ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(parikh[w_] := \((Mod[#1, 2] &)\) /@ ParikhVector[w, {a, b}];\)\), "\n", \(Union /@ Map[parikh, cong, {2}]\ // \ ColumnForm\)}], "Input", AspectRatioFixed->True], Cell["\<\ Correspondingly, the syntactic monoid has exactly four \ elements.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\({S, wit, eqn} = SyntacticSG[M, Equations \[Rule] True];\)\), "\n", \(S\ // \ ColumnForm\)}], "Input"], Cell[TextData[{ "Semigroup ", Cell[BoxData[ \(TraditionalForm\`S\)]], " really is a group. Proof by pictures:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(\(PlotT[#, 6, PlotStyle \[Rule] {0.04, 0.04}, DisplayFunction \[Rule] Identity] &\) /@ ToList[S];\)\), "\[IndentingNewLine]", \(\(ShowArray[%];\)\)}], "Input"], Cell[TextData[{ "Or we might compute the ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-class of some element in ", Cell[BoxData[ \(TraditionalForm\`S\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(HClassT[S\[LeftDoubleBracket]1\[RightDoubleBracket], S]\)], "Input", AspectRatioFixed->True], Cell["Here are the witnesses:", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(PrintWitnesses[S, wit]\)], "Input", AspectRatioFixed->True], Cell["And the defining equations.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(PrintEquations[eqn]\)], "Input", AspectRatioFixed->True], Cell["\<\ Hence the syntactic semigroup S is a nontrivial abelian group and \ therefore fails to be aperiodic. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(AperiodicQSG[S]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Locally Testable Languages", "Subsection"], Cell[TextData[{ "A language L is ", StyleBox["locally testable", FontColor->RGBColor[0, 0, 1]], " if it is a finite Boolean combination of languages of the form \n\t", Cell[BoxData[ \(TraditionalForm\`w\ \(\[CapitalSigma]\^*\), \ \(\[CapitalSigma]\^*\) w\)]], " or ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\ \ w\ \ \[CapitalSigma]\^\(\(*\)\(\ \)\)\)]], "\nwhere ", Cell[BoxData[ \(TraditionalForm\`F\)]], " is finite. Thus, every locally testable language is star-free (but not \ conversely, the language ", Cell[BoxData[ \(TraditionalForm\`\(\((ab + ba)\)\^*\)\)]], " from above is a counterexample). An important example of locally \ testable languages are finite complement languages: languages of the form ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\^\(\(*\)\(\ \)\) - \ \(\ \[CapitalSigma]\^*\)\ F\ \ \[CapitalSigma]\^\(\(*\)\(\ \)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`F\)]], " is finite. \nAnother way to describe these languages is to think of a \ window of fixed width being moved a across a word. Membership in a locally \ testable language can be determined by sliding a window of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], " across a word, and observing the factors that one sees. More precisely, \ write ", Cell[BoxData[ \(TraditionalForm\`\(fact\_n\)(w)\)]], " for the collection of all factors of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], " of ", Cell[BoxData[ \(TraditionalForm\`w\)]], ", and likewise ", Cell[BoxData[ \(TraditionalForm\`pref\_n\)]], "(w) and ", Cell[BoxData[ \(TraditionalForm\`\(suff\_n\)(w)\)]], " for the prefix and suffix of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], " (if it exists). We obtain a congruence ", Cell[BoxData[ \(TraditionalForm\`\( \[Congruent] \_n\)\)]], " of finite index on ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\^\(\(\ \)\(*\)\)\)]], "by setting\n\t", Cell[BoxData[ \(TraditionalForm\`u\ \( \[Congruent] \_n\)\ v\ \[DoubleLeftRightArrow] \ \(fact\_n\)( u)\ = \ \(\(fact\_n\)(v)\ \ \[And] \ \(pref\_\(n - 1\)\)( u)\ = \ \(\(\(pref\_\(n - 1\)\)( v)\ \ \[And] \ \(suff\_\(n - 1\)\)( u)\)\(\ \)\(=\)\(\ \)\(\(suff\_\(n - 1\)\)( v)\)\(\ \)\)\)\)]], ".\nA language is locally testable if it is saturated by ", Cell[BoxData[ \(TraditionalForm\`\( \[Congruent] \_n\)\)]], " for some ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". \nOne can show that a language is locally testable if and only if its \ syntactic semigroup is locally idempotent and locally commutative: for any \ idempotent ", Cell[BoxData[ \(TraditionalForm\`e\)]], " the subsemigroup ", Cell[BoxData[ \(TraditionalForm\`e\ S\ e\)]], " must be idempotent and commutative.\nAs an example, let us consider the \ language ", Cell[BoxData[ \(TraditionalForm\`L\ \[SubsetEqual] \ \({a, b}\^*\)\)]], " containing a factor ", Cell[BoxData[ FormBox[ StyleBox["aaa", FontSlant->"Italic"], TraditionalForm]]], " or ", Cell[BoxData[ FormBox[ StyleBox["bbb", FontSlant->"Italic"], TraditionalForm]]], ", but no factor ", Cell[BoxData[ FormBox[ StyleBox["abab", FontSlant->"Italic"], TraditionalForm]]], ":\n\t", Cell[BoxData[ FormBox[ RowBox[{"L", " ", "=", " ", RowBox[{ RowBox[{\(\[CapitalSigma]\^*\), RowBox[{"{", RowBox[{ StyleBox["aaa", FontSlant->"Italic"], ",", StyleBox["bbb", FontSlant->"Italic"]}], "}"}], " ", \(\[CapitalSigma]\^*\)}], " ", "-", " ", RowBox[{\(\[CapitalSigma]\^*\), StyleBox["abab", FontSlant->"Italic"], " ", \(\[CapitalSigma]\^\(\(*\)\(\ \)\)\)}]}]}], TraditionalForm]]], "\nIt is straightforward to construct an automaton for this language from \ ", ButtonBox["WordToFA", ButtonStyle->"AddOnsLink"], " and Boolean operations." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m1\ = \ WordToFA[aaa, 2, Type \[Rule] "\", Full \[Rule] True];\)\), "\n", \(\(m2\ = \ WordToFA[bbb, 2, Type \[Rule] "\", Full \[Rule] True];\)\), "\n", \(\(m3\ = \ WordToFA[abab, 2, Type \[Rule] "\", Full \[Rule] True];\)\), "\n", \(m = MinimizeFA[\ ComplementFA[\ \ UnionFA[\ m1, m2], \ m3\ ]\ ]\)}], "Input"], Cell["\<\ We can perform a simple validation by checking a few strings in the \ language.\ \>", "Text"], Cell[BoxData[ \(L\ = \ Flatten@LanguageFA[\ m, \ \(-6\)\ ]\)], "Input"], Cell[BoxData[{ \(L\ // \ Length\), "\[IndentingNewLine]", \(Select[L, StringMatchQ[#, "\<*aaa*\>"] || StringMatchQ[#, "\<*bbb*\>"] &]\ // \ Length\), "\[IndentingNewLine]", \(Select[L, StringMatchQ[#, "\<*abab*\>"] &]\ // \ Length\)}], "Input"], Cell["\<\ The syntactic semigroup has 45 elements, most of them being \ irregular.\ \>", "Text"], Cell[BoxData[{ \(\({S, wit, eq, \ dcl\ } = SyntacticSG[m, DClasses \[Rule] True];\)\), "\n", \(S\ // \ Length\)}], "Input"], Cell[TextData[{ "The semigroup is aperiodic, and there are 3 regular ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(DClassSize[dcl, Full \[Rule] True]\ // \ ColumnForm\)], "Input", AspectRatioFixed->True], Cell["There are 24 idempotents.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(IdemSG[S]\ // \ Length\)], "Input"], Cell[BoxData[{ \(LocallyIdempotentQSG[S]\), "\[IndentingNewLine]", \(LocallyCommutativeQSG[S]\)}], "Input"], Cell[TextData[{ "However, if we insist that the block ", Cell[BoxData[ FormBox[ StyleBox["aaa", FontSlant->"Italic"], TraditionalForm]]], " appear before the block ", StyleBox["bbb", FontSlant->"Italic"], " we lose local testability." }], "Text"], Cell[BoxData[{ \(\(m1\ = \ WordToFA[aaa, 2, Type \[Rule] "\", Full \[Rule] True];\)\), "\n", \(\(m2\ = \ WordToFA[bbb, 2, Type \[Rule] "\", Full \[Rule] True];\)\), "\n", \(\(m3\ = \ WordToFA[abab, 2, Type \[Rule] "\", Full \[Rule] True];\)\), "\n", \(m = MinimizeFA[\ ComplementFA[\ \ ConcatenateFA[\ m1, m2], \ m3\ ]\ ]\)}], "Input"], Cell["\<\ The syntactic semigroup here has size 101 and promptly fails the \ tests. \ \>", "Text"], Cell[BoxData[{ \(\(S = SyntacticSG[m];\)\), "\n", \(S\ // \ Length\)}], "Input"], Cell[BoxData[{ \(LocallyIdempotentQSG[S]\), "\[IndentingNewLine]", \(LocallyCommutativeQSG[S]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Piecewise Testable Languages", "Subsection"], Cell[TextData[{ "Write ", Cell[BoxData[ \(TraditionalForm\`\(subs\_n\)(w)\)]], " for the collection of all subwords (scattered subsequences, not factors) \ of ", Cell[BoxData[ \(TraditionalForm\`w\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`subs\_n\)]], " induces a congruence ", Cell[BoxData[ \(TraditionalForm\`\( \[Congruent] \_n\)\)]], " of finite index on ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\^\(\(\ \)\(*\)\)\)]], ". A language is piecewise testable if it is saturated by ", Cell[BoxData[ \(TraditionalForm\`\( \[Congruent] \_n\)\)]], " for some ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". Equivalently, the language belongs to the Boolean algebra generated by \ sets of the form ", Cell[BoxData[ \(TraditionalForm\`{\ w\ || \ x\ \ | \ \ x\ \[Element] \ \(\[CapitalSigma]\^*\)}\)]], " where ", Cell[BoxData[ \(TraditionalForm\` || \)]], " denotes the shuffle operation. One can show that a language is piecewise \ testable if and only if its syntactic semigroup is ", Cell[BoxData[ \(TraditionalForm\`J\)]], "-trivial.\nAs an example, let us consider the language ", Cell[BoxData[ \(TraditionalForm\`L\ \[SubsetEqual] \ \({a, b}\^*\)\)]], " that contains ", Cell[BoxData[ FormBox[ StyleBox["aab", FontSlant->"Italic"], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ StyleBox["bba", FontSlant->"Italic"], TraditionalForm]]], " as subwords, but not ", Cell[BoxData[ FormBox[ StyleBox["bbba", FontSlant->"Italic"], TraditionalForm]]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(m = MinimizeFA[\ \[IndentingNewLine]ComplementFA[\ \ IntersectionFA[\ SubwordDFA[\ aab, 2], SubwordDFA[bba, 2]], \[IndentingNewLine]\t\t\t\ \ SubwordDFA[\ bbba, \ 2\ ]\ ]\ ]\)], "Input"], Cell["A small sanity check.", "Text"], Cell[BoxData[ \(L\ = \ Flatten@LanguageFA[\ m, \ \(-6\)\ ]\)], "Input"], Cell[BoxData[{ \(WordBinomial[\ L, aab]\), "\[IndentingNewLine]", \(WordBinomial[\ L, bba]\), "\[IndentingNewLine]", \(WordBinomial[\ L, bbba]\)}], "Input"], Cell["\<\ The syntactic semigroup has 26 elements, most of them being \ irregular.\ \>", "Text"], Cell[BoxData[{ \(\({S, wit, eq, \ dcl\ } = SyntacticSG[m, DClasses \[Rule] True];\)\), "\n", \(S\ // \ Length\)}], "Input"], Cell[TextData[{ "There are 3 regular ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes of size 1 each." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(DClassSize[dcl, Full \[Rule] True]\ // \ ColumnForm\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Counting Subwords", "Subsection"], Cell[TextData[{ "The command ", ButtonBox["SubwordCounterDFA", ButtonStyle->"AddOnsLink"], " constructs a DFA for the language of all words that contain a fixed \ number of occurrences of a given words as subwords (scattered subsequences, \ not factors):\n\t", Cell[BoxData[ \(TraditionalForm\`L(w, p)\ \ = \ \ {\ \ \ x\ \ | \ \ WordBinomial[x, w]\ \ = \ \ p\ }\)]], ".\nSimilarly we can build a DFA for \n\t", Cell[BoxData[ \(TraditionalForm\`L(w, r, p)\ \ = \ \ {\ \ \ x\ \ | \ \ WordBinomial[x, w]\ \ = \ \ r\ \ mod\ p\ }\)]], ".\nNote that the number of states in the DFA for ", Cell[BoxData[ \(TraditionalForm\`L(w, p)\)]], " is bounded by ", Cell[BoxData[ \(TraditionalForm\`\((p + 2)\)\^\(\(|\)\(w\)\(|\)\)\)]], StyleBox[" ", FontVariations->{"CompatibilityType"->"Superscript"}], " and in the machine for ", Cell[BoxData[ \(TraditionalForm\`L(w, r, p)\)]], " by ", Cell[BoxData[ \(TraditionalForm\`p\^\(\(|\)\(w\)\(|\)\)\)]], ". Option ", StyleBox["Normalize->1", "MR"], " preserves the states as length ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(w\)\(|\)\)\)]], " vectors over ", Cell[BoxData[ \(TraditionalForm\`{0, 1, .. , p, p + 1}\)]], " (", Cell[BoxData[ \(TraditionalForm\`{0, 1, .. , p - 1}\)]], ", respectively). Generating a trace of a computation shows how the \ components of the state vector are updated. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m = SubwordCounterDFA[abab, 3, {a, b}, Normalize \[Rule] 1];\)\), "\n", \(Size[m]\), "\n", \(States[m]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\(w = bbaababbbb;\)\), "\n", \(TableForm[AcceptQFA[m, w, DoTrace \[Rule] True]]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Let us take a closer look at the language ", Cell[BoxData[ \(TraditionalForm\`L(a\[VeryThinSpace]b, 2)\)]], ":" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(m0 = SubwordCounterDFA[ab, 2, {a, b}, Normalize \[Rule] 1]\)], "Input", AspectRatioFixed->True], Cell["We minimize and generate a few words in the language. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m1 = MinimizeFA[m0, Normalize \[Rule] 2];\)\), "\n", \(\(L = LanguageFA[m1, \(-6\)];\)\), "\n", \(L\ // \ ColumnForm\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "It looks like ", Cell[BoxData[ \(TraditionalForm\`\(b\^*\)\ {\ a\[VeryThinSpace]a\[VeryThinSpace]b, \ a\[VeryThinSpace]b\[VeryThinSpace]b\ }\ \(a\^*\)\ \ = \ \ L( a\[VeryThinSpace]b, 2)\)]], ". We can verify this guess as follows:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(mm = BuildDFA[ L\[LeftDoubleBracket]4\[RightDoubleBracket], {a, b}];\)\), "\n", \(\(ma = BuildStarDFA[a, {a, b}];\)\), "\n", \(\(mb = BuildStarDFA[b, {a, b}];\)\), "\n", \(\(mmm = ToDFA[ConcatenateFA[mb, mm, ma]];\)\), "\n", \(EquivalentQFA[m1, mmm]\)}], "Input", AspectRatioFixed->True], Cell["\<\ It is interesting to take a closer look at the state set of \ m1.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(States[m1]\ // \ ColumnForm\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Note that the only input words that leave machine ", Cell[BoxData[ \(TraditionalForm\`m0\)]], " in state ", Cell[BoxData[ \(TraditionalForm\`{1, 1}\)]], " and ", Cell[BoxData[ \(TraditionalForm\`{2, 0}\)]], ", respectively, are ", Cell[BoxData[ FormBox[ StyleBox["ab", FontSlant->"Italic"], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ StyleBox["aa", FontSlant->"Italic"], TraditionalForm]]], ". Both lead to state 3 in ", Cell[BoxData[ \(TraditionalForm\`m1\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(WordBinomial[#, ab, DoTrace \[Rule] True] &\) /@ {ab, aa}\ // \ ColumnForm\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(AcceptQFA[m1, #, DoTrace \[Rule] True] &\) /@ {ab, aa}\ // \ ColumnForm\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "We can use the frontier construction to check that ", " ", Cell[BoxData[ FormBox[ StyleBox["ab", FontSlant->"Italic"], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ StyleBox["aa", FontSlant->"Italic"], TraditionalForm]]], " indeed lead to the same state in m1. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\({fr, F} = ToFrontierDFA[m1];\)\), "\n", \({fr, F}\ // \ \(Curry[TableForm]\)[ TableSpacing \[Rule] {2, 1}]\)}], "Input", AspectRatioFixed->True], Cell["\<\ All the four letter inputs in the frontier except the third lead to \ the trap state in m2.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(W = Drop[First /@ fr, 2];\)\), "\n", \(\(Last /@ AcceptQFA[m1, #, DoTrace \[Rule] True] &\) /@ W\ // \ ColumnForm\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "One can show that languages of the form ", Cell[BoxData[ \(TraditionalForm\`L(w, k)\)]], " are piecewise testable. To see this note that ", Cell[BoxData[ \(TraditionalForm\`L(w, k)\ = \ L(w, \(\(\[GreaterEqual]\)\(k\)\))\ \ - \ \ L( w, \(\(>\)\(k\)\))\)]], ". Any language of the form ", Cell[BoxData[ \(TraditionalForm\`L(w, \(\(>\)\(i\)\))\)]], " is upward closed with respect to subwords. Since any set of pairwise \ incomparable words must be finite, the language ", Cell[BoxData[ \(TraditionalForm\`L(w, i)\)]], " can be written as a finite union of languages ", Cell[BoxData[ \(TraditionalForm\`L(u, 1)\)]], " (all words ", Cell[BoxData[ \(TraditionalForm\`x\)]], " containing at least one subword ", Cell[BoxData[ \(TraditionalForm\`u\)]], "). Hence ", Cell[BoxData[ \(TraditionalForm\`L(w, k)\)]], " is in the boolean algebra generated by these languages. As a consequence, \ the syntactic semigroup of ", Cell[BoxData[ \(TraditionalForm\`L(w, k)\)]], " must be ", Cell[BoxData[ \(TraditionalForm\`J\)]], "-trivial. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\({S, wit, eq} = SyntacticSG[m1, Equations \[Rule] True];\)\), "\n", \(\(eq = SimplifyEquations[S, wit, eq];\)\), "\n", \(PrintEquations[eq]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(WordReduce[bbbbabbaaaa, eq, DoTrace \[Rule] True]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "The three regular ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes consist of one idempotent each." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(dc = DClassDecomposition[S];\)\), "\n", \(ColumnForm[DClassSize[dc, Full \[Rule] True]]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(DClassToBlocks[dc]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Here is an example for a machine counting subwords modulo ", Cell[BoxData[ \(TraditionalForm\`p\)]], ". We construct m5 to be the minimal automaton for ", Cell[BoxData[ \(TraditionalForm\`L(a\[VeryThinSpace]b, 0, 5)\)]], " over alphabet ", Cell[BoxData[ \(TraditionalForm\`{a, b}\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m5 = MinimizeFA[ SubwordCounterDFA[ab, 0, {a, b}, Modulus \[Rule] 5]];\)\), "\n", \(m5\ // \ Size\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(L7 = LanguageFA[m5, 7]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(WordBinomial[L7, ab]\)], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\({S5, wit, eqn} = SyntacticSG[m5, Equations \[Rule] True];\)\), "\n", \(S5\ // \ Length\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "By a theorem by Eilenberg and Sch\[UDoubleDot]tzenberger the boolean \ algebra generated by the languages ", Cell[BoxData[ \(TraditionalForm\`L(w, r, p)\)]], " corresponds to the variety of ", Cell[BoxData[ \(TraditionalForm\`p\)]], "-groups. Thus, ", Cell[BoxData[ \(TraditionalForm\`S5\)]], " should be a group. Indeed, ", Cell[BoxData[ \(TraditionalForm\`S5\)]], " is a subgroup of ", Cell[BoxData[ \(TraditionalForm\`S(25)\)]], ", the full symmetric group on 25 elements. The most efficient way to \ establish this is to check that the generators of ", Cell[BoxData[ \(TraditionalForm\`S5\)]], " are bijections. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Alternatively we can generate the ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-class of any element in S5 and verify that it is the whole semigroup. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(hc = HClassT[S5\[LeftDoubleBracket]17\[RightDoubleBracket], S5];\)\), "\n", \(hc\ // \ Length\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Note that the defining equations for S5 have the following property. Let \ \n\t", Cell[BoxData[ \(TraditionalForm\`t( w)\ \ := \ \ \(\(|\)\(w\)\(|\)\(\ \ \)\(\(+\ \ WordBinomial[w, ab]\)\ \ \ mod\ 5\)\)\)]], ". \nThen for any equation ", Cell[BoxData[ \(TraditionalForm\`u\ = \ v\)]], " we have ", Cell[BoxData[ \(TraditionalForm\`t(u)\ = \ t(v)\)]], ". Other than the trivial equations ", Cell[BoxData[ \(TraditionalForm\`aaaaa\ = \ 1\)]], " and ", Cell[BoxData[ \(TraditionalForm\`bbbbb\ = \ 1\)]], " it is rather tedious to find such relations by hand. Here are the \ defining relations for S5: " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(eqs\ = \ SimplifyEquations[S5, wit, eqn];\)\), "\[IndentingNewLine]", \(PrintEquations[eqs, Algebraic \[Rule] True]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "The ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class decomposition show that there is only on ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-class, namely the whole (semi-)group." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\({S, wit, eq, dc} = SyntacticSG[m5, DClasses \[Rule] True];\)\), "\n", \(Length[S]\), "\n", \(DClassSize[dc, Full \[Rule] True]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Reversal", "Subsection"], Cell[TextData[{ "For any regular language ", Cell[BoxData[ \(TraditionalForm\`L\)]], " the reversal language ", Cell[BoxData[ \(TraditionalForm\`L\^\(\(\ \)\(r\)\)\ = \ {\ x\^\(\(\ \)\(r\)\)\ | \ x\ \[Element] \ L}\)]], " is again regular. One might wonder what the relationship between ", Cell[BoxData[ \(TraditionalForm\`Syn(L)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`Syn(L\^r)\)]], " is. Note that the size of the minimal DFA for ", Cell[BoxData[ \(TraditionalForm\`L\)]], " and ", Cell[BoxData[ \(TraditionalForm\`L\^r\)]], " can differ exponentially, so a direct attack on this question using the \ corresponding transformation semigroups may be difficult." }], "Text"], Cell[BoxData[{ \(\(M = MinimizeFA[IthSymbolFA[b, \(-4\), {a, b}]];\)\), "\n", \(\(Mr = MinimizeFA[IthSymbolFA[b, 4, {a, b}]];\)\), "\n", \(Size[{M, Mr}]\)}], "Input"], Cell["Both syntactic monoids have size 30.", "Text"], Cell[BoxData[{ \(\({S, W, eqn, dcl} = SyntacticSG[\ M, DClasses \[Rule] True];\)\), "\n", \(\({Sr, Wr, eqnr, dclr} = SyntacticSG[\ Mr, DClasses \[Rule] True];\)\), "\n", \(Length[S]\), "\n", \(Length[Sr]\)}], "Input"], Cell[TextData[{ "And the unique regular ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class has size 16, but note the difference in dimensions." }], "Text"], Cell[BoxData[{ \(DClassSize[dcl, Full \[Rule] True]\), "\[IndentingNewLine]", \(DClassSize[dclr, Full \[Rule] True]\)}], "Input"], Cell[TextData[{ "The elements of this ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class are the idempotents, which happen to the right (and left) nulls \ here, respectively." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Sort@IdemSG[S]\ === \ Sort@RightNullSG[S] === \ Sort@\(Flatten@DClassToBlocks[dcl]\)\)], "Input"], Cell[BoxData[ \(Sort@IdemSG[Sr] === Sort@LeftNullSG[Sr] === \ Sort@\(Flatten@DClassToBlocks[dclr]\)\)], "Input"], Cell[TextData[{ "The best way to establish a connection is to use the characterization in \ terms of the syntactic congruence ", Cell[BoxData[ \(TraditionalForm\`\(~\_L\)\)]], ". It is easy to see that ", Cell[BoxData[ \(TraditionalForm\`x\ \(~\_L\)y\ \ \[DoubleLeftRightArrow] \ \ \(x\^\(\ \(\ \)\(r\)\)\)\ \(~\_\(L\^r\)\)\ \(y\^\(\(\ \)\(r\)\)\)\)]], ", so the map ", Cell[BoxData[ \(TraditionalForm\`x\ \ \[RightTeeArrow] \ x\^\(\(\ \)\(r\)\)\)]], " is an anti-isomorphism between the two semigroups. Let's verify this. We \ construct the corresponding map ", Cell[BoxData[ \(TraditionalForm\`h\ : \ S\ \[LongRightArrow]\ S\_\(\(\ \)\(r\)\)\)]], " and verify that it really is an anti-isomorphism." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(ClearAll[h]\), "\n", \(SetAttributes[h, Listable]\), "\n", \(h[t_T] := Sr\[LeftDoubleBracket]\(Position[Wr, StringReverse[ W\[LeftDoubleBracket]\(Position[S, t]\)\[LeftDoubleBracket]1, 1\[RightDoubleBracket]\[RightDoubleBracket]]]\)\ \[LeftDoubleBracket]1, 1\[RightDoubleBracket]\[RightDoubleBracket]\)}], "Input"], Cell[BoxData[{ \(S[\([1]\)]\), "\[IndentingNewLine]", \(%\ // \ h\)}], "Input", AspectRatioFixed->True], Cell["\<\ Here is a brute-force computation, ignoring the fact that we have \ access to the generators.\ \>", "Text"], Cell[BoxData[{ \(\(cp = CartesianProduct[ToList[S], ToList[S]];\)\), "\n", \(cp\ // \ Length\)}], "Input"], Cell[BoxData[ \(h[\ Apply[\ NonCommutativeMultiply, \ cp, \ 1\ ]]\ === Apply[\ NonCommutativeMultiply, h[Reverse\ /@ \ cp], \ 1\ ]\)], "Input"], Cell["A slightly more elegant test, using the generators.", "Text"], Cell[BoxData[ \(Table[\ h[S\[LeftDoubleBracket]i\[RightDoubleBracket] ** S\[LeftDoubleBracket]j\[RightDoubleBracket]] === h[S\[LeftDoubleBracket]j\[RightDoubleBracket]] ** h[S\[LeftDoubleBracket]i\[RightDoubleBracket]], {i, 2}, {j, 2}]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Rees Semigroups", "Subsection"], Cell[TextData[{ "We can construct a simple mock-up of the Rees matrix representation of ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-classes by overloading ", ButtonBox["NonCommutativeMultiply", ButtonStyle->"RefGuideLink"], ". Let's use the ", Cell[BoxData[ \(TraditionalForm\`6\ \[Cross]\ 4\ \[Cross]\ 6\)]], " ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class in ", Cell[BoxData[ \(TraditionalForm\`T\_4\)]], ". " }], "Text"], Cell[BoxData[ \(\({S, W, eq, dcl}\ = \ TransformationSG[4, DClasses \[Rule] True];\)\)], "Input"], Cell[BoxData[ \(DClassSize[dcl, Full \[Rule] True]\)], "Input"], Cell[TextData[{ "First, we determine the positions of the idempotent elements in ", Cell[BoxData[ \(TraditionalForm\`D\_1\)]], "." }], "Text"], Cell[BoxData[{ \(\(D1\ = \ DClassToBlocks[dcl[\([1]\)]];\)\), "\n", \(id\ = Select[\ Flatten[D1], IdemSG\ ]\)}], "Input"], Cell[BoxData[{ \(\(pos\ = \ FlattenOne[\(Position[D1, #] &\)\ /@ \ id];\)\), "\n", \(\(Fold[\ \ ReplacePart[#1, 1, #2] &, Array[0 &, {6, 4}], Most /@ pos]\ // \ \(Curry[PlotMatrix]\)[ GridLines \[Rule] True];\)\)}], "Input"], Cell[TextData[{ "For simplicity, let's permute the rows so that an idempotent appears in \ position ", Cell[BoxData[ \(TraditionalForm\`\((1, 1)\)\)]], "." }], "Text"], Cell[BoxData[{ \(\(dc\ = \ dcl[\([1]\)];\)\), "\n", \(\(dc\ = \ ReplacePart[dc, \(dc[\([1]\)]\)[\([{2, 1, 3, 4, 5, 6}]\)], 1];\)\), "\n", \(\(D1\ = \ DClassToBlocks[dc];\)\), "\n", \(\(H\ = \ D1[\([1, 1]\)];\)\), "\n", \(\(id\ = Select[\ Flatten[D1], IdemSG\ ];\)\), "\[IndentingNewLine]", \(\(Position[D1, #] &\)\ /@ \ id\)}], "Input"], Cell[TextData[{ "We extract the left- and right-multipliers and the ", Cell[BoxData[ \(TraditionalForm\`H\)]], "-class ", Cell[BoxData[ \(TraditionalForm\`H\_11\)]], ". Then we build the Rees matrix (which we will use as a global \ parameter)." }], "Text"], Cell[BoxData[{ \(ClearAll[lm, rm, H, ReesP]\), "\n", \(\({lm, rm, H}\ = \ ToList[dc];\)\), "\[IndentingNewLine]", \(\(ReesP[i_, j_]\ := \ \(ReesP[i, j]\ = \ \[IndentingNewLine]Module[\ {HH}, \[IndentingNewLine]\t HH\ = \ lm[\([i]\)]\ ** \ H\ ** \ rm[\([j]\)]; \[IndentingNewLine]\t If[\ Select[HH, IdemSG] === {}, \[IndentingNewLine]\t\t0, \ \[IndentingNewLine]\t\trm[\([j]\)] ** lm[\([i]\)]\[IndentingNewLine]\t]\[IndentingNewLine]]\);\)\), \ "\n", \(Apply[\ ReesP, \ Table[{i, j}, {i, 6}, {j, 4}], {2}]\ // \ MatrixForm\)}], "Input"], Cell["\<\ Same matrix with witnesses rather than the actual \ transformations.\ \>", "Text"], Cell[BoxData[{ \(WitnessFunction[h, S, W]\), "\[IndentingNewLine]", \(\(h[0]\ = \ 0;\)\), "\[IndentingNewLine]", \(\(Apply[\ ReesP, \ Table[{i, j}, {i, 6}, {j, 4}], {2}]\ // \ h\)\ // \ MatrixForm\)}], "Input"], Cell[TextData[{ "We use the constructor ", StyleBox["Rees", "MR"], " to implement the triples ", Cell[BoxData[ \(TraditionalForm\`\((i, g, j)\)\)]], " for the Rees representation and overload NonCommutativeMultiply to behave \ properly with respect to the adjoined 0." }], "Text"], Cell[BoxData[{ \(\(Unprotect[NonCommutativeMultiply];\)\), "\[IndentingNewLine]", \(\(Rees[i_, g_, j_] ** Rees[ii_, gg_, jj_]\ := \ If[\ ReesP[j, ii] =!= \ 0, \ Rees[\ i, g\ ** \ ReesP[j, ii] ** gg\ , jj], \ 0\ ];\)\), "\[IndentingNewLine]", \(\(0\ ** \ _\ := \ 0;\)\), "\[IndentingNewLine]", \(\(_\ ** \ 0\ := \ 0;\)\)}], "Input"], Cell[TextData[{ "Here is a sample multiplication for two elements in the ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class." }], "Text"], Cell[BoxData[ \(Rees[1, H[\([2]\)], 3] ** Rees[3, H[\([3]\)], 4]\)], "Input"], Cell["\<\ Here are the three transformations in the last evaluation, \ multiplied directly.\ \>", "Text"], Cell[BoxData[{ \(t1\ = \ \(\(\(lm[\([1]\)]\ ** \ H[\([2]\)]\)\ ** \ rm[\([3]\)]\)\(\ \ \)\)\), "\[IndentingNewLine]", \(t2\ = \ lm[\([3]\)]\ ** \ H[\([3]\)]\ ** \ rm[\([4]\)]\)}], "Input"], Cell[BoxData[ \(t1\ ** \ t2\ === \ \(\(\(lm[\([1]\)]\ ** \ T[4, 4, 1, 3]\)\ ** \ rm[\([4]\)]\)\(\ \)\)\)], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Fischer Automata", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Syntactic semigroups", "c:5"}], Cell[CellGroupData[{ Cell["One-Dimensional Cellular Automata", "Subsection"], Cell[TextData[{ "A one-dimensional cellular automaton \[Rho] can be thought of as a \ transducer operating on bi-infinite strings. The finite factors that appear \ in the images of all these strings form a regular language ", Cell[BoxData[ \(TraditionalForm\`L\_\[Rho]\)]], ". In other words, ", Cell[BoxData[ \(TraditionalForm\`L\_\[Rho]\)]], " is the union of all the covers of ", Cell[BoxData[ \(TraditionalForm\`\[Rho](X)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`X\ \[Element] \ \[CapitalSigma]\^\(\(\ \)\(\ \[Infinity]\)\)\)]], ". It is easy to see that these regular languages are extensible, \ factorial and transitive (even strongly transitive). Here a language ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is ", StyleBox["extensible", FontColor->RGBColor[0, 0, 1]], " if ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x\ \[Element] \ L\ \ \(\[Exists] \ a\), b\ \[Element] \ K\ \ \((\ \ a\[VeryThinSpace]x\[VeryThinSpace]b\ \[Element] \ L\ )\)\)]], ", ", StyleBox["factorial", FontColor->RGBColor[0, 0, 1]], " if ", Cell[BoxData[ \(TraditionalForm\`u\ x\ v\ \ \[Element] \ L\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ L\)]], " and ", StyleBox["transitive", FontColor->RGBColor[0, 0, 1]], " if \t", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ u, v\ \[Element] \ L\ \ \(\[Exists] \ x\ \((\ \ u\ x\ v\ \[Element] \ L\ )\)\)\)]], ". \nFischer has shown that for these languages there is a special normal \ form automaton, a deterministic semiautomaton whose states have distinct \ behavior. One algorithmically interesting way to construct this automaton is \ the following:\n- Build the de Bruijn automaton associated with the CA \ \[Rho].\n- Convert this semiautomaton to a DFA.\n- Minimize to obtain the \ minimal DFA ", Cell[BoxData[ \(TraditionalForm\`M\)]], " for ", Cell[BoxData[ \(TraditionalForm\`L\_\[Rho]\)]], ".\n- Extract the subautomaton of the minimal DFA that is determined by the \ unique strongly connected component of ", Cell[BoxData[ \(TraditionalForm\`M\)]], " that has out-transitions only to the sink. \nHere is an example:" }], "Text"], Cell[BoxData[{ \(\(C = CA[3, 2, 91];\)\), "\n", \(ToSA[C]\)}], "Input", AspectRatioFixed->True], Cell["\<\ The minimal DFA has size 16, and the sink is state number 16.\ \>", \ "Text"], Cell[BoxData[{ \(m = MinimizeFA[ToSA[C]]\), "\[IndentingNewLine]", \(m\ // \ TrapStatesFA\)}], "Input", AspectRatioFixed->True], Cell["\<\ We extract the diagram of the machine and compute its strongly \ connected components. In this case, there is only the sink and one other \ SCC.\ \>", "Text"], Cell[BoxData[{ \(\(g = ToGraphFA[m];\)\), "\n", \(scc = StronglyConnectedComponents[g, NonTrivial \[Rule] True]\)}], "Input", AspectRatioFixed->True], Cell["\<\ We can now construct a deterministic semiautomaton mm by \ restricting m to that other component.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(mm = ToSA[SelectFA[m, scc\[LeftDoubleBracket]1\[RightDoubleBracket]]]\)], "Input", AspectRatioFixed->True], Cell["The two semiautomata are equivalent.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(EquivalentQFA[m, mm]\)], "Input", AspectRatioFixed->True], Cell["But the Fischer automaton mm is deterministic.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(DeterministicQFA[mm]\)], "Input", AspectRatioFixed->True], Cell["\<\ In fact, the Fischer automaton is reduced. The minimal automata \ corresponding to the behaviors of the 15 states all have size 16 and are \ non-isomorphic.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(ToClasses[\ Range[15], \ \ MinimizeFA[\ SetInitialFA[mm, #\ ]] &, \ Type \[Rule] Function\ ]\)], "Input"], Cell["\<\ The construction of the minimal Fischer automaton can be \ accomplished by a single command.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(CA[3, 2, 91]\ // \ ToSA\)\ // \ MinimalFischerFA\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Subshifts of Finite Type", "Subsection", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ The complement of any factorial language is a two-sided ideal. \ Trivially, this ideal will have a countable set of generators, but the case \ where finitely many generators exist is particularly interesting. It is \ straightforward to construct a semiautomaton based on a de Bruijn graph that \ accepts the corresponding factorial language.\ \>", "Text"], Cell[BoxData[ \(sa = FiniteComplementSA[{aab, bbb, abba}, 2, Normalize \[Rule] 1]\)], "Input",\ AspectRatioFixed->True], Cell["m = MinimizeFA[sa]", "Input", AspectRatioFixed->True], Cell["LanguageFA[ ComplementFA[m], -5 ]", "Input", AspectRatioFixed->True], Cell[BoxData[ \(\({S, W, eq, dcl} = SyntacticSG[\ m, DClasses \[Rule] True];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(Length[S]\), "\n", \(DClassSize[dcl, Full \[Rule] True]\)}], "Input", AspectRatioFixed->True], Cell["NullSG[S]", "Input", AspectRatioFixed->True], Cell["PrintWitnesses[S,W]", "Input", AspectRatioFixed->True], Cell[TextData[{ "The first ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class consists of a single idempotent." }], "Text"], Cell["\<\ WitnessFunction[ wit, S, W ] DClassToBlocks[dcl\[LeftDoubleBracket]1\[RightDoubleBracket]] // wit // \ MatrixForm\ \>", "Input", AspectRatioFixed->True], Cell["The second one corresponds to elements of rank 2.", "Text"], Cell["\<\ DClassToBlocks[dcl\[LeftDoubleBracket]2\[RightDoubleBracket]] // \ wit // MatrixForm DClassToBlocks[dcl\[LeftDoubleBracket]2\[RightDoubleBracket]] // RankT\ \>", \ "Input", AspectRatioFixed->True], Cell["\<\ The last one consists of the null, whose witness is the length-lex \ minimal forbidden word.\ \>", "Text"], Cell["\<\ DClassToBlocks[dcl\[LeftDoubleBracket]3\[RightDoubleBracket]] // \ wit // MatrixForm DClassToBlocks[dcl\[LeftDoubleBracket]3\[RightDoubleBracket]]\ \>", "Input", AspectRatioFixed->True], Cell["The forbidden words reduce to 0 in the rewrite system.", "Text"], Cell["PrintEquations[SimplifyEquations[S,W,eq]]", "Input", AspectRatioFixed->True], Cell[TextData[{ "Of course, we can recover the ideal base from ", Cell[BoxData[ \(TraditionalForm\`m\)]], "." }], "Text"], Cell[BoxData[ \(mid\ = \ IdealBaseFA[ComplementFA[m]]\)], "Input"], Cell[BoxData[ \(LanguageFA[\ mid, \ Full \[Rule] True\ ]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["0-Minimal Ideals and Minimal Fischer Automata", "Subsection"], Cell[CellGroupData[{ Cell["The Ideal Automaton", "Subsubsection"], Cell[TextData[{ "An entirely different description of the minimal Fischer automaton can be \ obtained by inspecting the syntactic semigroup of the language of the \ cellular automaton. First note that a language ", Cell[BoxData[ \(TraditionalForm\`L\)]], " is factorial if and only if its complement ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\^\(\(\ \)\(*\)\) - \ L\)]], " is a two-sided ideal: every word containing an excluded block is itself \ excluded from ", Cell[BoxData[ \(TraditionalForm\`L\)]], ". Now consider the canonical homomorphism ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\[CapitalSigma]\^*\)\[LongRightArrow]\ S\)]], " where ", Cell[BoxData[ \(TraditionalForm\`S\)]], " is the syntactic semigroup of the language ", Cell[BoxData[ \(TraditionalForm\`L\_\[Rho]\)]], " associated to the CA \[Rho]. Then ", Cell[BoxData[ \(TraditionalForm\`S\ = \ S\^\(\(\ \)\(\[Prime]\)\)\ \[Union] \ {\[Nu]}\)]], " where \[Nu] is a null. The elements of ", Cell[BoxData[ \(TraditionalForm\`S\)]], " of rank at most 2 form a 0-minimal ideal is ", Cell[BoxData[ \(TraditionalForm\`S\)]], ", a ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class together with \[Nu]. The ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-classes of this ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class, augmented by \[Nu], can be used to construct a deterministic \ semiautomaton for ", Cell[BoxData[ \(TraditionalForm\`L\_\[Rho]\)]], " directly.\nHere is an example. The minimal automaton for the language of \ ECA number 61 has 7 states, and generates a syntactic semigroup of size 71." }], "Text"], Cell[BoxData[{ \(m = MinimizeFA[ToSA[CA[3, 2, 61]]]\), "\n", \(\(n = Size[m];\)\), "\n", \(sink\ = \ TrapStatesFA[m, Full \[Rule] False]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Here is the syntactic semigroup and its ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class decomposition." }], "Text"], Cell[BoxData[{ \(\({S, W, eq, dcl} = SyntacticSG[m, DClasses \[Rule] True];\)\), "\n", \(Length[S]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "The sink in ", Cell[BoxData[ \(TraditionalForm\`m\)]], " produces the null-element in ", Cell[BoxData[ \(TraditionalForm\`S\)]], ". " }], "Text"], Cell[BoxData[{ \(\(\[Nu]\ = \ T @@ Table[sink, {n}];\)\), "\n", \(NullSG[S] === \ {\[Nu]}\)}], "Input"], Cell[TextData[{ "We can verify that the range of the syntactic homomorphism is all ", Cell[BoxData[ \(TraditionalForm\`S\)]], " minus the null-element. Note that this computation is brute-force and may \ not work well for other examples." }], "Text"], Cell[BoxData[ \(\(\(SyntacticHomomorphism[f, m]\n \(SS\ = \ \(Rest@\(Flatten@LanguageFA[m, \(-9\)\ ]\)\ // \ f\)\ // \ Union;\)\n Complement[ToList[S], SS]\)\(\ \)\)\)], "Input"], Cell[TextData[{ "Let's take a closer look at the ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class decomposition. The last class is the null element." }], "Text"], Cell[BoxData[ \(DClassSize[\ dcl, \ Full \[Rule] True\ ]\)], "Input", AspectRatioFixed->True], Cell["\<\ Here is a simple test for whether a subset of a semigroup forms an \ two-sided ideal, given generators for the semigroup.\ \>", "Text"], Cell["\<\ IdealQSG[ L_List, g_List ] := \tSubsetQ[ AllTimes[L,g], L ] && SubsetQ[ AllTimes[g,L], L ];\ \>", "Input", AspectRatioFixed->True], Cell[TextData[{ "The first ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class augmented by 0 forms an ideal (the last one is just ", Cell[BoxData[ \(TraditionalForm\`{\[Nu]}\)]], " and of no interest to us)." }], "Text"], Cell[BoxData[ \(Table[\ \[IndentingNewLine]With[\ {id\ = \ Join[Flatten[ DClassToBlocks[ dcl[\([i]\)]]], {\[Nu]}]}, \[IndentingNewLine]\t\tIdealQSG[\ \ id, Last@ToGeneratorsFA[m]\ ]\ ], \ {i, 5}]\)], "Input"], Cell[BoxData[ \(\(id = Join[Flatten[DClassToBlocks[dcl[\([1]\)]]], {\[Nu]}];\)\)], "Input"], Cell[TextData[{ "The witnesses for the ", Cell[BoxData[ \(TraditionalForm\`D\)]], "-class." }], "Text"], Cell[BoxData[{ \(WitnessFunction[wit, S, W]\), "\n", \(\(dd = dcl\[LeftDoubleBracket]1\[RightDoubleBracket];\)\), "\n", \(\(wits\ = \ \(dd\ // \ DClassToBlocks\)\ // \ wit;\)\), "\[IndentingNewLine]", \(wits\ // \ MatrixForm\)}], "Input"], Cell["The witnesses all synchronize the partial minimal automaton.", "Text"], Cell[BoxData[{ \(TransitionFunctionFA[DeleteStateFA[m, sink], \[Delta]]\), "\n", \(\(Q\ = \ Range[n - 1];\)\), "\n", \(\(\[Delta][Q, #] &\)\ /@ \ \ Flatten[wits]\ // \ Union\)}], "Input"], Cell["\<\ The 0-minimal ideal can also be obtained by selecting the elements \ of rank 2 in the semigroup. \ \>", "Text"], Cell[BoxData[{ \(\(R2\ = \ Select[\ ToList[S], \ RankT[#] \[Equal] 2 &\ ];\)\), "\[IndentingNewLine]", \(Sort[\ R2\ ]\ === \ Sort[Flatten[DClassToBlocks[dd]]]\)}], "Input"], Cell[TextData[{ "We want to use this ideal as state set of a finite state machine. More \ precisely, we will use one of the ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-classes, augmented by \[Nu], in witness form. We choose the third ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-class." }], "Text"], Cell[BoxData[{ \(Q\ = \ Append[\ wit[Flatten[\(DClassToBlocks[dd]\)[\([3]\)]]], \ wit[\[Nu]]\ ]\), "\[IndentingNewLine]", \(\(nn\ = \ Length[Q];\)\)}], "Input"], Cell[TextData[{ "The transitions are given by applying the rewrite rules to the words \ obtained by concatenation with symbols ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], ". Thus we are using a transition function ", Cell[BoxData[ FormBox[ RowBox[{\((p, s)\), " ", "\[RightTeeArrow]", " ", RowBox[{"nf", "(", StyleBox["ps", FontSlant->"Italic"], ")"}]}], TraditionalForm]]], " where ", Cell[BoxData[ \(TraditionalForm\`nf(x)\)]], " indicates the normal form obtained by application of the rewrite rules to \ word ", Cell[BoxData[ \(TraditionalForm\`x\)]], ". In conjunction with ", ButtonBox["FunctionToSA", ButtonStyle->"AddOnsLink"], " this whole construction now turns into a one-liner." }], "Text"], Cell[BoxData[ \(sa\ = \ FunctionToSA[Q, 2, Function[{p, s}, WordReduce[\ Concatenate[p, s], eq]]]\)], "Input"], Cell["\<\ To obtain the ideal semiautomaton we still have to remove the sink \ corresponding to \[Nu].\ \>", "Text"], Cell["mid = DeleteStateFA[ sa, nn ]", "Input", AspectRatioFixed->True], Cell[TextData[{ "The new automaton is deterministic and equivalent to the minimal DFA for \ ", Cell[BoxData[ \(TraditionalForm\`L\)]], " from above." }], "Text"], Cell["\<\ DeterministicQFA[mid] EquivalentQFA[m,mid]\ \>", "Input", AspectRatioFixed->True], Cell["\<\ The states of the ideal automaton have distinct behaviors, so the \ ideal automaton is indeed the minimal Fischer automaton.\ \>", "Text"], Cell[BoxData[ \(ToClasses[\ Range[6], MinimizeFA[SetInitialFA[mid, #]] &, \ Type \[Rule] Function\ ]\)], "Input"], Cell["\<\ Of course, it is computationally cheaper to extract the appropriate \ strongly connected component from the minimal automaton to construct the \ minimal Fischer automaton.\ \>", "Text"], Cell[BoxData[ \(mf\ = \ MinimalFischerFA[m]\)], "Input"], Cell["\<\ Here is a brute-force approach towards establishing an isomorphism \ between the two machines: compute the behavior of all states and match them \ up. \ \>", "Text"], Cell[BoxData[ \(t1\ = \ Table[\ \ MinimizeFA[SetInitialFA[mid, i]], \ {i, 6}]\)], "Input"], Cell[BoxData[ \(t2\ = \ Table[\ \ MinimizeFA[SetInitialFA[mf, i]], \ {i, 6}]\)], "Input"], Cell[TextData[{ "Since ", ButtonBox["MinimizeFA", ButtonStyle->"AddOnsLink"], " is idempotent we do not have to check for isomorphic machines here, we \ can use an identity check." }], "Text"], Cell[BoxData[ \(Sort[t1] === Sort[t2]\)], "Input"], Cell["And here is the isomorphism:", "Text"], Cell[BoxData[ \(PositionList[t1, t2]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["L-Classes", "Subsubsection"], Cell[TextData[{ "An analogous construction can be carried out with ", Cell[BoxData[ \(TraditionalForm\`L\)]], "-classes rather than ", Cell[BoxData[ \(TraditionalForm\`R\)]], "-classes. However, since left-translations correspond to left-actions and \ finite state machines require right-actions we obtain a deterministic \ semiautomaton not for ", Cell[BoxData[ \(TraditionalForm\`L\)]], " but for ", Cell[BoxData[ \(TraditionalForm\`L\^\(\(\ \)\(r\)\)\)]], ". " }], "Text"], Cell[BoxData[{ \(Q\ = \ Append[\ \ Flatten[\ \(Thread[wits]\)[\([1]\)]], \ wit[\[Nu]]\ ]\), "\[IndentingNewLine]", \(\(nn\ = \ Length[Q];\)\)}], "Input"], Cell[TextData[{ "We concatenate on the left to obtain a deterministic semiautomaton, \ equivalent to the reversal of ", StyleBox["m", "MR"], " above. " }], "Text"], Cell[BoxData[{ \(\(FunctionToSA[Q, 2, Function[{p, s}, WordReduce[\ Concatenate[s, p], eq]]];\)\), "\n", \(midr\ = \ DeleteStateFA[\ %, \ nn\ ]\)}], "Input"], Cell[TextData[{ "The resulting automaton is indeed reduced and is (isomorphic to) the \ minimal Fischer automaton for ", Cell[BoxData[ \(TraditionalForm\`L\^\(\(\ \)\(r\)\)\)]], ". " }], "Text"], Cell["EquivalentQFA[ReverseFA[m],midr]", "Input", AspectRatioFixed->True], Cell[BoxData[ \(ToClasses[\ Range[5], MinimizeFA[SetInitialFA[midr, #]] &, \ Type \[Rule] Function\ ]\)], "Input"] }, Closed]] }, Closed]] }, Closed]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1280}, {0, 1024}}, AutoGeneratedPackage->None, WindowToolbars->{}, CellGrouping->Automatic, WindowSize->{1016, 998}, WindowMargins->{{0, Automatic}, {Automatic, 0}}, PrintingStartingPageNumber->1, PrivateNotebookOptions->{"ColorPalette"->{RGBColor, 128}}, ShowSelection->True, ShowCellLabel->False, CellLabelAutoDelete->True, ShowCellTags->False, RenderingOptions->{"ObjectDithering"->True, "RasterDithering"->False}, CharacterEncoding->Automatic, Magnification->1.5, StyleDefinitions -> "TextDemoMod.nb" ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{ "c:1"->{ Cell[1806, 53, 154, 4, 107, "Title", Evaluatable->False, CellTags->"c:1"]}, "c:4"->{ Cell[11378, 382, 64, 1, 63, "Subsection", CellTags->"c:4"], Cell[26556, 910, 58, 1, 63, "Subsection", CellTags->"c:4"]}, "Syntactic semigroups"->{ Cell[45332, 1574, 132, 3, 45, "Section", Evaluatable->False, CellTags->{"Syntactic semigroups", "c:5"}], Cell[105218, 3658, 128, 3, 45, "Section", Evaluatable->False, CellTags->{"Syntactic semigroups", "c:5"}]}, "c:5"->{ Cell[45332, 1574, 132, 3, 45, "Section", Evaluatable->False, CellTags->{"Syntactic semigroups", "c:5"}], Cell[105218, 3658, 128, 3, 45, "Section", Evaluatable->False, CellTags->{"Syntactic semigroups", "c:5"}]} } *) (*CellTagsIndex CellTagsIndex->{ {"c:1", 123480, 4294}, {"c:4", 123583, 4298}, {"Syntactic semigroups", 123752, 4303}, {"c:5", 124007, 4310} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 49, 0, 41, "SmallText"], Cell[1806, 53, 154, 4, 107, "Title", Evaluatable->False, CellTags->"c:1"], Cell[CellGroupData[{ Cell[1985, 61, 44, 0, 77, "Section"], Cell[CellGroupData[{ Cell[2054, 65, 37, 0, 63, "Subsection"], Cell[2094, 67, 1707, 51, 282, "Text", Evaluatable->False], Cell[3804, 120, 170, 5, 120, "Input"], Cell[3977, 127, 43, 0, 42, "Text"], Cell[4023, 129, 263, 5, 97, "Input"], Cell[4289, 136, 236, 8, 42, "Text", Evaluatable->False], Cell[4528, 146, 120, 3, 84, "Input"], Cell[4651, 151, 383, 11, 69, "Text", Evaluatable->False], Cell[5037, 164, 201, 5, 120, "Input"], Cell[5241, 171, 242, 7, 42, "Text", Evaluatable->False], Cell[5486, 180, 82, 2, 51, "Input"], Cell[5571, 184, 1098, 34, 123, "Text", Evaluatable->False], Cell[6672, 220, 200, 4, 74, "Input"], Cell[6875, 226, 200, 6, 143, "Input"], Cell[7078, 234, 233, 6, 69, "Text", Evaluatable->False], Cell[7314, 242, 150, 3, 78, "Input"], Cell[7467, 247, 244, 6, 69, "Text", Evaluatable->False], Cell[7714, 255, 226, 5, 97, "Input"], Cell[7943, 262, 147, 3, 74, "Input"], Cell[8093, 267, 700, 17, 123, "Text", Evaluatable->False], Cell[8796, 286, 120, 3, 74, "Input"], Cell[8919, 291, 524, 19, 69, "Text", Evaluatable->False], Cell[9446, 312, 72, 2, 51, "Input"], Cell[9521, 316, 72, 2, 51, "Input"], Cell[9596, 320, 186, 5, 42, "Text", Evaluatable->False], Cell[9785, 327, 251, 6, 120, "Input"], Cell[10039, 335, 411, 11, 69, "Text", Evaluatable->False], Cell[10453, 348, 202, 4, 74, "Input"], Cell[10658, 354, 91, 1, 51, "Input"], Cell[10752, 357, 62, 1, 51, "Input"], Cell[10817, 360, 128, 3, 42, "Text"], Cell[10948, 365, 234, 4, 97, "Input"], Cell[11185, 371, 108, 3, 42, "Text"], Cell[11296, 376, 45, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[11378, 382, 64, 1, 63, "Subsection", CellTags->"c:4"], Cell[CellGroupData[{ Cell[11467, 387, 55, 0, 64, "Subsubsection"], Cell[11525, 389, 742, 23, 96, "Text", Evaluatable->False], Cell[12270, 414, 120, 3, 51, "Input"], Cell[12393, 419, 279, 10, 42, "Text", Evaluatable->False], Cell[12675, 431, 83, 2, 51, "Input"], Cell[12761, 435, 605, 20, 96, "Text", Evaluatable->False], Cell[13369, 457, 112, 3, 74, "Input"], Cell[13484, 462, 107, 3, 74, "Input"], Cell[13594, 467, 81, 2, 51, "Input"], Cell[13678, 471, 80, 2, 51, "Input"], Cell[13761, 475, 151, 5, 42, "Text", Evaluatable->False], Cell[13915, 482, 78, 2, 56, "Input"], Cell[13996, 486, 78, 2, 51, "Input"], Cell[14077, 490, 104, 2, 42, "Text", Evaluatable->False], Cell[14184, 494, 180, 3, 74, "Input"], Cell[14367, 499, 148, 5, 42, "Text", Evaluatable->False], Cell[14518, 506, 91, 2, 51, "Input"], Cell[14612, 510, 181, 3, 74, "Input"], Cell[14796, 515, 691, 21, 96, "Text", Evaluatable->False], Cell[15490, 538, 170, 4, 74, "Input"], Cell[15663, 544, 1655, 44, 225, "Text", Evaluatable->False], Cell[17321, 590, 77, 2, 51, "Input"], Cell[17401, 594, 332, 7, 96, "Text", Evaluatable->False], Cell[17736, 603, 114, 2, 74, "Input"], Cell[17853, 607, 484, 14, 96, "Text", Evaluatable->False], Cell[18340, 623, 107, 2, 51, "Input"], Cell[18450, 627, 843, 26, 96, "Text", Evaluatable->False], Cell[19296, 655, 97, 2, 51, "Input"], Cell[19396, 659, 385, 10, 96, "Text", Evaluatable->False], Cell[19784, 671, 133, 2, 74, "Input"], Cell[19920, 675, 88, 2, 51, "Input"], Cell[20011, 679, 464, 14, 69, "Text", Evaluatable->False], Cell[20478, 695, 238, 6, 74, "Input"], Cell[20719, 703, 208, 5, 120, "Input"], Cell[20930, 710, 174, 6, 42, "Text", Evaluatable->False], Cell[21107, 718, 77, 2, 51, "Input"], Cell[21187, 722, 115, 3, 42, "Text"], Cell[21305, 727, 85, 1, 51, "Input"], Cell[21393, 730, 60, 1, 51, "Input"], Cell[21456, 733, 155, 5, 42, "Text", Evaluatable->False], Cell[21614, 740, 98, 2, 51, "Input"], Cell[21715, 744, 114, 2, 51, "Input"], Cell[21832, 748, 88, 2, 42, "Text", Evaluatable->False], Cell[21923, 752, 154, 2, 74, "Input"], Cell[22080, 756, 316, 11, 42, "Text", Evaluatable->False], Cell[22399, 769, 127, 2, 74, "Input"], Cell[22529, 773, 117, 2, 42, "Text", Evaluatable->False], Cell[22649, 777, 88, 1, 51, "Input"], Cell[22740, 780, 157, 5, 42, "Text", Evaluatable->False], Cell[22900, 787, 78, 1, 51, "Input"], Cell[22981, 790, 114, 2, 42, "Text", Evaluatable->False], Cell[23098, 794, 311, 6, 97, "Input"], Cell[23412, 802, 167, 5, 42, "Text", Evaluatable->False], Cell[23582, 809, 126, 2, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[23745, 816, 56, 0, 64, "Subsubsection"], Cell[23804, 818, 151, 5, 42, "Text", Evaluatable->False], Cell[23958, 825, 153, 3, 74, "Input"], Cell[24114, 830, 103, 2, 51, "Input"], Cell[24220, 834, 341, 7, 96, "Text", Evaluatable->False], Cell[24564, 843, 126, 2, 74, "Input"], Cell[24693, 847, 56, 1, 51, "Input"], Cell[24752, 850, 61, 1, 51, "Input"], Cell[24816, 853, 175, 5, 42, "Text", Evaluatable->False], Cell[24994, 860, 115, 2, 51, "Input"], Cell[25112, 864, 119, 2, 42, "Text", Evaluatable->False], Cell[25234, 868, 130, 2, 74, "Input"], Cell[25367, 872, 113, 3, 42, "Text"], Cell[25483, 877, 219, 3, 74, "Input"], Cell[25705, 882, 202, 4, 74, "Input"], Cell[25910, 888, 270, 5, 120, "Input"], Cell[26183, 895, 114, 3, 42, "Text"], Cell[26300, 900, 207, 4, 74, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[26556, 910, 58, 1, 63, "Subsection", CellTags->"c:4"], Cell[CellGroupData[{ Cell[26639, 915, 36, 0, 64, "Subsubsection"], Cell[26678, 917, 1205, 35, 291, "Text"], Cell[27886, 954, 158, 2, 74, "Input"], Cell[28047, 958, 111, 2, 51, "Input"], Cell[28161, 962, 111, 2, 51, "Input"], Cell[28275, 966, 111, 2, 51, "Input"], Cell[28389, 970, 145, 3, 69, "Text"], Cell[28537, 975, 111, 2, 51, "Input"], Cell[28651, 979, 1691, 55, 243, "Text"], Cell[30345, 1036, 416, 7, 166, "Input"], Cell[30764, 1045, 258, 8, 69, "Text"], Cell[31025, 1055, 119, 2, 74, "Input"], Cell[31147, 1059, 229, 4, 120, "Input"], Cell[31379, 1065, 29, 0, 42, "Text"], Cell[31411, 1067, 119, 2, 74, "Input"], Cell[31533, 1071, 117, 5, 42, "Text"], Cell[31653, 1078, 133, 2, 74, "Input"], Cell[31789, 1082, 346, 13, 69, "Text"], Cell[32138, 1097, 82, 2, 74, "Input"], Cell[32223, 1101, 82, 2, 74, "Input"], Cell[32308, 1105, 561, 14, 96, "Text"], Cell[32872, 1121, 74, 1, 51, "Input"], Cell[32949, 1124, 91, 1, 51, "Input"], Cell[33043, 1127, 180, 3, 74, "Input"], Cell[33226, 1132, 384, 14, 69, "Text"], Cell[33613, 1148, 149, 3, 74, "Input"], Cell[33765, 1153, 246, 11, 42, "Text"], Cell[34014, 1166, 163, 3, 74, "Input"], Cell[34180, 1171, 781, 24, 225, "Text"], Cell[34964, 1197, 111, 2, 51, "Input"], Cell[35078, 1201, 119, 5, 42, "Text"], Cell[35200, 1208, 73, 1, 51, "Input"], Cell[35276, 1211, 209, 8, 42, "Text"], Cell[35488, 1221, 45, 1, 51, "Input"], Cell[35536, 1224, 76, 0, 42, "Text"], Cell[35615, 1226, 89, 1, 51, "Input"], Cell[35707, 1229, 392, 12, 69, "Text"], Cell[36102, 1243, 89, 1, 51, "Input"], Cell[36194, 1246, 102, 3, 42, "Text"], Cell[36299, 1251, 169, 3, 74, "Input"], Cell[36471, 1256, 40, 0, 42, "Text"], Cell[36514, 1258, 76, 1, 51, "Input"], Cell[36593, 1261, 161, 5, 42, "Text"], Cell[36757, 1268, 78, 1, 51, "Input"], Cell[36838, 1271, 116, 5, 42, "Text"], Cell[36957, 1278, 78, 1, 51, "Input"], Cell[37038, 1281, 127, 5, 42, "Text"], Cell[37168, 1288, 81, 1, 51, "Input"], Cell[37252, 1291, 112, 3, 42, "Text"], Cell[37367, 1296, 109, 2, 51, "Input"], Cell[37479, 1300, 113, 2, 74, "Input"], Cell[37595, 1304, 638, 16, 96, "Text"], Cell[38236, 1322, 149, 2, 74, "Input"], Cell[38388, 1326, 61, 1, 51, "Input"], Cell[38452, 1329, 60, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[38549, 1335, 40, 0, 64, "Subsubsection"], Cell[38592, 1337, 46, 0, 42, "Text"], Cell[38641, 1339, 193, 3, 97, "Input"], Cell[38837, 1344, 189, 4, 74, "Input"], Cell[39029, 1350, 203, 8, 42, "Text"], Cell[39235, 1360, 67, 1, 51, "Input"], Cell[39305, 1363, 132, 6, 42, "Text"], Cell[39440, 1371, 193, 4, 74, "Input"], Cell[39636, 1377, 57, 0, 42, "Text"], Cell[39696, 1379, 115, 2, 74, "Input"], Cell[39814, 1383, 67, 0, 42, "Text"], Cell[39884, 1385, 92, 1, 51, "Input"], Cell[39979, 1388, 152, 5, 42, "Text"], Cell[40134, 1395, 135, 3, 51, "Input"], Cell[40272, 1400, 90, 1, 51, "Input"], Cell[40365, 1403, 53, 0, 42, "Text"], Cell[40421, 1405, 86, 1, 51, "Input"], Cell[40510, 1408, 211, 5, 69, "Text"], Cell[40724, 1415, 158, 3, 74, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[40919, 1423, 46, 0, 64, "Subsubsection"], Cell[40968, 1425, 474, 15, 69, "Text"], Cell[41445, 1442, 54, 1, 51, "Input"], Cell[41502, 1445, 213, 4, 97, "Input"], Cell[41718, 1451, 276, 8, 69, "Text"], Cell[41997, 1461, 63, 1, 51, "Input"], Cell[42063, 1464, 87, 1, 51, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[42199, 1471, 35, 0, 63, "Subsection"], Cell[42237, 1473, 497, 13, 96, "Text"], Cell[42737, 1488, 344, 5, 143, "Input"], Cell[43084, 1495, 163, 6, 42, "Text"], Cell[43250, 1503, 143, 3, 74, "Input"], Cell[43396, 1508, 275, 5, 120, "Input"], Cell[43674, 1515, 73, 0, 42, "Text"], Cell[43750, 1517, 55, 1, 51, "Input"], Cell[43808, 1520, 106, 2, 51, "Input"], Cell[43917, 1524, 46, 0, 42, "Text"], Cell[43966, 1526, 330, 6, 143, "Input"], Cell[44299, 1534, 73, 1, 51, "Input"], Cell[44375, 1537, 151, 5, 42, "Text"], Cell[44529, 1544, 68, 1, 51, "Input"], Cell[44600, 1547, 198, 6, 69, "Text"], Cell[44801, 1555, 229, 4, 74, "Input"], Cell[45033, 1561, 135, 3, 74, "Input"], Cell[45171, 1566, 112, 2, 51, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[45332, 1574, 132, 3, 45, "Section", Evaluatable->False, CellTags->{"Syntactic semigroups", "c:5"}], Cell[CellGroupData[{ Cell[45489, 1581, 42, 0, 63, "Subsection"], Cell[45534, 1583, 2459, 71, 333, "Text", Evaluatable->False], Cell[47996, 1656, 107, 2, 51, "Input"], Cell[48106, 1660, 81, 1, 51, "Input"], Cell[48190, 1663, 3041, 85, 582, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[51268, 1753, 42, 0, 63, "Subsection"], Cell[CellGroupData[{ Cell[51335, 1757, 98, 4, 64, "Subsubsection"], Cell[51436, 1763, 364, 11, 81, "Text", Evaluatable->False], Cell[51803, 1776, 65, 1, 51, "Input"], Cell[51871, 1779, 94, 2, 42, "Text", Evaluatable->False], Cell[51968, 1783, 135, 5, 42, "Text", Evaluatable->False], Cell[52106, 1790, 120, 3, 74, "Input"], Cell[52229, 1795, 359, 11, 69, "Text", Evaluatable->False], Cell[52591, 1808, 162, 4, 97, "Input"], Cell[52756, 1814, 389, 14, 69, "Text", Evaluatable->False], Cell[53148, 1830, 129, 2, 74, "Input"], Cell[53280, 1834, 136, 5, 42, "Text"], Cell[53419, 1841, 77, 2, 51, "Input"], Cell[53499, 1845, 71, 0, 42, "Text"], Cell[53573, 1847, 130, 2, 74, "Input"], Cell[53706, 1851, 183, 6, 42, "Text"], Cell[53892, 1859, 73, 1, 51, "Input"], Cell[53968, 1862, 68, 0, 42, "Text"], Cell[54039, 1864, 75, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[54151, 1870, 105, 4, 64, "Subsubsection"], Cell[54259, 1876, 150, 5, 42, "Text"], Cell[54412, 1883, 136, 4, 51, "Input"], Cell[54551, 1889, 78, 2, 51, "Input"], Cell[54632, 1893, 210, 6, 69, "Text", Evaluatable->False], Cell[54845, 1901, 146, 3, 74, "Input"], Cell[54994, 1906, 389, 14, 69, "Text", Evaluatable->False], Cell[55386, 1922, 154, 3, 74, "Input"], Cell[55543, 1927, 237, 8, 42, "Text"], Cell[55783, 1937, 67, 1, 51, "Input"], Cell[55853, 1940, 217, 4, 97, "Input"], Cell[56073, 1946, 213, 6, 69, "Text"], Cell[56289, 1954, 161, 3, 74, "Input"], Cell[56453, 1959, 51, 1, 51, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[56553, 1966, 51, 0, 63, "Subsection"], Cell[56607, 1968, 523, 15, 147, "Text", Evaluatable->False], Cell[57133, 1985, 66, 1, 51, "Input"], Cell[57202, 1988, 100, 2, 74, "Input"], Cell[57305, 1992, 94, 2, 42, "Text", Evaluatable->False], Cell[57402, 1996, 84, 2, 51, "Input"], Cell[57489, 2000, 194, 7, 42, "Text", Evaluatable->False], Cell[57686, 2009, 120, 3, 74, "Input"], Cell[57809, 2014, 196, 7, 42, "Text", Evaluatable->False], Cell[58008, 2023, 68, 2, 51, "Input"], Cell[58079, 2027, 359, 11, 69, "Text", Evaluatable->False], Cell[58441, 2040, 74, 2, 51, "Input"], Cell[58518, 2044, 659, 18, 96, "Text", Evaluatable->False], Cell[59180, 2064, 129, 2, 74, "Input"], Cell[59312, 2068, 77, 2, 51, "Input"], Cell[59392, 2072, 71, 0, 42, "Text"], Cell[59466, 2074, 130, 2, 74, "Input"], Cell[59599, 2078, 97, 2, 51, "Input"], Cell[59699, 2082, 198, 8, 42, "Text"], Cell[59900, 2092, 204, 4, 97, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[60141, 2101, 34, 0, 63, "Subsection"], Cell[60178, 2103, 437, 11, 96, "Text", Evaluatable->False], Cell[60618, 2116, 206, 3, 97, "Input"], Cell[60827, 2121, 72, 2, 51, "Input"], Cell[60902, 2125, 307, 10, 42, "Text", Evaluatable->False], Cell[61212, 2137, 69, 2, 51, "Input"], Cell[61284, 2141, 79, 2, 51, "Input"], Cell[61366, 2145, 82, 2, 51, "Input"], Cell[61451, 2149, 340, 13, 42, "Text", Evaluatable->False], Cell[61794, 2164, 78, 2, 51, "Input"], Cell[61875, 2168, 69, 0, 42, "Text"], Cell[61947, 2170, 80, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[62064, 2176, 83, 1, 57, "Subsection"], Cell[62150, 2179, 232, 8, 42, "Text"], Cell[62385, 2189, 225, 4, 120, "Input"], Cell[62613, 2195, 426, 14, 69, "Text", Evaluatable->False], Cell[63042, 2211, 75, 2, 51, "Input"], Cell[63120, 2215, 55, 1, 51, "Input"], Cell[63178, 2218, 166, 5, 42, "Text", Evaluatable->False], Cell[63347, 2225, 81, 2, 51, "Input"], Cell[63431, 2229, 559, 19, 69, "Text", Evaluatable->False], Cell[63993, 2250, 120, 2, 74, "Input"], Cell[64116, 2254, 315, 10, 69, "Text", Evaluatable->False], Cell[64434, 2266, 159, 3, 74, "Input"], Cell[64596, 2271, 154, 5, 42, "Text", Evaluatable->False], Cell[64753, 2278, 78, 2, 51, "Input"], Cell[64834, 2282, 162, 7, 42, "Text", Evaluatable->False], Cell[64999, 2291, 74, 2, 51, "Input"], Cell[65076, 2295, 383, 13, 69, "Text", Evaluatable->False], Cell[65462, 2310, 248, 5, 97, "Input"], Cell[65713, 2317, 249, 10, 42, "Text", Evaluatable->False], Cell[65965, 2329, 161, 3, 74, "Input"], Cell[66129, 2334, 121, 3, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[66287, 2342, 41, 0, 63, "Subsection"], Cell[66331, 2344, 2192, 55, 594, "Text", Evaluatable->False], Cell[68526, 2401, 255, 5, 120, "Input"], Cell[68784, 2408, 298, 12, 42, "Text", Evaluatable->False], Cell[69085, 2422, 68, 2, 51, "Input"], Cell[69156, 2426, 161, 3, 74, "Input"], Cell[69320, 2431, 835, 23, 123, "Text", Evaluatable->False], Cell[70158, 2456, 226, 4, 74, "Input"], Cell[70387, 2462, 158, 5, 42, "Text", Evaluatable->False], Cell[70548, 2469, 311, 7, 97, "Input"], Cell[70862, 2478, 386, 15, 42, "Text", Evaluatable->False], Cell[71251, 2495, 78, 2, 51, "Input"], Cell[71332, 2499, 84, 2, 42, "Text", Evaluatable->False], Cell[71419, 2503, 81, 2, 51, "Input"], Cell[71503, 2507, 304, 12, 42, "Text", Evaluatable->False], Cell[71810, 2521, 131, 3, 51, "Input"], Cell[71944, 2526, 82, 2, 51, "Input"], Cell[72029, 2530, 329, 10, 69, "Text", Evaluatable->False], Cell[72361, 2542, 135, 3, 51, "Input"], Cell[72499, 2547, 425, 10, 96, "Text", Evaluatable->False], Cell[72927, 2559, 303, 7, 120, "Input"], Cell[73233, 2568, 139, 5, 42, "Text", Evaluatable->False], Cell[73375, 2575, 202, 4, 74, "Input"], Cell[73580, 2581, 138, 5, 42, "Text", Evaluatable->False], Cell[73721, 2588, 130, 2, 74, "Input"], Cell[73854, 2592, 182, 7, 42, "Text", Evaluatable->False], Cell[74039, 2601, 209, 4, 74, "Input"], Cell[74251, 2607, 239, 10, 42, "Text", Evaluatable->False], Cell[74493, 2619, 114, 2, 51, "Input"], Cell[74610, 2623, 87, 2, 42, "Text", Evaluatable->False], Cell[74700, 2627, 81, 2, 51, "Input"], Cell[74784, 2631, 91, 2, 42, "Text", Evaluatable->False], Cell[74878, 2635, 78, 2, 51, "Input"], Cell[74959, 2639, 173, 5, 42, "Text", Evaluatable->False], Cell[75135, 2646, 74, 2, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[75246, 2653, 48, 0, 63, "Subsection"], Cell[75297, 2655, 4361, 124, 582, "Text", Evaluatable->False], Cell[79661, 2781, 445, 11, 120, "Input"], Cell[80109, 2794, 103, 3, 42, "Text"], Cell[80215, 2799, 76, 1, 51, "Input"], Cell[80294, 2802, 290, 6, 97, "Input"], Cell[80587, 2810, 96, 3, 42, "Text"], Cell[80686, 2815, 142, 3, 74, "Input"], Cell[80831, 2820, 195, 7, 42, "Text", Evaluatable->False], Cell[81029, 2829, 111, 2, 51, "Input"], Cell[81143, 2833, 89, 2, 42, "Text", Evaluatable->False], Cell[81235, 2837, 56, 1, 51, "Input"], Cell[81294, 2840, 116, 2, 74, "Input"], Cell[81413, 2844, 284, 10, 42, "Text"], Cell[81700, 2856, 460, 12, 120, "Input"], Cell[82163, 2870, 98, 3, 42, "Text"], Cell[82264, 2875, 90, 2, 74, "Input"], Cell[82357, 2879, 116, 2, 74, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[82510, 2886, 50, 0, 63, "Subsection"], Cell[82563, 2888, 1744, 56, 189, "Text", Evaluatable->False], Cell[84310, 2946, 252, 5, 97, "Input"], Cell[84565, 2953, 37, 0, 42, "Text"], Cell[84605, 2955, 76, 1, 51, "Input"], Cell[84684, 2958, 170, 3, 97, "Input"], Cell[84857, 2963, 96, 3, 42, "Text"], Cell[84956, 2968, 142, 3, 74, "Input"], Cell[85101, 2973, 178, 7, 42, "Text", Evaluatable->False], Cell[85282, 2982, 111, 2, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[85430, 2989, 39, 0, 63, "Subsection"], Cell[85472, 2991, 1565, 45, 285, "Text", Evaluatable->False], Cell[87040, 3038, 184, 5, 97, "Input"], Cell[87227, 3045, 145, 3, 74, "Input"], Cell[87375, 3050, 201, 7, 42, "Text", Evaluatable->False], Cell[87579, 3059, 117, 2, 51, "Input"], Cell[87699, 3063, 118, 2, 42, "Text", Evaluatable->False], Cell[87820, 3067, 190, 4, 97, "Input"], Cell[88013, 3073, 346, 9, 42, "Text", Evaluatable->False], Cell[88362, 3084, 351, 8, 143, "Input"], Cell[88716, 3094, 137, 5, 42, "Text", Evaluatable->False], Cell[88856, 3101, 87, 2, 51, "Input"], Cell[88946, 3105, 650, 26, 69, "Text", Evaluatable->False], Cell[89599, 3133, 143, 3, 51, "Input"], Cell[89745, 3138, 140, 3, 51, "Input"], Cell[89888, 3143, 405, 15, 42, "Text", Evaluatable->False], Cell[90296, 3160, 183, 4, 74, "Input"], Cell[90482, 3166, 163, 5, 42, "Text", Evaluatable->False], Cell[90648, 3173, 189, 4, 74, "Input"], Cell[90840, 3179, 1229, 38, 150, "Text", Evaluatable->False], Cell[92072, 3219, 211, 4, 97, "Input"], Cell[92286, 3225, 108, 2, 51, "Input"], Cell[92397, 3229, 192, 7, 42, "Text", Evaluatable->False], Cell[92592, 3238, 155, 3, 74, "Input"], Cell[92750, 3243, 77, 2, 51, "Input"], Cell[92830, 3247, 399, 13, 69, "Text", Evaluatable->False], Cell[93232, 3262, 185, 5, 74, "Input"], Cell[93420, 3269, 81, 2, 51, "Input"], Cell[93504, 3273, 79, 2, 51, "Input"], Cell[93586, 3277, 155, 3, 74, "Input"], Cell[93744, 3282, 756, 24, 123, "Text", Evaluatable->False], Cell[94503, 3308, 239, 7, 42, "Text", Evaluatable->False], Cell[94745, 3317, 182, 5, 74, "Input"], Cell[94930, 3324, 770, 23, 147, "Text", Evaluatable->False], Cell[95703, 3349, 193, 4, 74, "Input"], Cell[95899, 3355, 278, 10, 42, "Text", Evaluatable->False], Cell[96180, 3367, 182, 4, 97, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[96399, 3376, 30, 0, 63, "Subsection"], Cell[96432, 3378, 762, 22, 123, "Text"], Cell[97197, 3402, 180, 3, 97, "Input"], Cell[97380, 3407, 52, 0, 42, "Text"], Cell[97435, 3409, 254, 6, 120, "Input"], Cell[97692, 3417, 167, 5, 42, "Text"], Cell[97862, 3424, 138, 2, 74, "Input"], Cell[98003, 3428, 247, 8, 42, "Text", Evaluatable->False], Cell[98253, 3438, 125, 2, 51, "Input"], Cell[98381, 3442, 123, 2, 74, "Input"], Cell[98507, 3446, 819, 20, 123, "Text", Evaluatable->False], Cell[99329, 3468, 409, 9, 97, "Input"], Cell[99741, 3479, 115, 3, 74, "Input"], Cell[99859, 3484, 117, 3, 42, "Text"], Cell[99979, 3489, 116, 2, 74, "Input"], Cell[100098, 3493, 156, 2, 74, "Input"], Cell[100257, 3497, 67, 0, 42, "Text"], Cell[100327, 3499, 301, 6, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[100665, 3510, 37, 0, 63, "Subsection"], Cell[100705, 3512, 481, 17, 69, "Text"], Cell[101189, 3531, 111, 2, 51, "Input"], Cell[101303, 3535, 67, 1, 51, "Input"], Cell[101373, 3538, 154, 5, 42, "Text"], Cell[101530, 3545, 132, 2, 74, "Input"], Cell[101665, 3549, 257, 4, 97, "Input"], Cell[101925, 3555, 179, 6, 42, "Text"], Cell[102107, 3563, 391, 8, 166, "Input"], Cell[102501, 3573, 279, 9, 69, "Text"], Cell[102783, 3584, 669, 14, 281, "Input"], Cell[103455, 3600, 92, 3, 42, "Text"], Cell[103550, 3605, 236, 4, 97, "Input"], Cell[103789, 3611, 296, 8, 69, "Text"], Cell[104088, 3621, 387, 7, 143, "Input"], Cell[104478, 3630, 149, 5, 42, "Text"], Cell[104630, 3637, 81, 1, 51, "Input"], Cell[104714, 3640, 105, 3, 42, "Text"], Cell[104822, 3645, 212, 3, 74, "Input"], Cell[105037, 3650, 132, 2, 51, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[105218, 3658, 128, 3, 45, "Section", Evaluatable->False, CellTags->{"Syntactic semigroups", "c:5"}], Cell[CellGroupData[{ Cell[105371, 3665, 55, 0, 63, "Subsection"], Cell[105429, 3667, 2307, 62, 492, "Text"], Cell[107739, 3731, 106, 3, 74, "Input"], Cell[107848, 3736, 87, 3, 42, "Text"], Cell[107938, 3741, 139, 3, 74, "Input"], Cell[108080, 3746, 169, 4, 69, "Text"], Cell[108252, 3752, 167, 4, 74, "Input"], Cell[108422, 3758, 169, 5, 42, "Text", Evaluatable->False], Cell[108594, 3765, 146, 4, 51, "Input"], Cell[108743, 3771, 100, 2, 42, "Text", Evaluatable->False], Cell[108846, 3775, 79, 2, 51, "Input"], Cell[108928, 3779, 110, 2, 42, "Text", Evaluatable->False], Cell[109041, 3783, 79, 2, 51, "Input"], Cell[109123, 3787, 229, 6, 69, "Text", Evaluatable->False], Cell[109355, 3795, 132, 2, 74, "Input"], Cell[109490, 3799, 164, 5, 42, "Text", Evaluatable->False], Cell[109657, 3806, 85, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[109779, 3812, 94, 2, 63, "Subsection", Evaluatable->False], Cell[109876, 3816, 367, 6, 96, "Text"], Cell[110246, 3824, 133, 4, 51, "Input"], Cell[110382, 3830, 61, 1, 50, "Input"], Cell[110446, 3833, 76, 1, 50, "Input"], Cell[110525, 3836, 130, 3, 51, "Input"], Cell[110658, 3841, 121, 3, 74, "Input"], Cell[110782, 3846, 52, 1, 50, "Input"], Cell[110837, 3849, 62, 1, 50, "Input"], Cell[110902, 3852, 135, 5, 42, "Text"], Cell[111040, 3859, 164, 5, 70, "Input"], Cell[111207, 3866, 65, 0, 42, "Text"], Cell[111275, 3868, 208, 6, 70, "Input"], Cell[111486, 3876, 116, 3, 42, "Text"], Cell[111605, 3881, 197, 5, 70, "Input"], Cell[111805, 3888, 70, 0, 42, "Text"], Cell[111878, 3890, 84, 1, 50, "Input"], Cell[111965, 3893, 133, 5, 42, "Text"], Cell[112101, 3900, 71, 1, 51, "Input"], Cell[112175, 3903, 73, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[112285, 3909, 67, 0, 63, "Subsection"], Cell[CellGroupData[{ Cell[112377, 3913, 44, 0, 64, "Subsubsection"], Cell[112424, 3915, 1753, 48, 270, "Text"], Cell[114180, 3965, 191, 4, 97, "Input"], Cell[114374, 3971, 147, 5, 42, "Text"], Cell[114524, 3978, 147, 3, 74, "Input"], Cell[114674, 3983, 184, 8, 42, "Text"], Cell[114861, 3993, 113, 2, 74, "Input"], Cell[114977, 3997, 262, 6, 69, "Text"], Cell[115242, 4005, 204, 4, 97, "Input"], Cell[115449, 4011, 175, 5, 42, "Text"], Cell[115627, 4018, 99, 2, 51, "Input"], Cell[115729, 4022, 145, 3, 69, "Text"], Cell[115877, 4027, 143, 4, 70, "Input"], Cell[116023, 4033, 242, 8, 42, "Text"], Cell[116268, 4043, 260, 5, 97, "Input"], Cell[116531, 4050, 104, 2, 51, "Input"], Cell[116638, 4054, 115, 5, 42, "Text"], Cell[116756, 4061, 272, 5, 120, "Input"], Cell[117031, 4068, 76, 0, 42, "Text"], Cell[117110, 4070, 204, 3, 97, "Input"], Cell[117317, 4075, 121, 3, 42, "Text"], Cell[117441, 4080, 203, 4, 74, "Input"], Cell[117647, 4086, 321, 9, 69, "Text"], Cell[117971, 4097, 187, 4, 74, "Input"], Cell[118161, 4103, 859, 26, 123, "Text"], Cell[119023, 4131, 131, 3, 51, "Input"], Cell[119157, 4136, 116, 3, 42, "Text"], Cell[119276, 4141, 72, 1, 50, "Input"], Cell[119351, 4144, 174, 6, 42, "Text"], Cell[119528, 4152, 93, 4, 70, "Input"], Cell[119624, 4158, 148, 3, 69, "Text"], Cell[119775, 4163, 124, 2, 51, "Input"], Cell[119902, 4167, 195, 4, 69, "Text"], Cell[120100, 4173, 61, 1, 51, "Input"], Cell[120164, 4176, 175, 4, 69, "Text"], Cell[120342, 4182, 102, 2, 51, "Input"], Cell[120447, 4186, 101, 2, 51, "Input"], Cell[120551, 4190, 202, 6, 69, "Text"], Cell[120756, 4198, 54, 1, 51, "Input"], Cell[120813, 4201, 44, 0, 42, "Text"], Cell[120860, 4203, 53, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[120950, 4209, 34, 0, 64, "Subsubsection"], Cell[120987, 4211, 518, 16, 96, "Text"], Cell[121508, 4229, 180, 4, 74, "Input"], Cell[121691, 4235, 169, 5, 42, "Text"], Cell[121863, 4242, 176, 3, 74, "Input"], Cell[122042, 4247, 206, 6, 42, "Text"], Cell[122251, 4255, 75, 1, 50, "Input"], Cell[122329, 4258, 125, 2, 51, "Input"] }, Closed]] }, Closed]] }, Closed]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)