Title: Theory / Unimportant / CS / Fundamental / Automata / Finite / Sakarovitch / 3 - Weighted automata
Tags: récupéré fromMath mathToSee toBinaryFunction fromImplication questionExample
On every note of this deck, unless a note says otherwise:
Chapter: 1

Name: A semiring
Page: 379
Denoted by: \(\mathbb K\)

Name: A power series over \(M\) with coefficients in \(\mathbb K\)
Definition: A map from \(M\) to \(\mathbb K\)
Page: 379
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
Denoted by: \(s\)

Name: The coefficient of \(m\) in \(s\)
Definition: The image of \(m\) by \(s\)
Page: 379, 382
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
[$]s\in\mathbb K\llangle M\rrangle[/$]
Notation: \(\langle s,m\rangle\)
Index: 1, 2
Kind: Def, Rem
Definition2: \(\langle s,\underline m\rangle\)

Definition: whose elements are the power series over \(M\) with coefficients in \(\mathbb K\)
Page: 379, 386
Section: 1, 3
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
Notation: [$]\mathbb K\llangle M\rrangle[/$]
Definition2: whose topology is the product topology on \(\mathbb K^m\)
Conjdef: The topology

Question: [$]\mathbb B\llangle M\rrangle[/$]
Answer: is isomorphic to [$]\mathfrak B\llangle{M}\rrangle[/$] with \(\mathfrak B\) the set of subsets operator
Page: 380
Chapter: 1
Variables: \(M\) a monoid
Index: 2
Kind: Ex

Smaller0: [$](\mathbb B\llangle M\rrangle)\llangle N\rrangle [/$]
Greater0: [$]\mathbb B\llangle M\times N\rrangle [/$]
Page: 380
Chapter: 1
Variables: \(M\) a monoid
Index: 3
Kind: Ex
Smaller to greater: is isomorphic to

Name: The left exterior multiplication of \(s\) by \(k\)
Definition: \(m\mapsto k(sm)\)
Page: 380
Variables: \(M\) a monoid
\(\mathbb K\) a semiring,
\(k\in\mathbb K\),
[$]s\in\mathbb K\llangle M\rrangle[/$]
Notation: \(ks\)
Index: (i)

Name: The right exterior multiplication of \(s\) by \(k\)
Definition: \(m\mapsto (sm)k\)
Page: 380
Variables: \(M\) a monoid
\(\mathbb K\) a semiring,
\(k\in\mathbb K\),
[$]s\in\mathbb K\llangle M\rrangle[/$]
Notation: \(sk\)
Index: (i)

Name: The pointwise addition of \(s\) and \(t\)
Definition: \(m\mapsto \langle s,m\rangle+\langle t,m\rangle\)
Page: 380
Variables: \(M\) a monoid
\(\mathbb K\) a semiring,
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Notation: \(s+t\)
Index: (ii)

Name: The Cauchy product of \(s\) and \(t\)
Definition: \(m\mapsto\sum_{u,v\in M,uv=m}\langle s,u\rangle\langle t,v\rangle\)
Page: 380
Variables: \(M\) a monoid
\(\mathbb K\) a semiring,
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Notation: \(st\)
Index: (iii)

Definition: The set of polynomials over \(M\) with coefficients in \(\mathbb K\)
Page: 379
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
Notation: \(\mathbb K\langle M\rangle\)
Denoted by: \(s\)

Name: The support of \(s\)
Definition: the set of elements of \(M\) which have a non-zero coefficient in \(s\)
Page: 381
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
[$]s\in\mathbb K\llangle{M}\rrangle[/$]
Example: the support is \(A^*aA^*\)
Example2: \(A^*\) (0 is not the zero of the tropical semiring)
Abbreviation: supp \(s\)
Applied to: \(M=A^*\),
\(\mathbb K=\mathbb N\)
\(a\in A\), \(s\) associating to each element its number of \(a\),
Applied to2: \(M=A^*\),
\(\mathbb K=\mathcal M\)
\(a\in A\), \(s\) associating to each element its number of \(a\)

Name: The characteristic series of \(P\)
Definition: The element of [$]\mathbb K\llangle{M}\rrangle[/$] sending elements of \(P\) to \(1_{\mathbb K}\), everything else to \(0_{\mathbb K}\).
Page: 381
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
\(P\subseteq M\)
Notation: \(\underline P\)

Name: A characteristic series
Definition: \(\underline P\) for some \(P\subseteq M\)
Page: 381
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
\(P\subseteq M\)
Definition2: A series whose image contains only \(0_{\mathbb K}\) and \(1_{\mathbb K}\)
Name2: An unambiguous series
Extra: \(\underline P\) is the series sending element of \(P\) to 1, and everything else to \(0\)

Name: An unambiguous product
Definition: \(\underline{P Q}=\underline P \underline Q\)
Page: 382
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
Context: Characteristic series in [$]\mathbb K\llangle M\rrangle[/$]
Kind: Prop
Definition2: for each \(p,p'\in P\), \(q,q'\in Q\), \(pp'=qq'\) implies \(p=p'\) and \(q=q'\)
Conjdef: An product \(PQ\) with \(P,Q\subseteq M\) such that, equivalently

Name: \(m\) as an element of [$]\mathbb K\llangle{M}\rrangle[/$]
Definition: \(\underline m\)
Page: 382
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
\(m\in M\)
Kind: Prop

Name: \(M\) as a subset of [$]\mathbb K\llangle M\rrangle[/$]
Definition: The submonoid of [$]\mathbb K\llangle M\rrangle[/$] containing \(\underline m\) for each \(m\in M\)
Page: 382
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
Kind: Rem

Name: \(\mathbb K\) as a subset of [$]\mathbb K\llangle M\rrangle[/$]
Definition: The sub-semiring of [$]\mathbb K\llangle M\rrangle[/$] containing \(k\underline {1_M}\) for each \(k\in\mathbb K\)
Page: 382
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
Kind: Rem

Name: \(k\) as an element of [$]\mathbb K\llangle M\rrangle[/$]
Definition: \(k\underline {1_M}\)
Page: 382
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
\(k\in\mathbb K\)
Kind: Rem

Name: The Hadamard product of \(s\) and \(t\)
Definition: \(m\mapsto <s,m><t,m>\)
Page: 382
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
\(k\in\mathbb K\)
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Notation: \(s\odot t\)
Kind: Rem
Example: [$]m\mapsto\abs{m}_a\abs{m}_b[/$]
Example2: [$]m\mapsto\abs{m}_a+\abs{m}_b[/$] computes the number of \(a\) and \(b\)
Intuition: Generalisation of set intersection to power series.
Applied to: for \(M=A^*\),
\(\mathbb K=\mathbb N\)
\(s_a\) associating to each element its number of \(a\),
\(s_a\odot s_b\)
Applied to2: for \(M=A^*\),
\(\mathbb K=\mathcal M\)
\(s_a\) associating to each element its number of \(a\),
\(s_a\odot s_b\)

Name: The set of commutative semirings
Page: 382
Section: 1
Index: 2
Kind: Def
Under: transforming a series \(\mathbb K\) into [$]\mathbb K\llangle M\rrangle[/$], where the product is the Hadamard product
Under2: product ?
Condition3: quotient ?

Name: The scalar product of \(s\) and \(t\)
Definition: \(\sum_{m\in M}<s,m><t,m>\)
Page: 382
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
\(k\in\mathbb K\)
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Notation: \(\langle s,t\rangle\)

Smaller0: \(s\) or \(t\) is a polynomial
Greater0: \(\langle s,t\rangle\) is correctly defined
Page: 382
Chapter: 1
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
\(k\in\mathbb K\)
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Smaller1: \(M\) is graded
Connect Smaller0: or

Name: A finitely decomposable element of \(m\)
Definition: An element \(m\in M\) such that the number of \((p,q)\) with \(pq=m\) is finite
Page: 382
Section: 2
Variables: \(M\) a monoid

Name: A length on \(M\)
Definition: strictly positive on \(M\setminus\{1_M\}\)
Page: 382
Section: 2
Variables: \(M\) a monoid
Notation: \(\phi\) or [$]\abs{}[/$]
Definition2: \(f(mn)\le f(m)+f(n)\)
Conjdef: A function \(f:M\to\mathbb N\)

Name: A graduation on \(M\)
Definition: such that \(\phi(mn)=\phi(m)+\phi(n)\)
Page: 382
Section: 2
Variables: \(M\) a monoid
Example: On \(A^*\), the length
Conjdef: A length \(\phi:M\to\mathbb N\)

Name: A graded monoid
Definition: A monoid and a graduation on it
Page: 383
Section: 2

Name: Graded monoid
Page: 384
Section: 2
Chapter: 1
Under: product

Name: A graded monoid of finite type
Definition: which is finitely generated
Page: 384
Section: 2
Conjdef: A graded monoid

Name: The set of rings
Page: 384, 385,(Sakarovitch)
244 (Dummit, Foot)
Section: 2,
3
Chapter: 1,
7
Index: ,
4
Kind: ,
Ex
Under: sending \(\mathbb K\) to [$]\mathbb K\llangle M\rrangle[/$] with \(M\) graded, pointwise sum and Cauchy product
Under2: sending \(\mathbb K\) to [$]\mathbb K\llangle M\rrangle[/$] with \(M\) finite, pointwise sum and Cauchy product
Under3: sending \(\mathbb K\) to \(\mathbb K[M]\)
Under4: taking square matrix, with pointwise sum and matrix product
Under5: direct product
Under6: sending \(R\) a ring that to functions \(X\to R\)

Question: Basis of topology
Answer: is omitted
Page: 379, 386
Chapter: 1
Section: 1, 3
Index: \(\mathbb K\) a topological semiring
\(M\) a monoid

Name: The valuation of \(s\)
Definition: The least [$]\abs{m}[/$] for \(m\) in the support of \(s\)
Page: 387
Variables: \(\mathbb K\) a semiring
\(M\) a graded monoid
[$]s\in\mathbb K\llangle M\rrangle[/$]
Notation: \(\mathrm{v}(s)\)

Name: The gap between \(s\) and \(t\)
Definition: The least [$]\abs{m}[/$] such that \(<s,m>\ne <t,m>\)
Page: 388
Variables: \(\mathbb K\) a semiring
\(M\) a graded monoid
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Notation: \(\mathrm{e}(s,t)\)
Definition2: The gap of \(s-t\) (assuming \(\mathbb K\) is a ring)

Name: The distance between \(s\) and \(t\)
Definition: [$]\frac12\sum_{n\in\mathbb N}\left(\frac1{1^n}\max\left\{\mathrm{c}(<s,m>,<t,m>)\mid\abs{m}=n\right\}\right)[/$]
Page: 388
Variables: \(\mathbb K\) a metric semiring with distance \(\mathrm{c}\)
\(M\) a graded monoid
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Notation: \(\mathrm{d'}(s,t)\)
Assuming: Assuming \(\mathrm{c}\) is bounded above by 1
Property: A metric bounded above by 1

Smaller0: \(\frac12\mathrm{d}(s,t)\)
Greater0: \(\mathrm{d'}(s,t)\)
Page: 388
Chapter: 1
Variables: \(\mathbb K\) a metric semiring with distance \(\mathrm{c}\)
\(M\) a graded monoid
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Smaller to greater: \(\le\)
Assuming: \(\mathrm c\) is the discrete metric
Greater to smaller: \(\ge\)

Smaller0: \(s\) and \(t\) coincides for all \(m\) of length at most \(n\)
Greater0: \(\mathrm{d'}(s,t)\le{2^{-n}}\)
Page: 388
Chapter: 1
Variables: \(\mathbb K\) a metric semiring with distance \(\mathrm{c}\)
\(M\) a graded monoid
[$]s,t\in\mathbb K\llangle M\rrangle[/$]

Smaller0: \(\mathrm{d'}(s,t)\) (distance using the metric \(\mathrm{c}\))
Greater0: \(\mathrm{d}(s,t)\) (distance using the discrete topology and metric)
Page: 388
Chapter: 1
Variables: \(\mathbb K\) a metric semiring with distance \(\mathrm{c}\)
\(M\) a graded monoid
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Smaller to greater: \(\le\)
Prefix Greater: \(\ge\)

Page: 387
Section: 1
Notation: \(\mathrm{d}(s,t)\)
Variables: \(\mathbb K\) a metric semiring with distance \(\mathrm{c}\)
\(M\) a graded monoid
[$]s,t\in\mathbb K\llangle M\rrangle[/$]
Definition: \(2^{-\mathrm{e}(s,t)}\) with \(\mathrm e(s,t)\) the size of the least \(m\) where \(<s,m>\ne<t,m>\)

Name: The class of topological semiring
Page: 389
Section: 1
Under: sending \(\mathbb K\) to [$]\mathbb K\llangle M\rrangle[/$]

Name: The sum of \(\{t_i\}_{i\in I}\)
Definition: such that for all \(\epsilon>0\)
Page: 389
Variables: \(\mathbb T\) a metric semiring, with distance \(\mathrm{d}\)
\(\{t_i\}_{i\in I}\)
Notation: \(\sum_{i\in I}t_i\)
Definition2: there exists \(J_{\epsilon}\subseteq I\) finite
Conjdef: Some \(t\in\mathbb T\)
Definition3: such that for each finite \(J_{\epsilon}\subseteq L\subseteq I\)
Definition4: \(\mathrm{d}\left(\sum_{i\in L}t_i,t\right)\le \epsilon\)
Property: At most one

Name: A summable family
Definition: A family which admits a sum
Page: 389
Variables: \(\mathbb T\) a metric semiring, with distance \(\mathrm{d}\)

Page: 389
Chapter: 1
Variables: \(\mathbb T\) a metric semiring, with distance \(\mathrm{d}\)
Name: The class of summable families
Q: [...]
A: sending a family \(\{t_i\}_{i\in I}\) to a family \(\{\sum_{i\in J_k}\}_k\) where \(\{J_k\}\) is a partition of \(I\) whose sets are finite
Q: [...]
A: continuous morphism

Name: A locally finite family in [$]\mathbb K\llangle M\rrangle[/$]
Definition: A subset [$]\mathcal F\subseteq\mathbb K\llangle M\rrangle [/$] such that, for each \(m\in M\), there is a finite number of \(s\in\mathcal F\) such that \(<s,m>\ne0\)
Page: 389
Variables: \(\mathbb K\) a semiring
\(M\) a monoid

Smaller0: locally finite
Greater0: summable
Page: 390
Chapter: 1
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
[$]\mathcal{F}\subseteq\mathbb K\llangle M\rrangle[/$]
Index: 4
Kind: Prop
Prefix Greater: \(\mathcal F\) is

Question: Example of dense subset of [$]\mathbb K\llangle M\rrangle[/$]
Answer: \(\mathbb K\langle M\rangle\)
Page: 390
Chapter: 1
Section: 3.3
Variables: \(\mathbb K\) a semiring
\(M\) a monoid

Smaller0: \(\sum_{i\in I}s_i=s\)
Greater0: \(\sum_{i\in I}\langle s_i,m\rangle=\langle s,m\rangle\)
Page: 390
Chapter: 1
Section: 3.3
Variables: \(\mathbb K\) a semiring
\(M\) a monoid
[$]s,\{s_i\}_{i\in I}\in\mathbb K\llangle{M}\rrangle[/$]
Index: 7
Kind: Prop
Smaller to greater: iff