Title: Theory / Unimportant / CS / Fundamental / Automata / Finite / Pin{ / A Automata and semigroups / 04 Recognisable and rational sets+2
Tags: fromMath mathToDef automaticImplies closed multipartite complex hasSeenConjDef toBinaryRelation counterExample exampleToQuestion examplesSwitchExample1 mid1516974248815 toUnary
On every note of this deck, unless a note says otherwise:
Chapter: IV

Name: The class of Rational sets of \(M\)
Page: 74, 75
Section: 1
Chapter: IV
Index: 1, 3, 2
Variables: \(M\) a monoid
Kind: Prop, Ex, Theo
Not: no
Under: intersection
Not2: not
Under2: complementation
Under3: morphism?
Under4: inverse of morphism ?

Name: The class of Rational sets of a set \(S\)
Definition: contains \(\emptyset\)
Page: 73
Chapter: IV
Section: 1
Variables: \(S\) a monoid.
Definition2: contains singletons
Conjdef: the smallest set of language which
Definition3: closed under union
Definition4: closed under product
Definition5: closed under star

Name: The class of pair \((R,M)\) with \(R\) a rational subset of the monoid \(M\)
Page: 74, 75
Section: 1
Chapter: IV
Index: 1, 3, 2
Kind: Prop, Ex, Theo
Under: product (\((R,M)\), \((R',M')\) lead to a pair \((R\times R',M\times M')\))
Condition: arbitrary
Under2: inverse of morphism
Condition2: the inverse of singletons are rational
Condition3: in the sens that, for \(\phi:M\to N\) surjective and \(S\) rational in \(N\), there is \(R\) rational in \(M\) with \(\phi(R)=S\)
Under4: intersection by a sub monoid
Condition4: ?

Name: Rational sets whose intersection is not rational
Page: 74
Chapter: IV
Section: 1
Index: 3
Kind: Ex
Example: \(\{(a^n,b^nc^m)\mid n,m\in\mathbb N\}\) and \(\{(a^n,b^mc^n)\mid n,m\in\mathbb N\}\)

Name: A set recognized by \(\phi\)
Definition: \(\phi^{-1}(P)\) for \(P\subseteq N\)
Page: 75
Chapter: IV
Section: 2.1
Variables: \(M,N\) a monoid,
\(L\subseteq M\)
\(\phi:M\to N\).

Name: A set fully recognized by \(\phi\)
Definition: \(L\) is recognized by \(\phi\) such that \(\phi\) is surjective
Page: 75, 87
Chapter: IV
Section: 2.1
Variables: \(M,N\) a monoid,
\(L\subseteq M\)
\(\phi:M\to N\).
Index: ,23
Kind: , Cor
Definition2: the syntactic monoid of \(L\) is a quotient of \(N\)
Conjdef: A set \(L\subseteq M\) such that, equivalently

Name: \(\sim\) saturate \(L\)
Definition: \(x\sim y\) implies \(x\in L\iff y\in L\).
Page: 76
Chapter: IV
Section: 2.1
Variables: \(M\) monoid
\(L\subseteq M\)
\(\sim\) be an equivalence relation on \(M\).

Smaller0: \(\phi\) recognises \(P\)
Greater0: \(\phi(R\cap P)\)
Page: 76
Section: 2.1
Variables: \(M\) be a monoid,
\(P,R\) subsets of \(M\)
\(\phi:M\to N\).
Index: 6
Kind: Prop
Greater1: \(\phi(R)\cap \phi(P)\)
Connect Greater0: \(=\)

Smaller0: \(\phi\) recognises \(P\)
Greater0: \(\phi(R-P)\)
Page: 76
Section: 2.1
Variables: \(M\) be a monoid,
\(P,R\) subsets of \(M\)
\(\phi:M\to N\).
Index: 6
Kind: Prop
Greater1: \(\phi(R)-\phi(P)\)
Connect Greater0: \(=\)

Smaller0: \(\phi\)
Greater0: \(M\setminus L\)
Page: 77
Section: 2.2
Variables: \(M,N\) be a monoid,
\(\phi:M\to N\).
\(L\subseteq M\) recognized by \(\phi\)
Index: 8
Kind: Prop
Smaller to greater: recognize
Hide middle: yes
Greater1: \(K^{-1}L\) and \(LK^{-1}\) for all \(K\subseteq M\)
Greater to smaller: are recognized by
Connect Greater0: and

Smaller0: \(\phi\circ\eta\)
Greater0: \(\eta^{-1}(L)\)
Page: 78
Section: 2.2
Variables: \(R,M,N\) monoids,
\(L\subseteq M\)
\(\eta:R\to M\)
\(\phi:M\to N\).
Index: 10
Kind: Prop
Smaller to greater: recognizes
Hide middle: yes
Assuming: \(\phi\) recognizes \(L\)
Greater to smaller: is recognized by

Name: The class of recognisable subsets of \(M\)
Page: 78, 79
Section: 2.3
Chapter: IV
Index: 12, 14
Variables: \(M\) a monoid.
Kind: Cor, Prop
Under: union
Condition: finite
Under2: intersection
Under3: complement
Under4: left and right quotients

Smaller0: \(M\) is finitely generated
Greater0: every recognisable subset of \(M\) is rational
Page: 79
Section: 2.3
Variables: \(M\) be a monoid.
Index: 2.13
Kind: Theo
Smaller to greater: iff
Name: McKnight theorem
Smallest: the set \(M\) is a rational subset of \(M\)

Question: \(A\) is rational and \(B\) is recognisable
\(A\cap B\) is
Answer: recognisable
Page: 79
Chapter: IV
Section: 2.3
Variables: \(S\) a semigroup
\(A,B\subseteq S\).
Index: 14
Kind: Prop

Name: The transition monoid of \(\mathcal A\)
Definition: \(\mu(A^*)\)
Page: 83
Chapter: IV
Section: 3.2
Variables: \(Q\) a set, \(A\) an alphabet,
\(E\subseteq Q\times Q\),
\(I,F\subseteq Q\) and
\(\mathcal A=(Q,A,E,I,F)\) nondeterministic,
\(\mu\) the relation sending \(u\) to the set of pair \((p,q)\) of states with a transition \(p\xrightarrow{u}q\)
Notation: \(M(\mathcal A)\).

Smaller0: \(M(L+ K)\)
Greater0: \(M(L)\times M(K)\)
Page: 88
Section: 4.2
Variables: \(A\) an alphabet and \(K,L\subseteq A^*\).
Index: 26
Kind: Prop
Smaller to greater: divides
Greater to smaller: is a multiple of
Extra: plusieurs conditions

Name: The natural preorder from a deterministic automaton
Definition: The relation containing the pairs \((p,q)\) such that for all \(u\in A^*\), \(p\cdot u\in F\) implies \(q\cdot u\in F\).
Page: 89
Chapter: IV
Section: 5.1
Variables: \(\mathcal A=(Q,A,E,I,F)\) an automaton.
Notation: \(p\le q\)

Smaller0: \(\phi\) recognizes \(P\)
Greater0: \(\phi(R\setminus P)\)
Page: 76
Section: 2.2
Variables: \(M\) be a monoid, \(P,R\) subsets of \(M\) and \(\phi:M\to N\).
Index: 6
Kind: Prop
Greater1: \(\phi(R)\setminus\phi(P)\)
Connect Greater0: \(=\)

Name: A recognisable subset of \(M\)
Definition: A subset of \(M\) recognized by some monoid.
Page: 76
Chapter: IV
Section: 2.1
Variables: \(M\) a monoid.

Name: A subset of \(M\) (fully) recognized by \(N\)
Definition: A set \(L\subseteq M\) which is (fully) recognised by some morphism \(\phi:M\to N\).
Page: 76
Chapter: IV
Section: 2.1
Variables: \(M,N\) monoids

Page: 86
Definition: the relation \(R\) such that \(R(u,v)\) iff for all \(x,y\in M\), \(xuy\in L\iff xvy\in L\).
Chapter: IV
Section: 4
Variables: \(M\) a monoid
\(L\subseteq M\).
Notation: \(\sim_L\)
Name: The syntactic congruence of \(L\) in \(M\)
Kind: 1

Name: The syntactic monoid of \(L\) in \(M\)
Definition: \(M(L)\).
Page: 86
Chapter: IV
Section: 4.1
Variables: \(M\) a monoid
\(L\subseteq M\).
Notation: \(M/\sim_L\)

Name: The syntactic morphism of \(L\)
Definition: The projection \(M\to M/\sim L\).
Page: 86
Chapter: IV
Section: 4
Variables: \(M\) a monoid and \(L\subseteq M\).
Notation: \(\eta_L\)
Kind: 1

Name: The syntactic image of \(L\)
Definition: The set \(\eta_L(L)\).
Page: 86
Chapter: IV
Section: 4 1
Variables: \(M\) a monoid and \(L\subseteq M\).

Smaller0: minimal and complete
Greater0: an order
Page: 89
Section: 5.1
Variables: \(\mathcal A=(Q,A,E,I,F)\) an automaton.
Index: 28
Kind: Prop
Prefix Greater: the natural preorder is
Prefix Smaller: the automaton is

Question: \(R\) is also a rational subset of
Answer: a finitely generated submonoid of \(M\).
Page: 75
Chapter: IV
Section: 1
Variables: \(M\) a monoid
\(R\subseteq M\) rational.
Index: 3
Kind: Prop

Smaller0: \(S\) is finite
Greater0: \(H\) is rational
Page: 74
Section: 1
Variables: \(S\) a monoid
\(H\subseteq S\).
Kind: Ex
Extra: autre condition

Name: A semilinear set
Definition: A finite union of linear sets
Page: 74
Chapter: IV
Section: 1
Index: 2
Kind: Ex
Definition2: \(R\) is a set of the form \(\{v_0+n_1v_1+\dots+n_rv_r\mid n_1,\dots,n_r\in\mathbb N\}\) where the \(v_i\)'s are \(k\)-tuples of \(\mathbb N^ k\)).
Conjdef: \(R\subseteq \mathbb N^k\)
Definition3: \(R\) is a rational subset of \(\mathbb N^ k\).

Smaller0: \(P=X_1-X_2\) with \(X_2\subseteq X_1\)
Greater0: \(\phi(P)=\phi(X_1)-\phi(X_2)\)
Page: 77
Section: 2
Variables: \(M\) be a monoid,
\(P\) a subset of \(M\) and
\(\phi:M\to N\) be a morphism recognising \(P\).
Index: 7
Kind: Cor

Smaller0: \(R\) is recognisable
Greater0: \(R\) is a finite union of \(R_1\times \dots\times R_n\) with \(R_i\) recognisable subset of \(M_i\)
Page: 80
Section: 2.3
Variables: \(M_1,\dots,M_n\) be monoids,
\(M=\Pi_{i=1}^ nM_i\),
\(R\subseteq M\).
Index: 15
Kind: Prop
Smaller to greater: iff

Definition: The relation which contains \((p,q)\) if there exists a path from \(p\) to \(q\) labelled by \(u\).
Page: 83
Section: 3.2
Chapter: IV
Variables: \(Q\) a set,
\(A\) an alphabet,
\(E\subseteq Q\times Q\),
\(I,F\subseteq Q\),
\(\mathcal A=(Q,A,E,I,F)\) and
\(u\in A^*\).
Notation: \(\mu(u)\)
Morphism: a morphism from \(A^*\) to the monoid of relations of \(Q\).

Smaller0: \(\mathcal A\) recognises \(L\)
Greater0: the transition monoid of \(\mathcal A\) recognises \(L\)
Page: 84
Section: 3.3
Variables: \(\mathcal A=(Q,A,E,I,F)\) an automaton
\(L\subseteq A^*\).
Index: 18
Kind: Prop
Counterexample: take a deterministic automaton recognizing \(L\).
Inverse the accepting state

Smaller0: \(L\) is recognised by a finite monoid
Greater0: a finite determinisitic automaton
Page: 85
Section: 3.3
Variables: \(A\) an alphabet,
\(L\subseteq A^*\) a language
Index: 19
Kind: Prop
Smaller to greater: iff
Prefix Greater: \(L\) is recognised by

Page: 86
Definition: The coarsest congruence relation that saturates \(L\).
Chapter: IV
Section: 4
Variables: \(A\) an alphabet and \(L\subseteq A^*\).
Name: The syntactic congruence of \(L\)
Kind: Prop
Index: 21

Smaller0: recognises \(L\)
Greater0: \(M(L)\) divides \(M\)
Page: 87
Section: 4.2
Variables: \(A\) an alphabet,
\(L\subseteq A^*\)
\(M(L)\) be the syntactic monoid of \(L\)
\(M\) a monoid.
Index: 25
Kind: Prop
Smaller to greater: iff
Prefix Smaller: \(M\)

Smaller0: \(\phi\) recognises \(L\)
Greater0: there is a surjective morphism \(\pi:N\to M(L)\) such that \(\eta_L=\pi\circ \phi\)
Page: 104
Section: 4.2
Variables: \(M,N\) a monoid,
\(\phi:M\to N\),
\(L\subseteq M\) and
\(\eta_L:M\to M(L)\) be the syntactic morphism of \(L\).
Index: 22
Kind: Cor
Smaller to greater: iff
Hide middle: yes

Smaller0: \(M(L^c)\)
Greater0: \(M(L)\)
Page: 88
Section: 4.2
Variables: \(A\) an alphabet and
\(L\subseteq A^*\).
Index: 26 (1)
Kind: Prop
Smaller to greater: equals

Smaller0: \(\bigcup_{i=1}^n (L_i)\) and \(\bigcap_{i=1}^n (L_i)\)
Greater0: the product of \(\phi_i\)
Page: 77
Section: 2.2
Variables: \(M\) be a monoid,
\(L_1,\dots,L_n\) be subsets of \(M\)
\(\phi_1,\dots,\phi_n\) recognizing \(L_1,\dots,L_n\).
Index: 9
Kind: Prop
Smaller to greater: are recognised by
Hide middle: yes
Greater to smaller: recognise

Smaller0: \(M\) recognises \(L\)
Greater0: \(N\) recognises \(L\)
Page: 87
Section: 4.2
Variables: \(A\) an alphabet,
let \(L\subseteq A^*\) and
\(M\) a monoid.
Index: 58
Kind: Prop 4.25
Hide middle: yes
Smaller1: \(M\) divides \(N\)
Extra: Also written as a «closed under»
Connect Smaller0: and

Smaller0: \(\phi\) is surjective
Greater0: the syntactic monoid of \(L\) in \(N\)
Page: 87
Section: 4.2
Variables: \(M,N\) monoid,
\(L\subseteq N\),
\(\phi:M\to N\)
Index: 24
Kind: Prop
Greater1: the syntactic monoid of \(\phi^{-1}(L)\) in \(M\)
Connect Greater0: is equal to

Smaller0: \(M(LK^{-1})\) and \(M(K^{-1}L)\)
Greater0: \(M(L)\)
Page: 88
Section: 4.2
Variables: \(A\) an alphabet and \(K,L\subseteq A^*\).
Index: 26
Kind: Prop
Smaller to greater: divides
Greater to smaller: is a multiple of

Smaller0: the transition monoid of its minimal automaton of \(L\)
Greater0: the syntactic monoid of \(L\)
Page: 88
Section: 4.3
Variables: \(A\) an alphabet and \(L\subseteq A^*\).
Index: 27
Kind: Prop
Smaller to greater: is equal to
Extra: \(L\) is recognisable

Name: An ordered automaton
Definition: \((\mathcal A,\prec)\) where \(p\prec q\) implies \(pu\prec qu\) for all states \(p,q\) and \(u\in A^*\).
Page: 89
Chapter: IV
Section: 5.1

Smaller0: \(L\) is recognised by \((M,\le)\)
Greater0: \(L^C\) is recognised by \((M,\ge)\)
Page: 90
Section: 5.2
Variables: \((M,\le)\) an ordered monoid
\(L\subseteq M\).
Index: 29
Kind: Prop
Smaller to greater: iff

Smaller0: \(L\) is recognisable
Greater0: the syntactic ordered monoid of \(L\)
Page: 92
Section: 5. 4.
Variables: \(M\) a monoid
\(L\subseteq M\).
Index: 5.33
Kind: Cor
Hide middle: yes
Greater1: the transition monoid of the ordered minimal automaton recognizing \(L\)
Connect Greater0: is equal to

Smaller0: \(M(L\cap K)\)
Greater0: \(M(L)\times M(K)\)
Section: 4.2
Variables: \(A\) an alphabet and
\(K,L\subseteq A^*\).
Index: 26
Kind: Prop
Smaller to greater: divides
Greater to smaller: is a multiple of

Smaller0: \(M(\phi^{-1}(L))\)
Greater0: \(M(L)\)
Section: 4.2
Variables: \(A,B\) alphabets,
\(L\subseteq A\)
\(\phi:B^*\to A^*\).
Index: 26
Smaller to greater: divides
Greater to smaller: is a multiple of

Question: If \(M\) recognises \(L\) and if \(N\) divides \(M\), then
Answer: nothing
Page: 106
Chapter: IV
Section: 4.2
Variables: \(L\) be a language of \(A^*\) and let \(M(L)\) be the syntactic monoid of \(l\).
Index: 25
Kind: Prop

Question: \(\phi^{-1}(\phi(L))\)
Answer: equals \(L\)
Page: 76
Chapter: IV
Section: 1
Variables: \(\phi:M\to N\) be a monoid morphism
\(L\) be a subset of \(M\) recognised by \(\phi\).
Index: 5
Kind: Prop

Smaller0: \(\phi\) recognizes \(P\) or \(R\)
Greater0: equals \(\phi(R)\cap\phi(P)\)
Page: 76
Section: 2
Variables: \(M\) be a monoid, \(P,R\) subsets of \(M\) and \(\phi:M\to N\).
Index: 2.6
Kind: Prop
Prefix Greater: \(\phi(R\cap P)\)

Smaller0: \(L\) is saturated by \(\sim_\phi\)
Greater0: \(L\) is recognised by \(\phi\)
Page: 76
Section: 2
Variables: \(\phi:M\to N\) be a monoid morphism
\(L\) be a subset of \(M\).
Index: 5
Kind: Prop
Smaller to greater: iff
Smallest: \(\phi^{-1}(\phi(L))=L\)

Name: recognisable subsets of \(M\)
Page: 77, 78
Section: 2.2
Chapter: IV
Index: 8, 9, 10
Variables: \(M,N\) be a monoid,
\(\phi:M\to N\).
Kind: Prop
Under: complement
Under2: left and right quotient by a subset of \(M\)
Under3: union
Condition3: finite, but not infinite
Under4: intersection
Condition4: finite but not infinite

Name: The set of monoid recognizing \(A\)
Page: 87
Section: 2
Chapter: 4
Index: 25
Variables: \(A\) an alphabet,
\(L\subseteq A^*\)
Kind: Prop
Under: taking a divider of the recognizing monoid
product

Smaller0: \(L\) is recognized by \(\phi\)
Greater0: the morphism \(\phi\)
Page: 75
Section: 2.1
Variables: \(M,N\) a monoid,
\(\phi:M\to N\).
\(L\subseteq M\)
Index: 2.4
Kind: Prop
Greater to smaller: fully recognizes \(L\)