Title: Theory / Unimportant / CS / Fundamental / Automata / Finite / Sakarovitch / 1 - the Three stages of rationnality
Tags: fromMath mathToDef rationalIdentities hasSeenConjDef fromAlgorithm hasNotNewEffectReturnsMeaning mathToSee autSingle defToAut closed StateAlphabetTransitionInitialTerminal autDo autDone duplicateToOtherBook examplesSwitchExample1 fromImplementation fromImplication markedrationalIdentities oldAlgoNewName récupéré toBinaryFunction toBinaryRelation typToBinary

Name: An initial state
Page: 52
Chapter: 1
Section: 1.1
Representation: an initial arrow

Name: A final state
Page: 52
Chapter: 1
Section: 1.1
Representation: an outer arrow

Name: A finite automaton
Definition: An automaton \(\mathcal A=\langle Q,A,E,I,T\rangle\) such that \(E\) is finite.
Page: 52
Chapter: 1
Section: 1.1

Name: A sub-automaton of \(\mathcal A\)
Definition: For some \(R\subseteq Q\), the automaton \(\langle R,A,E\cap (R\times A\times R), I\cap R, T\cap R\rangle\).
Page: 53
Chapter: 1
Section: 1.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 2
Kind: Def

Name: The transition matrix of \(\mathcal A\)
Definition: A square matrix of dimension \(|Q|\) whose \(p,q\) entry is the set of labels of transitions that go from \(p\) to \(q\).
Page: 54
Chapter: 1
Section: 1.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 3
Kind: Def

Name: The representation of \(A\) using its transition matrix
Definition: \(\langle I,E,T\rangle\) where \(I\) is a row-vector with \(I_p\) being 0 or 1 depending of whether \(p\in I\). \(T\) is the column-vector defined similarly. \(E\) is the transition matrix.
Page: 54
Chapter: 1
Section: 1.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 3
Kind: Def

Definition: \((p,a,q)\in E\).
Page: 54
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Notation: \(p\xrightarrow aq\)
Notation2: \(p\xrightarrow[\mathcal A] aq\)

Name: A computation in \(\mathcal A\)
Definition: \(c:=p_0\xrightarrow {a_1}\dots\xrightarrow{a_n}p_n\).
Page: 54
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 4
Kind: Def

Name: The length of the computation
Definition: \(n\).
Page: 54
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Let \(c:=p_0\xrightarrow {a_1}\dots\xrightarrow{a_n}p_n\) a computation
Index: 4
Kind: Def

Name: The label of the computation
Definition: \(a_1\dots a_n\).
Page: 54
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Let \(c:=p_0\xrightarrow {a_1}\dots\xrightarrow{a_n}p_n\) a computation
Index: 4
Kind: Def

Definition: There exists a computation \(c:=p_0\xrightarrow {a_1}\dots\xrightarrow{a_n}p_n\) .
Page: 54
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Notation: \(c:=p_0\xrightarrow {a_1\dots a_n}p_n\)
Index: 4
Kind: Def

Name: The label of \(e\)
Definition: \(a\).
Page: 54
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
\(e=(p,a,q)\in E\)
Index: 4
Kind: Def

Name: A successful computation
Definition: A computation \(c:=p_0\xrightarrow {a_1}\dots\xrightarrow{a_n}p_n\) with \(p_0\in I\) and \(p_n\in F\).
Page: 54
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Index: 4
Kind: Def

Name: A word accepted by \(\mathcal A\)
Definition: The label of a successful computation.
Page: 54
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Index: 4
Kind: Def
Name2: A word recognised by \(\mathcal A\)

Name: A recognisable language
Definition: recognised by a finite automaton
Page: 54, 109, 119, 64, 228
Chapter: 1, 3, 3, 1, 1
Section: 1.2, 3, 4.1, 2.3, 3
Index: 6, 3, 4,9
Kind: Def, Theo, Prop, Prop
Definition2: satisfying \(\mathfrak E_h\), \(\mathfrak E'_h\) or \(\mathfrak J_h\) for some \(h\in\mathbb N\) (assuming that the monoid is the free monoid of a finite alphabet)
Conjdef: A language, equivalently
Definition3: rational
Definition4: unambiguously rational
Definition5: Have a finite number of quotient
Definition6: image of a local language under a strictly alphabetic morphism

Name: A recognisable language in \(\{1\}^*\)
Definition: A set of words of length \(n\in S\), for \(S\) the union of a finite set and a finite union of arithmetic progressions of the same period (for an alphabet of cardinality one)
Page: 54, 109, 119
Chapter: 1, 3, 3
Section: 1.2, 3, 4.1
Variables: \(A=\{1\}\) an alphabet of cardinality one
Index: 6, 3
Kind: Def, Theo

Smaller0: \(\mathcal A\) accepts the empty word
Greater0: \(I\) intersects \(T\)
Page: 55
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Kind: Prop
Smaller to greater: iff

Name: The language accepted by \(\mathcal A\)
Definition: The set of words accepted by \(\mathcal A\).
Page: 55
Chapter: 1
Section: 1.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Notation: \(L(\mathcal A)\)
Index: 5
Kind: Def
Name2: The behaviour of \(\mathcal A\)
Notation2: [$]\abs{\mathcal A}[/$]

Name: Two equivalent automata
Definition: Two automata \(\mathcal A\) and \(\mathcal A'\) such that \(L(\mathcal A)=L(\mathcal A')\).
Page: 55
Chapter: 1
Section: 1.2
Index: 5 (ii)
Kind: Def

Smaller0: \(\mathcal B\) is a subautomata of \(\mathcal A\)
Greater0: \(L(\mathcal B)\subseteq L(\mathcal A)\)
Page: 56
Chapter: 1
Section: 1.2
Variables: \(\mathcal A\),
\(\mathcal B\), automata
Index: 2
Kind: Prop

Name: The set of recognisable languages over the alphabet \(A\)
Page: 56
Chapter: 1
Section: 1.2
Variables: \(A\) an alphabet
Notation: Rec \(A^*\)
Index: 6
Kind: Def

Question: \(\{f\}\) is recognised by
Answer: an automaton of length \(|f|+1\).
Page: 57
Chapter: 1
Section: 1.2
Variables: \(A\) an alphabet
\(f\in A^*\)
Index: 3
Kind: Prop

Page: 58
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Section: 1.3
Chapter: 1
Transitions: \(\{(p,a,q)\mid (q,a,p)\in E\}\)
States: \(Q\)
Initial: \(T\)
Name: The transpose of \(\mathcal A\)
Notation: \(\mathcal A^t\)
Final: \(I\)
Alphabet: \(A\)

Question: \(L(\mathcal A^t)\) equals
Answer: the mirror of \(L(\mathcal A)\).
Page: 58
Chapter: 1
Section: 1.3
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,

Name: recognisable languages
Page: 58, 61, 61, 64, 81, 91
Section: 1.3, 2.1, 2.2, 2.3, 4.3, 2.2
Chapter: 1, 1, 1, 1, 1, 2
Index: 1,2, 4, 5, 7, 8, 18, 5, 3
Kind: Prop, Prop, Prop, Prop, Prop, Prop, Prop, Prop, Cor
Under: mirror
Under2: union
Condition2: finite
Under3: intersection
Under4: languages
Condition4: arbitrary
Under5: shuffle
Under6: infiltration
Under7: taking set of suffixes, prefixes, factors
Under8: taking set of subwords
Under9: star
Under10: complementation
Under11: finite languages

Name: The union of \(\mathcal A\) and \(\mathcal A'\)
Definition: \(\langle Q\cup Q', A,E'\cup E', I\cup I', T\cup T'\rangle\).
Page: 58
Chapter: 1
Section: 2.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\), \(\mathcal A'=\langle Q',A,E',I',T'\rangle\) automata,
Notation: \(\mathcal A\cup\mathcal A'\)

Smaller0: \(L(\mathcal A\cup\mathcal A')\)
Greater0: \(L(\mathcal A)\cup L(\mathcal A')\)
Page: 60
Chapter: 1
Section: 2.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\), \(\mathcal A'=\langle Q',A,E',I',T'\rangle\) automata,
Smaller to greater: =

Page: 61
Variables: \(\mathcal A_i=\langle Q_i,A,E_i,I_i,T_i\rangle\)
Section: 2.2
Chapter: 1
Transitions: \(((p_i),a,(q_i))\mid (p_i,a,q_i)\in E_i)\)
States: \(\prod Q_i\)
Initial: \(\prod I_i\)
Name: The cartesian product of the \(\mathcal A_i\)'s
Notation: \(\prod\mathcal A\)
Final: \(\prod T_i\)
Alphabet: \(A\)
Name2: The direct product of the \(\mathcal A_i\)'s

Smaller0: \(L(\mathcal A\times \mathcal A')\)
Greater0: \(L(\mathcal A)\cap L(\mathcal A')\)
Page: 61
Chapter: 1
Section: 2.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\), \(\mathcal A'=\langle Q',A,E',I',T'\rangle\) automata,
Smaller to greater: =

Question: \(L(\mathcal A\times \mathcal A)\)
Answer: \(L(\mathcal A)\)
Page: 62
Chapter: 1
Section: 2.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,

Name: The (left) quotient of \(g\) by \(f\)
Definition: if \(g=fh\) then \(h\), otherwise undefined.
Page: 63
Chapter: 1
Section: 2.3
Variables: \(A\) an alphabet
\(f,g\in A^*\)
Context: Finite word
Notation: \(f^{-1}g\)

Question: \(f^{-1}f=\)
Answer: \(1_{A^*} \).
Page: 63
Chapter: 1
Section: 2.3
Variables: \(A\) an alphabet,
\(f\in A^*\)

Name: A state accessible in \(\mathcal A\) by \(f\)
Definition: A state \(q\) such that \(i\xrightarrow f q\) for some \(i\in I\)
Page: 63
Chapter: 1
Section: 2.3
Variables: \(A\) an alphabet,
\(f\in A^*\),
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton

Name: The set of states accessible in \(\mathcal A\) by \(f\)
Page: 63
Chapter: 1
Section: 2.3
Variables: \(A\) an alphabet,
\(f\in A^*\),
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Notation: \(I_f\)

Page: 63
Variables: \(A\) an alphabet,
\(f\in A^*\),
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Section: 2.3
Chapter: 1
Transitions: \(E\)
States: \(Q\)
Initial: \(I_f\)
Notation: \(f^{-1}\mathcal A\)
Final: \(T\)
Alphabet: \(A\)

Smaller0: \(f^{-1}L(\mathcal A)\)
Greater0: \(L(f^{-1}\mathcal A)\)
Page: 63
Chapter: 1
Section: 2.3
Variables: \(A\) an alphabet,
\(f\in A^*\),
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Smaller to greater: =

Name: The quotient of \(L\) by \(K\)
Definition: \(\bigcup_{f\in K}f^{-1}L\)
Page: 64
Chapter: 1
Section: 2.3
Variables: \(A\) an alphabet,
\(K,L\subseteq A^*\)
Notation: \(K^{-1}L\)

Page: 65
Section: 2.3
Notation: \(f\between g\)
Variables: \(A\) an alphabet,
\(f,g\in A^*\)
Chapter: 1
Name: The shuffle of \(f\) and \(g\)
Definition: \(\{f_1g_1\dots f_ng_n\mid f_i,g_i\in A^*, f_1\dots f_n=f, g_1\dots g_n=g\}\)
Associative: Associative
Extra: second notation and associativity from Automata Theory, Pin p 145
Notation2: [$]f\textvisiblespace\textvisiblespace g[/$]

Name: The shuffle of \(K\) and \(L\)
Definition: \(\bigcup_{f\in L,g\in K}f\between g\)
Page: 65
Chapter: 1
Section: 2.3
Variables: \(A\) an alphabet,
\(K,L\subseteq A^*\) languages
Notation: \(K\between L\)
Index: 7
Kind: Def

Name: The infiltration of \(f\) and \(g\)
Definition: \(\{h\in A^*\mid \exists F,G\subseteq [|h|], F\cup G=[|h|], h_F=f, h_G=g\}\)
Page: 66
Chapter: 1
Section: 2.3
Variables: \(A\) an alphabet,
\(f,g\in A^*\)
Notation: \(f\uparrow g\)
Index: 8
Kind: Def

Name: The infiltration of \(F\) and \(G\)
Definition: \(\bigcup_{f\in F,g\in G}f\uparrow g\)
Page: 66
Chapter: 1
Section: 2.3
Variables: \(A\) an alphabet,
\(F,G\subseteq A^*\)
Context: Automata theory
Notation: \(F\uparrow G\)
Index: 8
Kind: Def

Name: \(p\) is accessible from \(q\)
Definition: There is a computation in \(\mathcal A\) whose source is \(q\) and whose destination is \(p\).
Page: 67
Chapter: 1
Section: 3.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
\(p,q\in Q\)
Index: 9
Kind: Def

Name: An accessible state
Definition: A state accessible from an initial state.
Page: 67
Chapter: 1
Section: 3.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 9
Kind: Def

Name: A co-accessible state
Definition: A state co-accessible to a final state.
Page: 67
Chapter: 1
Section: 3.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
\(p,q\in Q\)
Index: 9
Kind: Def

Question: The set of accessible of \(\mathcal A^t\) is
Answer: the set of co-accessible state of \(\mathcal A\).
Page: 67
Chapter: 1
Section: 3.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 5
Kind: Prop

Question: The set of useful states of \(\mathcal A^t\) is
Answer: the set of useful state of \(\mathcal A\).
Page: 67
Chapter: 1
Section: 3.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 5
Kind: Prop

Name: A (co-)accessible automaton
Definition: An automaton whose every states are (co-)accessible.
Page: 67
Chapter: 1
Section: 3.1
Index: 10
Kind: Def

Name: A trim automaton
Definition: An automaton whose every states are useful.
Page: 67
Chapter: 1
Section: 3.1
Index: 10
Kind: Def

\(\mathcal A\) is equivalent to:
-a trim automaton,
-a complete accessible automaton,
-a normalized automaton, apart maybe for the empty word
-an automaton in standard form,
-a deterministic automaton.
Page: 68, 77, 88, 93, 105
Chapter: 1, 1, 2,2, 3
Section: 3.1, 4.2, 3.1, 3.3, 2.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Index: 9, 6, 3, 6, 2
Kind: Prop, Prop, Lem, Lem, Prop

Smaller0: \(L(\mathcal A)\) is infinite
Greater0: \(\mathcal A\) contains words of length at least [$]\norm{Q}[/$]
Page: 69, 70
Chapter: 1
Section: 3.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Smaller to greater: iff

Page: 70
Implementation: Test for accessibility of final state from initial state
Section: 3.2
Chapter: 1
Effect: Whether \(\mathcal A\) is empty
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Time complexity: \(O(|Q|+|E|)\).
Index: 11 (i)
Kind: Prop

Page: 70
Implementation: Test for the existence of an accepting path containing a cycle
Section: 3.2
Chapter: 1
Effect: Whether \(\mathcal A\) is finite
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Time complexity: \(O(|Q|+|E|)\).
Index: 11 (i)
Kind: Prop

Page: 70
Implementation: By fixpoint, compute the set of accessible and of co accessible states
Section: 3.2
Chapter: 1
Effect: Trimming \(\mathcal A\)
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Time complexity: \(O(|Q|+|E|)\).
Index: 11 (ii)
Kind: Prop

Smaller0: \(L\) is recognisable
Greater0: there exists an integer \(N\) such that for every \(f\in L\), and every factorization of the form \(f=uv_1\dots v_Nw\), where the \(v_i\ne1_{A^*}\), there is a pair \((j,k)\) of indices \(0\le j<k\le N\) such that \(uv_1\dots v_j(v_{j+1}\dots v_k)^*v_{k+1}\dots v_N w\subseteq L\)
Page: 70
Chapter: 1
Section: 3.2
Variables: \(L\) a language
Index: 14
Kind: Lem
Name: Block star lemma

Name: An unambiguous automaton
Definition: -for every \(p,q\in Q\), every \(f\in A^*\) there exists at most one computation from \(p\) to \(q\) labelled \(f\),
-for every word \(f\in L(\mathcal A)\), there exists a unique \(i\in I\), \(t\in T\) such that \(i\xrightarrow f t\).
Page: 74
Chapter: 1
Section: 4.1
Index: 11
Kind: Def
Definition2: for all \(f\in L(\mathcal A)\) there exists a unique successful computation in \(\mathcal A\) with label \(f\) (assuming \(\mathcal A\) trim)
Conjdef: An automaton \(\mathcal A=\langle Q,A,E,I,T\rangle\) such that, equivalently

Page: 75
Implementation: Compute \(\mathcal {A\times A}\)
Compute its set of accessible state
If it contains a state \((p,q)\) with \(p\ne q\), rejects
Section: 4.1
Chapter: 1
Effect: Whether \(\mathcal A\) is unambiguous
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Time complexity: \(O(|Q|^2|A|)\).
Index: 15
Kind: Prop

Name: A complete automaton
Definition: for all \(p\in Q\), \(a\in A\), there exists \(q\in Q\) such that \((p,a,q)\in E\),
Page: 75, 76
Chapter: 1
Section: 4.2
Definition2: for all \(p\in Q\), \(f\in A^*\), there exists \(q\in Q\) such that \(p\xrightarrow fq\)
Conjdef: An automaton \(\mathcal A=\langle Q,A,E,I,T\rangle\) such that, equivalently
Assuming: \(\mathcal A\) is trim

Name: The completion of \(\mathcal A\)
Definition: If \(\mathcal A\) is complete, \(\mathcal A\).
Page: 76
Chapter: 1
Section: 4.2
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Notation: \(\mathcal A_c\)
Definition2: Otherwise, \(\langle Q\cup\{z\}, A, E\cup \{(p,a,z)\in Q\cup\{z\},a\in A\mid\forall q\in Q, (p,a,q)\not\in E \},I,T\rangle\)
Conjdef: either

Name: A co-complete automaton
Definition: An automaton whose transpose is complete.
Page: 77
Chapter: 1
Section: 4.2
Index: 13
Kind: Rem

Name: A deterministic automaton
Definition: for all \(p\in Q\), and all \(a\in A\), there exists at most one transition in \(E\) with source \(p\) and label \(a\) and
there is at most one initial state.
Page: 77, 78
Chapter: 1
Section: 4.3
Index: 13, 7
Kind: Def, Prop
Definition2: the accessible part of \(\mathcal A\times \mathcal A\) is \(\{(q,q)\mid q\in Q\}\)
Conjdef: An automaton \(\mathcal A=\langle Q,A,E,I,T\rangle\) such that, equivalently

Smaller0: \(\mathcal A\) is (co-)deterministic
Greater0: \(\mathcal A\) is unambiguous
Page: 78
Chapter: 1
Section: 4.3
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 8, 9
Kind: Prop

Name: A co-deterministic automaton
Definition: An automaton \(\mathcal A\) such that \(\mathcal A^t\) is deterministic.
Page: 78
Chapter: 1
Section: 4.3
Index: 8
Kind: Prop

Name: The set of deterministic automata
Page: 78
Section: 4.3
Chapter: 1
Index: 10
Kind: Prop
Under: product.

Name: An automaton with spontaneous transition
Definition: \(\mathcal A=\langle Q,A,E,S,I,T\rangle\) such that \(\langle Q,A,E,I,T\rangle\) is an automaton and \(S\subseteq Q\times Q\) is the set of spontaneous transition.
Page: 79
Chapter: 1
Section: 4.3

Name: The graph obtained by forward closure
Definition: \(\langle Q,A,\{(p,a,q)\mid p\xrightarrow{a }v_1\xrightarrow{1_{A^*} }\dots\xrightarrow{1_{A^*} }q\},\{q\mid i\in I, i\xrightarrow{1_{A^*} }\dots\xrightarrow{1_{A^*} }q\},T\rangle\).
Page: 80
Chapter: 1
Section: 4.3
Variables: \(\mathcal A=\langle Q,A,E,S,I,T\rangle\) a graph with spontaneous transition

Name: The graph obtained by backward closure
Definition: \(\langle Q,A,\{(p,a,q)\mid p\xrightarrow{1_{A^*} }\dots\xrightarrow{1_{A^*} }v_n\xrightarrow{a }q\},I,\{q\mid f\in I, q\xrightarrow{1_{A^*} }\dots\xrightarrow{1_{A^*} }f\}\rangle\).
Page: 80
Chapter: 1
Section: 4.3
Variables: \(\mathcal A=\langle Q,A,E,S,I,T\rangle\) a graph with spontaneous transition

Name: Their product
Definition: \(\{fg\mid f\in X,g\in Y\}\)
Page: 82
Chapter: 2
Section: 1.1
Variables: \(A\) an alphabet,Let \(X,Y\) languages
Notation: \(X\cdot Y\)

Name: Its \(n\)th power
Definition: \(1_{A^*}\) if \(n=0\), \(X\cdot X^{n-1}\) otherwise.
Page: 82
Chapter: 2
Section: 1.1
Variables: \(A\) an alphabet,Let \(X\) a language,
\(n\in\mathbb N\)
Notation: \(X^n\)

Definition: \(\bigcup_{i=0}^{n}X^i\).
Page: 82
Chapter: 2
Section: 1.1
Variables: \(A\) an alphabet,\(X\) a language,
\(n\in\mathbb N\)
Notation: \(X^{\le n}\)

Name: Its star
Definition: \(\bigcup_{i=0}^{\infty}X^i\).
Page: 82
Chapter: 2
Section: 1.1
Variables: \(A\) an alphabet,Let \(X\) a language,
Notation: \(X^{*}\)

Name: Its proper star
Definition: \(\bigcup_{i=1}^{\infty}X^i\).
Page: 83
Chapter: 2
Section: 1.1
Variables: \(A\) an alphabet,Let \(X\) a language,
Notation: \(X^{+}\)

Name: The rational operations on \(A^*\)
Definition: Union
Page: 84
Chapter: 2
Section: 1.3
Variables: \(A\) an alphabet
Definition2: product
Conjdef: all of
Definition3: star

Name: A rationally closed family of languages
Definition: A family \(\mathcal F\subseteq\mathfrak B(A^*)\) such that, for all \(X,Y\in\mathcal F\), \(X+Y,XY,X^*\in\mathcal F\).
Page: 86
Chapter: 2
Variables: \(A\) an alphabet
Kind: Def

Name: The rational closure of \(\mathcal F\)
Definition: The smallest rationally closed family containing \(\mathcal F\).
Page: 86
Chapter: 2
Variables: \(A\) an alphabet,
\(\mathcal F\subseteq\mathfrak B(A^*)\)
Kind: Def
Abbreviation: \(\text{Rat }F\)

Name: Kleene
Definition: \(L\) is recognisable iff \(L\) is rational
Page: 87
Chapter: 2
Variables: \(A\) an alphabet,
\(L\subseteq A^*\)
Index: 1
Kind: Theo
Property: \(\{f^{-1}L\mid f\in A^*\}\) is finite

Smaller0: \(L\) is recognisable
Greater0: \(L\) is rational
Page: 87, 114
Chapter: 2, 3
Section: 2, 3.2
Variables: \(A\) an alphabet,
\(L\subseteq A^*\)
Index: 1, 10
Kind: Theo, Prop
Smaller to greater: iff
Smallest: \(\{f^{-1}L\mid f\in A^*\}\) is finite

Name: A normalized automaton
Definition: An automaton such that:
-\(I=\{i\}\) and \(i \) is not the destination of any transititon,
-\(F=\{f\}\) and \(f\ne i \) is not the source of any transititon.
Page: 87
Chapter: 2
Variables: \(A\) an alphabet
Index: 3
Kind: Def

Name: A standard automaton
Definition: An automaton such that:
-\(I=\{i\}\) and \(i\) is not the destination of any transititon.
Page: 92
Chapter: 2
Section: 3.3
Variables: \(A\) an alphabet
Index: 4
Kind: Def

Name: A generalized automaton
Definition: A 5-tuple \(\mathcal A=\langle Q,A,E,I,T\rangle\), similar to automata, apart that \(E\subseteq Q\times \mathfrak B(A^*)\times Q\).
Page: 97
Chapter: 2
Section: 4.2
Variables: \(A\) an alphabet

Question: The set of solutions of \(X=KX+L\) is
Answer: \(\{K^*L\}\).
Page: 100
Chapter: 2
Section: 4.2
Variables: \(A\) an alphabet,
\(K,L\) languages
Index: 9
Kind: Lem
Assuming: \(1_{A^*}\not\in K\)
Name: Arden

Name: The elimination of \(q\)
Definition: \(\langle Q\setminus\{q\}, A, \{(p,f+ gh^*i,r)\mid (p,f,r), (p,g,q), (q,h,q), (q,i,r)\in E\}, I,T\rangle\).
Page: 98
Chapter: 2
Section: 4.2
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) a generalized automaton,
\(q\in Q\setminus(I\cup F)\)
Index: 8
Kind: Prop

Definition: The set of labels of path from \(q\) to an accepting state.
Page: 99
Chapter: 2
Section: 4.3
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) a generalized automaton
\(q\in Q\)
Notation: \(L_q\)
Index: 8
Kind: Prop

Name: The equation associated to \(\mathcal A\)
Definition: \(L_p=\oplus_{(p,f,q)\in E}fL_q+ \{1_{A^*}\mid \text{if }p\in F\}\) for each state \(p\).
Page: 99
Chapter: 2
Section: 4.3
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) a generalized automaton

Name: The transition function of \(\mathcal A\)
Definition: [$]\defFun{Q\times A}{\mathfrak B(Q)}{(p,a)}{\{q\in Q\mid (pa,aq)\in E\}}[/$].
Page: 102
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Context: Determinization
Notation: \(\delta\)

Name: The representation of the transition function of \(\mathcal A\)
Definition: A table, whose lines are indexed by letters and columns by states.
Page: 102
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton

Question: \((P,fg)\delta=\)
Answer: \(((P,f)\delta,g)\delta\).
Page: 103
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
\(f,g\) words,
\(P\subseteq Q\)

Question: \((P,f)\delta=\)
Answer: \(\{q\mid \exists p\in P p\xrightarrow{f}q\} \).
Page: 103
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
\(f\) a word,
\(P\subseteq Q\)

Page: 106
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
Section: 1
Chapter: 3
States: \(\langle\mathfrak B(Q),A,\delta,I,\{U\subseteq Q\mid U\cap F\ne\emptyset\}\rangle\).
Name: The determinisation of \(\mathcal A\)
Notation: \(\mathcal A_{\text{det} }\)
Kind: Def
Index: 2

Smaller0: \(\mathcal A\) is co-accessible
Greater0: \(F\) is co-accessible in the determinisation of \(\mathcal A\)
Page: 107
Chapter: 3
Section: 2.2
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
\(F\subseteq Q\)
Index: 4
Kind: Prop
Smaller1: \(F\ne\emptyset\)
Smaller2: \(F\) occurs in \(\mathcal A_{\mathrm{det}}\)

Smaller0: \(A^*\setminus L(\mathcal A) \)
Greater0: \(\langle Q,A,E,I,Q\setminus T\rangle\)
Page: 109
Chapter: 2.4
Section: 3
Variables: \(A\) an alphabet,
Let \(\mathcal A=\langle Q,A,E,I,T\rangle\)
Index: 5
Kind: Prop
Smaller to greater: is recognised by
Hide middle: yes
Assuming: \(\mathcal A\) deterministic
Greater to smaller: recognise

Smaller0: \(1_{A^*}\in w^{-1}X\)
Greater0: \(w\in X\)
Page: 112
Chapter: 3.1
Section: 3
Variables: \(A\) an alphabet,
\(X\subseteq A^*\),
\(w\in A^*\)
Index: 6
Kind: Prop
Smaller to greater: iff

Smaller0: \((fg)^{-1}X\)
Greater0: \(g^{-1}(f^{-1}X)\)
Page: 112
Chapter: 3.1
Section: 3
Variables: \(A\) an alphabet,
\(X\subseteq A^*\),
\(f,g\in A^*\)
Index: 7
Kind: Prop
Smaller to greater: =

Name: The minimal automaton of \(L\)
Definition: \(\langle \{f^{-1}L\mid f\in A^*\}, A,(F,a)\mapsto a^{-1}F, L, \{F\mid 1_{A^*}\in F\}\rangle\).
Page: 112, 113
Chapter: 3.1, 3.2
Section: 3
Variables: \(A\) an alphabet,
\(L\subseteq A^*\)
Notation: \(\mathcal A_L\)

Smaller0: \(\mathcal A_L\)
Greater0: \(L\)
Page: 113
Chapter: 3.1
Section: 3
Variables: \(A\) an alphabet,
\(L\subseteq A^*\)
Index: 7
Kind: Prop
Smaller to greater: =
Prefix Smaller: \(L(\)
Suffix Smaller: \()\)

Name: Nerode's equivalence
Definition: \(\{(p,q)\mid L_p=L_q\}\).
Page: 114
Chapter: 3
Section: 3.3
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,\delta,i,T\rangle\) a deterministic automaton,
\(p\in Q\)
Notation: \(\sim\)
Kind: Def
Typ: Equivalence relation

Smaller0: \(p\sim q\)
Greater0: \(\forall f\in A^*, p\cdot f\sim q\cdot f\)
Page: 115
Chapter: 3
Section: 3.3
Variables: \(\mathcal A=\langle Q,A,\delta,i,T\rangle\) a deterministic automaton,
\(p,q\in Q\)
Index: 8
Kind: Prop
Greater1: (\(p\in T\iff q\in T\))

Question: \(\mathcal A/\nu\) is
Answer: isomorphic to \(\mathcal A_{L(\mathcal A)}\).
Page: 115
Chapter: 3
Section: 3.3
Variables: \(\mathcal A=\langle Q,A,\delta,i,T\rangle\) a deterministic automaton
Index: 11
Kind: Prop
Assuming: \(\mathcal A\) is complete

Page: 115
Implementation: \(\mathcal Q_0=\{Q\setminus T,T\}\),
\(\mathcal Q_{k+1}\) is the refinement of \(\mathcal Q_k\) such that, for all \(p,q\in Q\), \(p,q\) are connected in \(\mathcal Q_k\) and disconnected in \(\mathcal Q_{k+1}\) if there exists a letter \(a\in A\) such that \(p\cdot a\) and \(q\cdot a\) are disconnected in \(\mathcal Q_k\).
Output the first \(\mathcal Q_{k}\) such that \(\mathcal Q_{k}=\mathcal Q_{k+1}\).
Section: 3.3
Chapter: 3
Variables: \(\mathcal A=\langle Q,A,\delta,i,T\rangle\) a deterministic automaton
Name: Moore's algorithm
Returns: Minimal automaton of \(\mathcal A\): \(\mathcal A/\nu\)
Index: 12
Kind: Prop

Smaller0: co-deterministic co-accessible
Greater0: is minimal
Page: 117
Chapter: 3
Section: 3.4
Variables: \(\mathcal A=\langle Q,A,\delta,I,T\rangle\) an automaton
Index: 13
Kind: Prop
Prefix Greater: the determinisation of \(\mathcal A\)
Prefix Smaller: \(\mathcal A\) is
Construction: co-deterministic implies that a state corresponds to exactly one left quotient of \(L\), thus to a state of the minimal automaton.
Co-accessible shows that there is no useless state

Definition: The class of languages \(L\) such that, for every word \(f\in A^*\) and every factorisation of the form \(f=uv_1\dots v_hw\) with \(|v_i|\ge 1\forall i\in [h]\), there exists a pair of indices \((j,k),0\le j<k\le h\) such that \(uv_1\dots v_j(v_{j+1}\dots v_k)^nv_{k+1}\dots v_hw\in L\iff f\in L\), for all \(n\in\mathbb N\).
Page: 119
Chapter: 3
Section: 4.1
Variables: \(\mathcal A=\langle Q,A,\delta,i,T\rangle\) a deterministic automaton
Notation: \(\mathfrak E_h'(A^*)\)

Definition: The set of \(k\)-set of elements of \(E\)
Page: 119
Chapter: 3
Section: 4.1
Variables: \(X\) a set,
\(k\in\mathbb N\)
Notation: \(\mathfrak B_{k}(E)\)
Kind: Theo

Definition: For all integers \(k\), \(m\), \(r\), there exists an integer \(N=R(k,m,r)\) such that if a set \(E\) has at least \(N\) elements, for every partition \(\mathcal P\) of \(\mathfrak B_{(k)}(E)\) into \(m\) classes a subset of \(E\) with cardinality \(r\) can be found such that \(\mathfrak B_{(k)}(F)\) is completly contained in a single class of \(\mathcal P\).
Page: 120
Chapter: 3
Section: 4.1
Variables: \(X\) a set,
\(k\in\mathbb N\)
Notation: Ramsey's theorem
Index: 4
Kind: Theo

Definition: The set of languages over \(A\) such that for every word \(f\in A^h\), there exists a factorization \(uvw\) with \(v\) non-empty such that \(f\) and \(u(v)^nw\) have the same right quotients for every \(n\in\mathbb N\)
Page: 122
Chapter: 3
Section: 4.1
Variables: \(A\) an alphabet,
\(h\in\mathbb N\)
Notation: \(\mathfrak J'_h\)
Index: 4
Kind: Theo

Definition: The set of languages over \(A\) such that for every word \(f\in A^h\), there exists a factorization \(uvw\) with \(v\) non-empty such that \(f\) and \(uw\) have the same right quotients for every \(n\in\mathbb N\)
Page: 122
Chapter: 3
Section: 4.1
Variables: \(A\) an alphabet,
\(h\in\mathbb N\)
Notation: \(\mathfrak J_h\)
Index: 4
Kind: Theo

Name: A rational expression over \(A\)
Definition: A term over the alphabet \(\{0/0,1/0,+/2,\cdot/2,*/1\}\cup\{a/0\mid a\in A\}\)
Page: 124
Chapter: 4
Section: 1.1
Variables: \(A\) an alphabet
Index: 1
Kind: Def
Denoted by: \(\text{E}\)

Name: The depth of \(r\)
Definition: The function \(f\) sending atomic formula to \(0\), and \(A_1+A_2\), \(A_1\cdot A_2\) and \(A_1\) to \(1+\max\{A_i\}\)
Page: 125
Chapter: 4
Section: 1.1
Variables: \(A\) an alphabet,
\(r\in \text{RatE} A^*\)
Name2: The height of \(r\)

Name: The set of rational expression over \(A\)
Page: 124
Chapter: 4
Section: 1.1
Variables: \(A\) an alphabet
Notation: \(\text{RatE} A^*\)
Index: 1
Kind: Def

Name: The language denoted by \(\mathbf{E}\)
Definition: The morphism from \(\text{RatE}A^*\) to subsets of \(A^*\), sending \(0\) to \(\emptyset\), \(1\) to \(1_{A^*}\), \(a\) to \(a\), \(+\) to \(\cup\), \(\cdot\) to concatenation, \(*\) to \(*\)
Page: 125
Chapter: 4
Section: 1.1
Variables: \(A\) an alphabet,
\(\mathbf{E}\) a rational expression
Notation: \(L[\mathbf{E}]\)
Index: 2
Kind: Def
Notation2: \(|\mathbf{E}|\)

Question: Why do we consider \(a+b\) as distinct from \(a\cup b\), and in general rational expression from the language their denote ?
Answer: Computers manipulate expressions, not language.
Page: 126, 128
Chapter: 4
Section: 1.1
Answer2: Multiple expressions may lead to the same language.
Index: 2
Kind: Def
Answer3: Furthermore, this allows to use regexp on other monoids than \(A^*\)

Page: 126
Definition: Rational expressions denoting the same language
Chapter: 4
Section: 1.1
Variables: \(A\) an alphabet
Notation: \(\equiv\)
Name: Equivalent rational expressions
Kind: Def
Index: 3
Context: Rational expression
Definition2: \(L[\mathbf E]=L[\mathbf F]\)

Page: 127
Implementation: Converting them to automata and checking equivalence of automata
Section: 1.1
Chapter: 4
Effect: Deciding equivalence of rational expression
Variables: \(A\) an alphabet
r, r' regexp
Index: 1,1
Kind: Theo, rem

Smaller0: \(E\in\text{Rat}\mathcal C\)
Greater0: there exists a rational expression and an interpretation of it whose value is in \(\mathcal C\) and whose result is \(R\)
Page: 127
Chapter: 4
Section: 1.2
Variables: \(A\) an alphabet,
\(R\subseteq A^*\),\(\mathcal C \subseteq\mathcal P( A^*)\),
Smaller to greater: iff

Name: A rational expression over \(\mathcal X\)
Definition: Similar to rational expression, with elements of \(X\) as atom
Page: 127
Chapter: 4
Section: 1.2
Variables: \(A\) an alphabet,
\(\mathbf X\) a set of variables

Name: The set of variables occurring in \(\mathbf E\)
Page: 127
Chapter: 4
Section: 1.2
Variables: \(A\) an alphabet,
\(\mathbf X\) a set of variables
\(\mathbf E\) a rational expression over \(\mathcal X\)
Abbreviation: \(\text{Var}\mathbf{E}\)

Name: An interpretation of \(\mathbf E\) over \(A^*\)
Definition: A map from \(\text{Var}\mathbf{E}\) to \(\mathcal P(A^*)\)
Page: 127
Chapter: 4
Section: 1.2
Variables: \(A\) an alphabet,
\(\mathbf X\) a set of variables
\(\mathbf E\) a rational expression over \(\mathcal X\)
Denoted by: \(\tau\)

Name: The result of the interpretation
Definition: Defined by induction on \(\mathbf E\) with the new atomic rule \([x]\tau=x\tau\)
Page: 127
Chapter: 4
Section: 1.2
Variables: \(A\) an alphabet,
\(\mathbf X\) a set of variables
\(\mathbf E\) a rational expression over \(\mathcal X\)
\(\tau\) an interpretation of \(\mathbf E\) over \(A^*\)
Notation: \([\mathbf E]_\tau\)
Index: 4, 4
Kind: Def, Prop
Definition2: \((L[\mathbf E])_\tau\)

Name: The trivial identities of rational expressions
Definition: \(E\cdot 0=0\cdot E=0\), \(E+ 0=0+ E=E\)
Page: 129
Chapter: 4
Section: 2.1
Context: Identities
Notation: \((\mathbf T)\)
Kind: Def
Definition2: \(E\cdot 1=1\cdot E=E\)
Conjdef: All of

Name: The associative identities of rational expressions
Definition: The associative identities of sum and products
Page: 129
Chapter: 4
Section: 2.1
Context: Identities
Notation: \((\mathbf A)\)
Kind: Def

Name: The distributive identities of rational expressions
Definition: \((E+F)\cdot G=E\cdot G+F\cdot G\) and \(E\cdot G+ F\cdot G=E\cdot (F+G)\)
Page: 129
Chapter: 4
Section: 2.1
Context: Identities
Notation: \(\mathbf D\)
Kind: Def

Name: The commutative identity of rational expressions
Definition: \(E+F=F+E\)
Page: 129
Chapter: 4
Section: 2.1
Context: Identities
Notation: \(\mathbf C\)
Kind: Def

Name: The natural identity of rational expressions
Definition: trivial
Page: 129
Chapter: 4
Section: 2.1
Context: Identities
Kind: Def
Definition2: associative
Conjdef: All of
Definition3: commutative
Definition4: distributive

Name: The associative identity of sum
Definition: \((E+F)+G=E+(F+G)\)
Page: 130
Chapter: 4
Section: 2.1
Context: Identities
Notation: \(\mathbf {A_s}\)
Kind: Def

Name: The associative identity of sum
Definition: \((E+F)+G=E+(F+G)\)
Page: 130
Chapter: 4
Section: 2.1
Context: Identity
Notation: \(\mathbf {A_s}\)
Kind: Def

Name: The associative identity of product
Definition: \((EF)G=E(FG)\)
Page: 130
Chapter: 4
Section: 2.1
Context: Identity
Notation: \(\mathbf {A_p}\)
Kind: Def

Definition: \(E^*\equiv 1+EE^*\)
Page: 130
Chapter: 4
Section: 2.1
Context: Identities
Notation: \(\mathbf{U_l}\)
Kind: Def

Definition: \(E^*\equiv 1+E^*E\)
Page: 130
Chapter: 4
Section: 2.1
Context: Identities
Notation: \(\mathbf{U_r}\)
Kind: Def

Definition: \(0^*\equiv 1\)
Page: 130
Chapter: 4
Section: 2.1
Context: Identities
Notation: \(\mathbf{Y}\)
Kind: Def

Name: The aperiodic identities
Definition: \(\mathbf{S_r}\): \((E+F)^*\equiv (E^*F)^*E^*\)
\(\mathbf{S_l}\): \((E+F)^*\equiv E^*(FE^*)^*\)
Page: 130
Chapter: 4
Section: 2.1
Kind: Def
Definition2: \(\mathbf{P}\): \((EF)^*\equiv 1+E(FE)^*F\)
Conjdef: The identities

Name: The cyclic identities
Definition: \(E^*\equiv E^{<n}(E^n)^*\)
Page: 131
Chapter: 4
Section: 2.1
Context: Identities, rational sets
Notation: \(\mathbf {Z}_n\)
Kind: Def

Name: The idempotent identities
Definition: \(\mathbf {I}\): \(E+E\equiv E\)
Page: 131
Chapter: 4
Section: 2.1
Definition2: \(\mathbf J\) \(E^*\equiv (E^*)^*\)
Conjdef: Both

Name: Classical identities
Definition: The identities: natural, aperiodic, cyclic, \(\mathcal{U_l,U_r}\) and idempotent
Page: 132
Chapter: 4
Section: 2.1
Kind: Def

Definition: \(\mathbf{E\equiv F}\) can be derived from the other identities
Page: 132
Chapter: 4
Section: 2.1
Variables: \(\mathbf{X}\) a set of identities,
\(\mathbf{E\equiv F}\) an identity
Notation: \(\mathbf{X\vdash E\equiv F}\)
Kind: Def

Name: \(p\) is co accessible to a state \(q\)
Definition: There is a computation in \(\mathcal A\) whose source is \(p\) and whose destination is \(q\)
Page: 67
Chapter: 1
Section: 3.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
\(p,q\in Q\)
Index: 9
Kind: Def

Name: The set of rational languages
Definition: finite sets of \(A^*\)
Page: 86
Chapter: 2
Variables: \(A\) an alphabet,
\(\mathcal F\subseteq \mathfrak B(A^*)\)
Kind: Def
Definition2: elements of \(A^*\) and empty language
Conjdef: The rational closure of
Definition3: letters and empty languages.
Abbreviation: \(\text{Rat }A^*\)

Question: The language recognised by \(\mathcal A\) belongs to
Answer: the rational closure of the family of labels of transitions of \(\mathcal A\).
Page: 97
Chapter: 2
Section: 4.2
Variables: \(A\) an alphabet,
\(\mathcal A=\langle Q,A,E,I,T\rangle\) a generalized automaton
Index: 8
Kind: Prop

Name: An automaton over the alphabet \(A\)
Definition: A non-empty set \(Q\) called the set of states of \(\mathcal A\)
Page: 51
Chapter: 1
Section: 1.1
Variables: \(A\) an alphabet
Kind: Def
Definition2: A set \(A\), also non-empty, called the (input) alphabet of \(\mathcal A\)
Conjdef: \(\langle Q,A,E,I,T\rangle\) such that
Definition3: \(I\subseteq Q\) the set of initial states of \(\mathcal A\)
Definition4: \(F\subseteq Q\) the set of final states of \(\mathcal A\)
Definition5: A subset \(E\subseteq Q\times A\times Q\), called the set of transitions of \(\mathcal A\)

Question: The set of co-accessible sets of \(\mathcal A^t\) is equal to
Answer: the set of accessible state of \(\mathcal A\).
Page: 67
Chapter: 1
Section: 3.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 5
Kind: Prop

Smaller0: \(\mathcal A\) is unambiguous
Greater0: the trim part of \(\mathcal A\times \mathcal A\) is \(\{(q,q)\mid q\in Q\}\)
Page: 75
Chapter: 1
Section: 4.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton
Index: 16
Kind: Lem
Smaller to greater: iff
Assuming: \(\mathcal A\) is trim

Name: A useful state
Definition: \(q\) is accessible and co-accessible state
Page: 67
Chapter: 1
Section: 3.1
Variables: \(\mathcal A=\langle Q,A,E,I,T\rangle\) an automaton,
\(p,q\in Q\)
Index: 9, 5
Kind: Def, Prop
Definition2: there exists a successful computation which passes through \(q\)
Conjdef: A state \(q\) such that, equivalently

Name: Unambiguous automata
Page: 76
Section: 4.1
Chapter: 1
Extra: transpose means reversing arrows
Under: transpose
Under2: product ?