AutMan.toc

\contentsline {chapter}{\numberline {1}\leavevmode {\color {Chapter } Introduction }}{5}{chapter.1}
\contentsline {chapter}{\numberline {2}\leavevmode {\color {Chapter }Finite Automata}}{7}{chapter.2}
\contentsline {section}{\numberline {2.1}\leavevmode {\color {Chapter }Automata generation}}{7}{section.2.1}
\contentsline {subsection}{\numberline {2.1.1}\leavevmode {\color {Chapter }Automaton}}{7}{subsection.2.1.1}
\contentsline {subsection}{\numberline {2.1.2}\leavevmode {\color {Chapter }IsAutomaton}}{9}{subsection.2.1.2}
\contentsline {subsection}{\numberline {2.1.3}\leavevmode {\color {Chapter }IsDeterministicAutomaton}}{9}{subsection.2.1.3}
\contentsline {subsection}{\numberline {2.1.4}\leavevmode {\color {Chapter }IsNonDeterministicAutomaton}}{9}{subsection.2.1.4}
\contentsline {subsection}{\numberline {2.1.5}\leavevmode {\color {Chapter }IsEpsilonAutomaton}}{9}{subsection.2.1.5}
\contentsline {subsection}{\numberline {2.1.6}\leavevmode {\color {Chapter }String}}{10}{subsection.2.1.6}
\contentsline {subsection}{\numberline {2.1.7}\leavevmode {\color {Chapter }RandomAutomaton}}{10}{subsection.2.1.7}
\contentsline {section}{\numberline {2.2}\leavevmode {\color {Chapter }Automata internals}}{11}{section.2.2}
\contentsline {subsection}{\numberline {2.2.1}\leavevmode {\color {Chapter }AlphabetOfAutomaton}}{11}{subsection.2.2.1}
\contentsline {subsection}{\numberline {2.2.2}\leavevmode {\color {Chapter }AlphabetOfAutomatonAsList}}{11}{subsection.2.2.2}
\contentsline {subsection}{\numberline {2.2.3}\leavevmode {\color {Chapter }TransitionMatrixOfAutomaton}}{12}{subsection.2.2.3}
\contentsline {subsection}{\numberline {2.2.4}\leavevmode {\color {Chapter }InitialStatesOfAutomaton}}{12}{subsection.2.2.4}
\contentsline {subsection}{\numberline {2.2.5}\leavevmode {\color {Chapter }SetInitialStatesOfAutomaton}}{12}{subsection.2.2.5}
\contentsline {subsection}{\numberline {2.2.6}\leavevmode {\color {Chapter }FinalStatesOfAutomaton}}{12}{subsection.2.2.6}
\contentsline {subsection}{\numberline {2.2.7}\leavevmode {\color {Chapter }SetFinalStatesOfAutomaton}}{13}{subsection.2.2.7}
\contentsline {subsection}{\numberline {2.2.8}\leavevmode {\color {Chapter }NumberStatesOfAutomaton}}{13}{subsection.2.2.8}
\contentsline {section}{\numberline {2.3}\leavevmode {\color {Chapter }Comparison of automata}}{13}{section.2.3}
\contentsline {section}{\numberline {2.4}\leavevmode {\color {Chapter }Tests involving automata}}{13}{section.2.4}
\contentsline {subsection}{\numberline {2.4.1}\leavevmode {\color {Chapter }IsDenseAutomaton}}{13}{subsection.2.4.1}
\contentsline {subsection}{\numberline {2.4.2}\leavevmode {\color {Chapter }IsRecognizedByAutomaton}}{14}{subsection.2.4.2}
\contentsline {subsection}{\numberline {2.4.3}\leavevmode {\color {Chapter }IsPermutationAutomaton}}{14}{subsection.2.4.3}
\contentsline {subsection}{\numberline {2.4.4}\leavevmode {\color {Chapter }IsInverseAutomaton}}{14}{subsection.2.4.4}
\contentsline {subsection}{\numberline {2.4.5}\leavevmode {\color {Chapter }AddInverseEdgesToInverseAutomaton}}{14}{subsection.2.4.5}
\contentsline {subsection}{\numberline {2.4.6}\leavevmode {\color {Chapter }IsReversibleAutomaton}}{15}{subsection.2.4.6}
\contentsline {section}{\numberline {2.5}\leavevmode {\color {Chapter }Basic operations}}{15}{section.2.5}
\contentsline {subsection}{\numberline {2.5.1}\leavevmode {\color {Chapter }CopyAutomaton}}{15}{subsection.2.5.1}
\contentsline {subsection}{\numberline {2.5.2}\leavevmode {\color {Chapter }NullCompletionAutomaton}}{15}{subsection.2.5.2}
\contentsline {subsection}{\numberline {2.5.3}\leavevmode {\color {Chapter }ListSinkStatesAut}}{16}{subsection.2.5.3}
\contentsline {subsection}{\numberline {2.5.4}\leavevmode {\color {Chapter }RemovedSinkStates}}{16}{subsection.2.5.4}
\contentsline {subsection}{\numberline {2.5.5}\leavevmode {\color {Chapter }ReversedAutomaton}}{16}{subsection.2.5.5}
\contentsline {subsection}{\numberline {2.5.6}\leavevmode {\color {Chapter }PermutedAutomaton}}{17}{subsection.2.5.6}
\contentsline {subsection}{\numberline {2.5.7}\leavevmode {\color {Chapter }ListPermutedAutomata}}{17}{subsection.2.5.7}
\contentsline {subsection}{\numberline {2.5.8}\leavevmode {\color {Chapter }NormalizedAutomaton}}{17}{subsection.2.5.8}
\contentsline {subsection}{\numberline {2.5.9}\leavevmode {\color {Chapter }UnionAutomata}}{18}{subsection.2.5.9}
\contentsline {subsection}{\numberline {2.5.10}\leavevmode {\color {Chapter }ProductAutomaton}}{18}{subsection.2.5.10}
\contentsline {subsection}{\numberline {2.5.11}\leavevmode {\color {Chapter }ProductOfLanguages}}{19}{subsection.2.5.11}
\contentsline {section}{\numberline {2.6}\leavevmode {\color {Chapter }Links with Semigroups}}{19}{section.2.6}
\contentsline {subsection}{\numberline {2.6.1}\leavevmode {\color {Chapter }TransitionSemigroup}}{19}{subsection.2.6.1}
\contentsline {subsection}{\numberline {2.6.2}\leavevmode {\color {Chapter }SyntacticSemigroupAut}}{20}{subsection.2.6.2}
\contentsline {subsection}{\numberline {2.6.3}\leavevmode {\color {Chapter }SyntacticSemigroupLang}}{20}{subsection.2.6.3}
\contentsline {chapter}{\numberline {3}\leavevmode {\color {Chapter }Rational languages}}{21}{chapter.3}
\contentsline {section}{\numberline {3.1}\leavevmode {\color {Chapter }Rational Expressions}}{21}{section.3.1}
\contentsline {subsection}{\numberline {3.1.1}\leavevmode {\color {Chapter }RationalExpression}}{21}{subsection.3.1.1}
\contentsline {subsection}{\numberline {3.1.2}\leavevmode {\color {Chapter }RatExpOnnLetters}}{21}{subsection.3.1.2}
\contentsline {subsection}{\numberline {3.1.3}\leavevmode {\color {Chapter }RandomRatExp}}{22}{subsection.3.1.3}
\contentsline {subsection}{\numberline {3.1.4}\leavevmode {\color {Chapter }SizeRatExp}}{22}{subsection.3.1.4}
\contentsline {subsection}{\numberline {3.1.5}\leavevmode {\color {Chapter }IsRationalExpression}}{22}{subsection.3.1.5}
\contentsline {subsection}{\numberline {3.1.6}\leavevmode {\color {Chapter }AlphabetOfRatExp}}{23}{subsection.3.1.6}
\contentsline {subsection}{\numberline {3.1.7}\leavevmode {\color {Chapter }AlphabetOfRatExpAsList}}{23}{subsection.3.1.7}
\contentsline {subsection}{\numberline {3.1.8}\leavevmode {\color {Chapter }CopyRatExp}}{24}{subsection.3.1.8}
\contentsline {section}{\numberline {3.2}\leavevmode {\color {Chapter }Comparison of rational expressions}}{24}{section.3.2}
\contentsline {section}{\numberline {3.3}\leavevmode {\color {Chapter }Operations with rational languages}}{24}{section.3.3}
\contentsline {subsection}{\numberline {3.3.1}\leavevmode {\color {Chapter }UnionRatExp}}{24}{subsection.3.3.1}
\contentsline {subsection}{\numberline {3.3.2}\leavevmode {\color {Chapter }ProductRatExp}}{24}{subsection.3.3.2}
\contentsline {subsection}{\numberline {3.3.3}\leavevmode {\color {Chapter } StarRatExp}}{24}{subsection.3.3.3}
\contentsline {chapter}{\numberline {4}\leavevmode {\color {Chapter }Automata \emph {versus} rational expressions}}{26}{chapter.4}
\contentsline {section}{\numberline {4.1}\leavevmode {\color {Chapter }From automata to rational expressions}}{26}{section.4.1}
\contentsline {subsection}{\numberline {4.1.1}\leavevmode {\color {Chapter }AutomatonToRatExp }}{26}{subsection.4.1.1}
\contentsline {section}{\numberline {4.2}\leavevmode {\color {Chapter }From rational expression to automata}}{26}{section.4.2}
\contentsline {subsection}{\numberline {4.2.1}\leavevmode {\color {Chapter }RatExpToNDAut}}{26}{subsection.4.2.1}
\contentsline {subsection}{\numberline {4.2.2}\leavevmode {\color {Chapter }RatExpToAutomaton}}{27}{subsection.4.2.2}
\contentsline {section}{\numberline {4.3}\leavevmode {\color {Chapter } Some tests on automata }}{27}{section.4.3}
\contentsline {subsection}{\numberline {4.3.1}\leavevmode {\color {Chapter }IsEmptyLang}}{28}{subsection.4.3.1}
\contentsline {subsection}{\numberline {4.3.2}\leavevmode {\color {Chapter }IsFullLang}}{28}{subsection.4.3.2}
\contentsline {subsection}{\numberline {4.3.3}\leavevmode {\color {Chapter }AreEqualLang}}{28}{subsection.4.3.3}
\contentsline {subsection}{\numberline {4.3.4}\leavevmode {\color {Chapter }IsContainedLang}}{29}{subsection.4.3.4}
\contentsline {subsection}{\numberline {4.3.5}\leavevmode {\color {Chapter }AreDisjointLang}}{29}{subsection.4.3.5}
\contentsline {chapter}{\numberline {5}\leavevmode {\color {Chapter }Some functions involving automata}}{30}{chapter.5}
\contentsline {section}{\numberline {5.1}\leavevmode {\color {Chapter }From one type to another}}{30}{section.5.1}
\contentsline {subsection}{\numberline {5.1.1}\leavevmode {\color {Chapter }EpsilonToNFA}}{30}{subsection.5.1.1}
\contentsline {subsection}{\numberline {5.1.2}\leavevmode {\color {Chapter }EpsilonToNFASet}}{30}{subsection.5.1.2}
\contentsline {subsection}{\numberline {5.1.3}\leavevmode {\color {Chapter }EpsilonCompactedAut}}{31}{subsection.5.1.3}
\contentsline {subsection}{\numberline {5.1.4}\leavevmode {\color {Chapter }ReducedNFA}}{31}{subsection.5.1.4}
\contentsline {subsection}{\numberline {5.1.5}\leavevmode {\color {Chapter }NFAtoDFA}}{32}{subsection.5.1.5}
\contentsline {subsection}{\numberline {5.1.6}\leavevmode {\color {Chapter }FuseSymbolsAut}}{32}{subsection.5.1.6}
\contentsline {section}{\numberline {5.2}\leavevmode {\color {Chapter }Minimalization of an automaton}}{32}{section.5.2}
\contentsline {subsection}{\numberline {5.2.1}\leavevmode {\color {Chapter }UsefulAutomaton}}{33}{subsection.5.2.1}
\contentsline {subsection}{\numberline {5.2.2}\leavevmode {\color {Chapter }MinimalizedAut}}{33}{subsection.5.2.2}
\contentsline {subsection}{\numberline {5.2.3}\leavevmode {\color {Chapter } MinimalAutomaton}}{33}{subsection.5.2.3}
\contentsline {subsection}{\numberline {5.2.4}\leavevmode {\color {Chapter }AccessibleStates}}{34}{subsection.5.2.4}
\contentsline {subsection}{\numberline {5.2.5}\leavevmode {\color {Chapter }AccessibleAutomaton}}{34}{subsection.5.2.5}
\contentsline {subsection}{\numberline {5.2.6}\leavevmode {\color {Chapter }IntersectionLanguage}}{35}{subsection.5.2.6}
\contentsline {subsection}{\numberline {5.2.7}\leavevmode {\color {Chapter }AutomatonAllPairsPaths}}{35}{subsection.5.2.7}
\contentsline {chapter}{\numberline {6}\leavevmode {\color {Chapter }Finite regular languages}}{37}{chapter.6}
\contentsline {section}{\numberline {6.1}\leavevmode {\color {Chapter }Dealing with finite regular languages}}{37}{section.6.1}
\contentsline {subsection}{\numberline {6.1.1}\leavevmode {\color {Chapter }IsFiniteRegularLanguage}}{37}{subsection.6.1.1}
\contentsline {subsection}{\numberline {6.1.2}\leavevmode {\color {Chapter }FiniteRegularLanguageToListOfWords}}{37}{subsection.6.1.2}
\contentsline {subsection}{\numberline {6.1.3}\leavevmode {\color {Chapter }ListOfWordsToAutomaton}}{37}{subsection.6.1.3}
\contentsline {chapter}{\numberline {A}\leavevmode {\color {Chapter }Directed graphs}}{39}{appendix.A}
\contentsline {section}{\numberline {A.1}\leavevmode {\color {Chapter }Directed graphs}}{39}{section.A.1}
\contentsline {subsection}{\numberline {A.1.1}\leavevmode {\color {Chapter }RandomDiGraph}}{40}{subsection.A.1.1}
\contentsline {subsection}{\numberline {A.1.2}\leavevmode {\color {Chapter }VertexInDegree}}{40}{subsection.A.1.2}
\contentsline {subsection}{\numberline {A.1.3}\leavevmode {\color {Chapter }VertexOutDegree}}{40}{subsection.A.1.3}
\contentsline {subsection}{\numberline {A.1.4}\leavevmode {\color {Chapter }AutoVertexDegree}}{40}{subsection.A.1.4}
\contentsline {subsection}{\numberline {A.1.5}\leavevmode {\color {Chapter }ReversedGraph}}{40}{subsection.A.1.5}
\contentsline {subsection}{\numberline {A.1.6}\leavevmode {\color {Chapter }AutoConnectedComponents}}{41}{subsection.A.1.6}
\contentsline {subsection}{\numberline {A.1.7}\leavevmode {\color {Chapter }GraphStronglyConnectedComponents}}{41}{subsection.A.1.7}
\contentsline {subsection}{\numberline {A.1.8}\leavevmode {\color {Chapter }UnderlyingMultiGraphOfAutomaton}}{41}{subsection.A.1.8}
\contentsline {subsection}{\numberline {A.1.9}\leavevmode {\color {Chapter }UnderlyingGraphOfAutomaton}}{42}{subsection.A.1.9}
\contentsline {subsection}{\numberline {A.1.10}\leavevmode {\color {Chapter }DiGraphToRelation}}{42}{subsection.A.1.10}
\contentsline {subsection}{\numberline {A.1.11}\leavevmode {\color {Chapter }MSccAutomaton}}{42}{subsection.A.1.11}
\contentsline {subsection}{\numberline {A.1.12}\leavevmode {\color {Chapter }AutoIsAcyclicGraph}}{43}{subsection.A.1.12}
\contentsline {chapter}{\numberline {B}\leavevmode {\color {Chapter } Drawing automata }}{44}{appendix.B}
\contentsline {section}{\numberline {B.1}\leavevmode {\color {Chapter } Installing some external programs }}{44}{section.B.1}
\contentsline {section}{\numberline {B.2}\leavevmode {\color {Chapter } Functions to draw automata }}{44}{section.B.2}
\contentsline {subsection}{\numberline {B.2.1}\leavevmode {\color {Chapter }DrawAutomaton}}{44}{subsection.B.2.1}
\contentsline {subsection}{\numberline {B.2.2}\leavevmode {\color {Chapter }DrawAutomata}}{46}{subsection.B.2.2}
\contentsline {subsection}{\numberline {B.2.3}\leavevmode {\color {Chapter }DrawGraph}}{46}{subsection.B.2.3}
\contentsline {subsection}{\numberline {B.2.4}\leavevmode {\color {Chapter }DrawSCCAutomaton}}{46}{subsection.B.2.4}
\contentsline {section}{\numberline {B.3}\leavevmode {\color {Chapter }Drawings output formats}}{46}{section.B.3}
\contentsline {section}{\numberline {B.4}\leavevmode {\color {Chapter }Drawings extra graph attributes}}{47}{section.B.4}
\contentsline {chapter}{\numberline {C}\leavevmode {\color {Chapter }Inverse automata and subgroups of the free group}}{48}{appendix.C}
\contentsline {section}{\numberline {C.1}\leavevmode {\color {Chapter }From subgroups to inverse automata}}{48}{section.C.1}
\contentsline {subsection}{\numberline {C.1.1}\leavevmode {\color {Chapter }GeneratorsToListRepresentation}}{48}{subsection.C.1.1}
\contentsline {subsection}{\numberline {C.1.2}\leavevmode {\color {Chapter }ListToGeneratorsRepresentation}}{48}{subsection.C.1.2}
\contentsline {subsection}{\numberline {C.1.3}\leavevmode {\color {Chapter }FlowerAutomaton}}{49}{subsection.C.1.3}
\contentsline {subsection}{\numberline {C.1.4}\leavevmode {\color {Chapter }FoldFlowerAutomaton}}{49}{subsection.C.1.4}
\contentsline {subsection}{\numberline {C.1.5}\leavevmode {\color {Chapter }SubgroupGenToInvAut}}{49}{subsection.C.1.5}
\contentsline {section}{\numberline {C.2}\leavevmode {\color {Chapter }From inverse automata to subgroups}}{50}{section.C.2}
\contentsline {subsection}{\numberline {C.2.1}\leavevmode {\color {Chapter }GeodesicTreeOfInverseAutomaton}}{50}{subsection.C.2.1}
\contentsline {subsection}{\numberline {C.2.2}\leavevmode {\color {Chapter }InverseAutomatonToGenerators}}{50}{subsection.C.2.2}
\contentsline {chapter}{References}{51}{appendix*.5}
\contentsline {chapter}{Index}{52}{section*.6}