Title: Theory / Unimportant / CS / Fundamental / Automata / Finite / Sakarovitch / 2 - Algebra
Tags: hasSeenConjDef fromMath fromImplication closed examplesSwitchExample1 mathToDef mathToSee récupéré toAlgebra topology

Page: 114
Name: Product topology
Set: \(\Pi_\alpha X_\alpha\)
Chapter: 2
Section: 19
Variables: \(\mathbf J\) be an index set
\(\{X_\alpha\}_{\alpha\in\mathbf J}\) an indexed family of sets.
Kind: Definition
Base: \(\pi^{-1}_\beta(U_\beta)\) for \(U_\beta\) open in \(X_\beta\) and \(\beta\in\mathbf J\).
Base2: \(\Pi_{\alpha\in\mathbf J}B_\alpha\), where \(B_\alpha\in\mathbf B_\alpha\) and only a finite number of \(B_\alpha\) is distinct from \(X_\alpha\).
Intuition: \(\Pi_{\alpha\in\mathbf J}X_\alpha\)

Name: A monoid
Page: 219
Chapter: 1
Notation: \(M,N\)

Name: Morphism of monoid
Definition: A function \(M\to N\) such that the function commutes with the binary operation
Page: 219
Chapter: 1
Variables: \((M,\cdot_M),(N,\cdot_N)\) monoids
Denoted by: \(\alpha\)

Definition: The function associating to each transition its source
Page: 219
Chapter: 1
Variables: (M\) a monoid
\(\mathcal A=\langle Q,M,E,I,T\rangle\)
Notation: \(\iota\)

Definition: The function associating to each transition its destination
Page: 219
Chapter: 1
Variables: \(M\) a monoid
\(\mathcal A=\langle Q,M,E,I,T\rangle\)
Notation: \(\tau\)

Definition: The function associating to each transition its label
Page: 219
Chapter: 1
Variables: \(M\) a monoid
\(\mathcal A=\langle Q,M,E,I,T\rangle\)
Notation: \(\epsilon\)

Name: A computation
Definition: A path in the graph \(\mathcal A\)
Page: 219
Chapter: 1
Variables: \(M\) a monoid
\(\mathcal A=\langle Q,M,E,I,T\rangle\)
Denoted by: \(c\)

Name: A successful computation
Definition: A computation starting in \(I\) and ending in \(T\)
Page: 219
Chapter: 1
Variables: \(M\) a monoid
\(\mathcal A=\langle Q,M,E,I,T\rangle\)

Name: The label of \(c\)
Definition: \(\Pi_{i=1}^n m_i\)
Page: 219
Chapter: 1
Variables: \(M\) a monoid
\(\mathcal A=\langle Q,M,E,I,T\rangle\)
\(c:=p_0\xrightarrow{m_1}p_1\xrightarrow{m_1}\dots \xrightarrow{m_n}p_n\)
Notation: \(|c|\)

Definition: There exists \(p_0\xrightarrow{m_1}p_1\xrightarrow{m_1}\dots \xrightarrow{m_n}p_n\)
Page: 219
Chapter: 1
Variables: \(M\) a monoid
Let \(\mathcal A=\langle Q,M,E,I,T\rangle\)
Notation: \(p_0\xrightarrow[\mathcal A]{\Pi_{i=1}^n m_i}p_n\)

Name: An element accepted by \(M\)
Definition: A label of a successful path of \(\mathcal A\)
Page: 219
Chapter: 1
Variables: \(M\) a monoid
Let \(\mathcal A=\langle Q,M,E,I,T\rangle\)

Name: The behavior of \(\mathcal A\)
Definition: \(\{m\in M\mid \exists I\ni p\xrightarrow[\mathcal A]{m}q\in T\}\)
Page: 219
Chapter: 1
Variables: \(M\) a monoid
Let \(\mathcal A=\langle Q,M,E,I,T\rangle\)
Notation: \(|\mathcal A|\)
Kind: Def

Name: Equivalent automata
Definition: Automata with the same behavior
Page: 219
Chapter: 1
Variables: \(M\) a monoid
Index: 1 (ii)
Kind: Def

Name: A finite automaton
Definition: An automaton with a finite set of transitions
Page: 220
Chapter: 1
Index: 2
Kind: Def

Definition: \(\{pq\mid p\in P,q\in Q\}\)
Page: 221
Chapter: 1
Section: 2.1
Variables: \(M\) a monoid,
\(P,Q\subseteq M\)
Notation: \(PQ\)

Name: A complete semiring
Definition: whose semigroup is complete
Page: 221, https://en.wikipedia.org/wiki/Semiring#Complete_and_continuous_semirings
Chapter: 1
Section: 2.1
Variables: \(M\) a monoid,
Index: 2
Kind: Def
Definition2: with distributivity over infinite sum
Conjdef: A semiring

Definition: elements: subsets of \(M\)
Page: 221
Chapter: 1
Section: 2.1
Variables: \(M\) a monoid,
Notation: \(\mathfrak B(M)\)
Index: 2
Kind: Def
Definition2: sum: union
Conjdef: The semiring
Definition3: product: set product
Typ: Complete semiring

Name: A complete semigroup
Definition: A semigroup with infinite sum
Page: 221, https://en.wikipedia.org/wiki/Semiring#Complete_and_continuous_semirings
Chapter: 1
Section: 2.1
Variables: \(M\) a monoid,
Index: 2
Kind: Def

Definition: \(\{\emptyset,\{1_M\}\}\)
Page: 221
Chapter: 1
Section: 2.1
Variables: \(M\) a monoid,
Context: Subsemiring of \(\mathfrak B(M)\)
Notation: \(\mathbb B\)

Name: The extension of \(\alpha\) to \(\mathfrak B(M)\)
Definition: [$]\defFun{\mathfrak B(M)}{\mathfrak B(N)}{S}{\{\alpha (s)\mid s\in S\}}[/$]
Page: 221
Chapter: 1
Section: 2.1
Variables: \(M,N\) monoids
\(\alpha:M\to N\)
Index: 2, 1
Kind: Def, Lem,
Assuming: Morphism of complete semiring

Name: The submonoid generated by \(P\)
Definition: \(\bigcup _{n\in\mathbb N}P^n\)
Page: 221
Chapter: 1
Section: 2.1
Variables: \(M,N\) monoids
\(P\in\mathfrak B(M)\)
Notation: \(\langle P\rangle\)
Kind: Prop
Notation2: \(P^*\)

Smaller0: \((P^*)\alpha\)
Greater0: \((P\alpha)^*\)
Page: 221
Chapter: 1
Section: 2.1
Variables: \(M,N\) monoids
\(\alpha:M\to N\) morphism
\(P\in\mathfrak B(M)\)
Index: 2
Kind: Lem
Smaller to greater: =

Name: A rationally family of subsets of \(m\)
Definition: closed under addition
Page: 221
Chapter: 1
Section: 2.2
Variables: \(M\) a monoid,
Index: 3 (a)
Kind: Def
Definition2: closed under product and star
Conjdef: Some \(\mathcal F\subseteq\mathcal P(M)\)
Definition3: closed under star

Name: The rational closure of \(\mathcal F\)
Definition: it is the smallest family of subsets of \(M\) that contains \(\mathcal F\), and which is rationally closed
Page: 222, 223
Chapter: 1
Section: 2.2
Variables: \(M\) a monoid,
\(\mathcal F\subseteq\mathcal P(M)\)
Index: 3(b), 6
Kind: Def, Prop
Definition2: there exists a rational expression \(\text E\) over a set of variables and an interpretation of \(\text E\) which takes values in \(\mathcal F\), whose result is \(R\)
Conjdef: A subset of \(M\) such that, equivalently
Abbreviation: \(\text{Rat} \mathcal F\)

Name: A rational subset of \(M\)
Definition: belonging to the rational closure of finite subsets of \(M\)
Page: 221, 225
Chapter: 1
Section: 2.2, 3
Variables: \(M\) a monoid,
Index: 3(c), 1
Kind: Def, Theo
Definition2: accepted by a finite automaton over \(M\)
Conjdef: A subset of \(M\)

Name: A rational subset of \(M\)
Definition: it is denoted by a rational expression
Page: 221, 223
Chapter: 1
Section: 2.2, 5.3
Variables: \(M\) a monoid,
Index: 3(c), 3
Kind: Def, Prop
Definition2: belonging to the rational closure of finite subsets of \(M\).
Example: \((a,b)*=\{(a^n,b^n)\mid n\in\mathbb N\}\)
Conjdef: A subset of \(M\), equivalently
Extra: more examples
Applied to: In \(\mathbb N^2=\{a\}^*\times\{b\}^*\)

Name: The family of rational subsets of \(M\)
Page: 221
Chapter: 1
Section: 2.2
Variables: \(M\) a monoid,
Index: 3(c)
Kind: Def
Abbreviation: \(\text{Rat }M\)

Name: A rational expression over \(M\)
Definition: A formula obtained recursively from the elements of \(M\), addition, product and star
Page: 221
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
Index: 4
Kind: Def

Name: The set of rational expressions over \(M\)
Page: 222
Chapter: 1
Section: 2.3
Index: 5
Kind: Def
Abbreviation: \(\text{RatE} M\)

Name: The set denoted by \(\text E\)
Page: 222
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
\(\text{E}\in\text{RatE} M\)
Notation: \(|\text E|\)
Index: 5
Kind: Def
Typ: Subset of \(M\)

Name: The set denoted by \(0\)
Definition: \(\emptyset\),
Page: 222
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
\(\text{E}\in\text{RatE} M\)
Context: rational expression
Index: 5
Kind: Def

Name: The set denoted by \(1\)
Definition: \(1_M\),
Page: 222
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
\(\text{E}\in\text{RatE} M\)
Context: rational expression
Index: 5
Kind: Def

Name: The set denoted by \(m\)
Definition: \(\{m\}\),
Page: 222
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
\(\text{E}\in\text{RatE} M\)
\(m\in M\)
Context: rational expression
Index: 5
Kind: Def

Name: The set denoted by \(\text {E+F}\)
Definition: The union of the set denoted by \(E\) and \(F\)
Page: 222
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
\(\text{E,F}\in\text{RatE} M\)
Context: rational expression
Index: 5
Kind: Def

Name: The set denoted by \(\text E^*\)
Definition: Kleen star ofhe set denoted by \(\text E\)
Page: 222
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
\(\text{E}\in\text{RatE} M\)
Context: rational expression
Index: 5
Kind: Def

Name: The set denoted by \(\text {EF}\)
Definition: The product of the set denoted by \(\text {E}\) and by \(\text {F}\)
Page: 222
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
\(\text{E,F}\in\text{RatE} M\)
Context: rational expression
Index: 5
Kind: Def

Smaller0: \(S\) is rational
Greater0: \(S\) is contained in a finitely generated submonoid of \(M\)
Page: 222
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
\(S\subseteq M\)
Index: 4
Kind: Cor
Counterexample: \(\{a^nb^n\mid n\in\mathbb N\}\) is finitely generated but not rational in \(\{a,b\}^*\)

Smaller0: \(M\) is a rational subset of itself
Greater0: \(M\) is finitely generated
Page: 222
Chapter: 1
Section: 2.3
Variables: \(M\) a monoid,
Index: 5
Kind: Cor
Smaller to greater: iff
Construction: If \(M\) is finitely generated by \(m_1,\dots,m_n\) then \(M=(\sum m_i)^*\)
If \(M\) is rational, it is generated by the singletons of the expression defining \(M\)

Name: Rational subets of monoids
Page: 223, 224
Section: 2.4, 2.5
Chapter: 1
Index: 7, 2
Kind: Prop, ex
Under: morphism
Not2: not
Under2: inverse of morphism
Under3: intersection
Under4: under complement

Smaller0: surjective
Greater0: the image of a rational by \(\alpha\)
Page: 223
Chapter: 1
Section: 2.4
Variables: \(\alpha:M\to N\) morphism of monoid,
\(S\subseteq N\) rational
Index: 7 (ii)
Kind: Prop
Prefix Greater: \(S\) is
Prefix Smaller: \(\alpha\) is

Page: 224
Chapter: 1
Section: 2.5
Variables: \(M\) a monoid
Name: The family of rational subsets of \(M\)
Q: [...]
A: inverse morphism
Closure2: intersection
Q: [...]
A: complement
Q: [...]
A: not
Q: [...]
A: no
Q: [...]
A: not

Question: Proof that rational subsets are not closed under inverse of morphism
Answer: Take [$]\alpha:\defFun{\{a,b\}^*}{\{a\}^*\times \{b\}^*}{w}{\abs{w}_a,\abs{w}_b}[/$]. Then \(((a,b)^*)\alpha^{-1}\) is the set of words with the same number of \(a\) and of \(b\), which is not rational
Page: 224
Chapter: 1
Section: 2.5
Variables: \(M\) a monoid
Index: 2
Kind: Ex

Question: Proof that rational subsets are not closed under intersection
Answer: Let \(V=(a,c)^*(b,1)^*\)
\(W=(a,1)^*(b,c)^*\)
\(V\cap W=\{(a^nb^n,c^n)\mid n\in\mathbb N\}\), which is not rational
Page: 224
Chapter: 1
Section: 2.5
Variables: \(M\) a monoid
Index: 2
Kind: Ex

Name: The relabelling of \(\mathcal A\) under \(\alpha\)
Definition: \(\langle Q,M,\{(p,m\alpha,q)\mid (p,m,q)\in E\},I,T\rangle\)
Page: 225
Chapter: 1
Section: 3
Variables: \(M,N\) monoids
\(\alpha:M\to N\) a morphism
\(\mathcal A=\langle Q,M,E,I,T\rangle\) an automaton over \(M\)

Question: [$]\abs{\mathcal B}[/$]
Answer: equals [$]\abs{\mathcal A}\alpha[/$]
Page: 225
Chapter: 1
Section: 3
Variables: \(M,N\) monoids
\(\alpha:M\to N\) a morphism
\(\mathcal A=\langle Q,M,E,I,T\rangle\) an automaton over \(M\)
\(\mathcal B\) the relabelling of \(\mathcal A\) under \(\alpha\)

Smaller0: \(S\) belongs to the rational closure of \(\mathcal F\)
Greater0: \(S\) is the behaviour of a generalised finite automaton whose labels are elements of \(\mathcal F\)
Page: 27
Chapter: 1
Section: 3
Variables: \(M\) a monoid
\(S\subseteq M\)
\(\mathcal F\) a family of subsets
Index: 2
Kind: Theo
Smaller to greater: iff

Name: A local language
Definition: A language of the form \((DA^*\cap A^*F)\setminus(A^*VA^*)\) with \(D,F\subseteq A\) and \(V^\subseteq A^2\)
Page: 228
Chapter: 1
Section: 3
Index: 6
Kind: Def
Intuition: The set of first letter, last letter, and pair of successive letters is fixed

Name: An unambiguous star
Definition: A star of the form \(X^*\), with \(X\subseteq M\), and for each \(x_1,\dots,x_n,x_1',\dots,x'_{n'}\), \(x_1\dots x_n=x'_1\dots x'_{n'}\) implies \(n=n'\) and \(x_i=x'_i\)
Page: 228
Chapter: 1
Section: 4
Variables: \(M\) a monoid

Name: An ambiguous union/product/star
Definition: A union/product/star which is not unambiguous
Page: 229
Chapter: 1
Section: 4
Variables: \(M\) a monoid

Name: A family closed under the unambiguous relational operations
Definition: A subset of \(M\) closed under unambiguous operator
Page: 229
Chapter: 2
Variables: \(M\) a monoid

Name: The unambiguous rational closure of \(\mathcal F\)
Definition: The smallest family of subsets of \(M\) containing \(\mathcal F\) and closed under the unambiguous relational operations
Page: 229
Chapter: 2
Variables: \(M\) a monoid
\(\mathcal F\subseteq M\)
Notation: \(\mathrm{URat}\mathcal F\)

Name: An unambiguously rational subset of \(M\)
Definition: belonging to the unambiguous rational closure of the class of finite subsets of \(M\)
Page: 229
Chapter: 1
Section: 4
Variables: \(M\) a monoid
Definition2: denoted by an unambiguous rational expression over \(M\)
Conjdef: A subset of \(M\), equivalently

Name: An unambiguous rational expression over \(M\)
Definition: An expression such that every rational operation that is used in the computation of the subset it denotes is unambiguous.
Page: 229
Chapter: 1
Section: 4
Variables: \(M\) a monoid
Index: 8
Kind: Def

Definition: The set of unambiguous rational expressions over \(M\)
Page: 229
Chapter: 1
Section: 4
Variables: \(M\) a monoid
Notation: \(\mathrm{URatE}M\)
Index: 8
Kind: Def

Smaller0: \(\mathrm{URatE}M\)
Greater0: \(\supseteq\)
Page: 229
Chapter: 1
Section: 4.2
Variables: \(M\) a monoid
Index: 8
Kind: Def
Smaller to greater: \(\subseteq\)
Connect Greater0: \(\mathrm{RatE}M\)
Construction: Take \(M=\{a,b\}^*\times \{c\}^*\)
\((a,c)^*(b,1)^*\cup (a,b)^*(b,c)^*\) is inherently ambiguous

Smaller0: \(\mathrm{URatE}A^*\)
Page: 229
Chapter: 1
Section: 4.2
Variables: \(A\) a finite alphabet
Index: 8
Kind: Def
Smaller to greater: =
Connect Greater0: \(\mathrm{RatE}A^*\)
Construction: McNaughton–Yamada algorithm yields a unambiguous rational expression from deterministic automaton

Name: The set of pairs \((U,M)\) with unambiguous rational subsets of \(M\)
Page: 231
Section: 4.2
Chapter: 1
Index: 12
Variables: \(M,N\) monoids
Kind: Prop
Under: morphism
Condition: injective
Under2: inverse of morphism
Condition2: surjective. In the sens that there exists an unambiguous rational antecedent, not necessarily exactly equal to the inverse

Name: The set of unambiguous rational of \(M\)
Page: 231
Section: 4.2
Chapter: 1
Index: 9
Variables: \(M\) monoids
Kind: Ex
Under: removing a set
Condition: finite

Name: A cross-section of \(A^*\) for \(\alpha\)
Definition: \(R\alpha=M\)
Page: 231
Chapter: 1
Section: 4.2
Variables: \(M\) monoid
\(\alpha:A^*\to M\)
Index: 13
Definition2: \(\alpha\) is injective on \(R\)
Conjdef: A subset \(R\subseteq A^*\) such that, both
Assuming: \(\alpha\) surjective,