Title: Theory / Unimportant / CS / Fundamental / Automata / Finite / Sakarovitch / 4 - Relations=
Tags: fromMath mathToSee closed hasSeenConjDef

Name: Static way to consider \(\tau\)
Definition: Considering \(\tau\) as a subset of \(A^*\times B^*\)
Page: 525
Chapter: 1
Variables: \(A,B\) finite alphabets,
\(\tau\) a relation from \(A^*\) to \(B^*\)

Name: Dynamic way to consider \(\tau\)
Definition: Considering \(\tau\) as a subset function from \(A^*\) to \(\mathfrak P(B^*)\)
Page: 525
Chapter: 1
Variables: \(A,B\) finite alphabets,
\(\tau\) a relation from \(A^*\) to \(B^*\)

Definition: The graph of the relation \(\tau\)
Page: 525, 527
Chapter: 1
Section: , 1.2
Variables: \(M,N\) monoids
\(\tau:M\to\mathfrak P(N)\) a relation
Notation: \(\hat\tau\)

Name: A rational relation
Definition: \(\hat\tau\) is rational
Page: 525, 527, 527, 529, 530, 531, 532
Chapter: 1
Section: 1, 1.2, 2, 3.1
Variables: \(M_1 ,M_2\) monoids
Index: 1, 2, 1, 1, 1, 1, 2
Kind: Def, Def, Ex, Theo, Prop, Theo, Theo
Definition2: \(\hat\tau\) is accepted by an automaton with transitions from a minimal generator
Example: Identity and reverse of identity
Conjdef: A relation \(\tau:M_1\to M_2\) such that, equivalently
Definition3: there exists a finite alphabet \(Z\), two morphism \(\phi_i:Z^*\to M_i\), and \(K\subseteq\text{Rat }Z^*\) such that \(\tau=\phi_1^{-1}\circ\iota_K\circ\psi\), or equivalently \(\hat \tau=(K)\phi_1\times\phi_2\) (in case of \(M_i=A^*_i\), take \(\phi_i=\pi_{A_i}\))
Example2: Morphism, assuming a monoid is finitely generated,
Example3: Rectangles
product
Example4: Over words: factor relation

Name: Rational relations on free monoids
Page: 526, 534, 536
Section: 1, 3.3
Chapter: 1
Index: 1, 4, 1
Variables: \(A,B\) finite alphabets,
Kind: Prop,,,theo, Fact
Under: inverse
Not2: not
Under2: complement
Not3: no
Under3: intersection
Under4: composition
Condition4: the middle one is free and finitely generated
Under5: iteration
Condition5: finite

Question: \(\text{Dom}(\tau)\) is
Answer: rational
Page: 526
Chapter: 1
Variables: \(A,B\) finite alphabets,
\(\tau:A^*\to \mathfrak P(B^*)\)
Kind: Prop

Question: \(\text{Im}(\tau)\) is
Answer: rational
Page: 526
Chapter: 1
Variables: \(A,B\) finite alphabets,
\(\tau:A^*\to \mathfrak P(B^*)\)
Index: 2
Kind: Prop

Name: A rational substitution
Definition: A substitution \(\sigma\) such that \(\sigma a\) is rational for each \(a\in A\)
Page: 526
Chapter: 1
Variables: \(A,B\) finite alphabets,
Index: iii
Kind: Ex

Name: A rectangle in \(S_1\times S_2\)
Definition: A set \(R_1\times R_2\) as a subset of \(S_1\times S_2\), with \(R_i\subseteq S_i\)
Page: 527
Chapter: 1
Variables: \(S_1,S_2\) sets
Index: 4
Kind: Ex

Name: The Hamming distance on \(A^n\)
Definition: The function sending to each pair of word the number of distinct letters
Page: 528
Chapter: 1
Variables: \(A\) an alphabet,
\(n\in\mathbb N\)
Index: 4
Kind: Exercice

Name: An automaton over \(A^*\times B^*\) in normal form
Definition: An automaton whose transitions are of the form \((a,1_{B^*})\) or \((1_{A^*},b)\)
Page: 529
Chapter: 1
Section: 2
Variables: \(A,B\) alphabets

Name: A transducer
Definition: An automaton over a product of free monoids
Page: 529
Chapter: 1
Section: 2

Name: The underlying automaton of \(\mathcal T\)
Definition: The automaton obtained by taking the projection of each label on its first component
Page: 529
Chapter: 1
Section: 2
Variables: \(A,B\) alphabets
\(\mathcal T\) a transuducer

Name: Semigroup morphisms with domain \(A^*\)
Page: 531
Section: 3
Chapter: 1
Index: 2
Kind: Lem
Under: product \((\phi\times\psi)(u)\mapsto (u\phi,u\psi)\)

Name: The product of the \(\phi_i\)'s
Definition: \(u\mapsto (u\phi_i)_i\)
Page: 531
Chapter: 1
Section: 3
Variables: \(A\) an alphabet,
\(\phi_i:Z^*\to M_i\)
Notation: \(\prod\phi_i\)
Index: 2
Kind: Lem
Typ: A morphism \(Z^*\to\prod M_i\)

Name: Rational languages over a finitely generated free monoid
Page: 531
Section: 3.2
Chapter: 1
Index: 3
Kind: THeo
Under: relation
Condition: relational

Definition: [$]\defFun{\mathfrak B(A^*)}{\mathfrak B(B^*)}{L}{\{f\in B^*\mid f\sigma\subseteq L\}}[/$]
Page: 533
Chapter: 1
Section: 3.2
Variables: \(A,B\) alphabets
\(\sigma:B^*\to A^*\) a substitution
Notation: \(\breve{\sigma} \)
Index: 2
Kind: Rem

Name: Rational relations
Page: 534
Section: 3.3
Chapter: 1
Under: composition
Condition: the middle monoid is a free monoid

Definition: \(\bigcup_{i=0}^n\tau ^i\)
Page: 536
Chapter: 1
Section: 3.3
Variables: \(A\) an alphabet
\(\tau\) a relation from \(A^*\) to itself
Notation: \(\tau^{\le n}\)
Index: 3
Kind: def

Name: The iteration of \(\tau\)
Definition: \(\bigcup_{i=0}^\infty\tau ^i\)
Page: 536
Chapter: 1
Section: 3.3
Variables: \(A\) an alphabet
\(\tau\) a relation from \(A^*\) to itself
Notation: \(\stackrel{\star}{\tau}\)
Index: 3
Kind: def

Name: The proper iteration of \(\tau\)
Definition: \(\bigcup_{i=1}^\infty\tau ^i\)
Page: 536
Chapter: 1
Section: 3.3
Variables: \(A\) an alphabet
\(\tau\) a relation from \(A^*\) to itself
Notation: \(\stackrel{+}{\tau}\)
Index: 3
Kind: def