Title: Theory / Unimportant / CS / Fundamental / Automata / Finite / Pin{ / B Historical results / 06 Star-free languages
Tags: fromMath hasSeenConjDef

Name: A star-free language of \(A^*\)
Definition: either the empty set, \(\{1\}\), \(\{a\}\) for \(a\in A\), or a finite finite Boolean operations of such objects
Page: 133,135, 171
Chapter: VI,, IX
Section: 1, 2, 4.1
Variables: \(A\) an alphabet
Definition2: whose syntactic monoid is aperiodic
Example: \(A^*=0^c\)
Conjdef: A language, equivalently
Definition3: Definable by a formula of \(\mathrm{FO}[<]\)
Example2: \(B^*\) for each \(B\subseteq A\)
Example3: \((ab)^*\)

Name: An aperiodic finite ordered monoid
Definition: which satisfies the equation \(x^{n+1}\le x^n\) for some \(n\) (assuming \(M\) finite)
Page: 134
Chapter: VI
Section: 2
Kind: Prop
Definition2: whose underlying monoid is aperiodic
Conjdef: An ordered monoid \(M\) equivalently
Construction: \(x^n=x^{n+1}\) implies \(x^n\le x^{n+1}\)
Assume the inequality holds. \(\omega\ge n\), multiple of the exponent of \(M\)
\(x^\omega=x^{2\omega}\le x^{2\omega-1}\le\dots x^{\omega+1}\le x^\omega\) thus \(x^\omega=x^{\omega+1}\) for all \(x\in M\)

Name: Schützenberger, theorem
Definition: A language is star-free iff its syntactic monoid is aperiodic.
Page: 135
Chapter: VI
Section: 3
Kind: Theo

Name: The set of star-free languages
Definition: the empty language
Page: 133
Chapter: VI
Section: 1
Variables: \(A\) an alphabet
Definition2: containing the language \(\{1\}\)
Conjdef: The least class
Definition3: containing the languages \(\{a\}\) for each letter \(a\)
Intuition: Rational, but Kleene star is replaced by complement
Definition4: closed under finite union
Definition5: closed under finite product
Definition6: closed under complement

Question: How to write \(A^*\) star-free
Answer: \(0^c\)
Page: 133
Chapter: VI
Section: 1
Variables: \(A\) an alphabet

Question: How to write \(A^*\) star-free
Answer: \(A^*-A^*(A\setminus B)A^*\)
Page: 133
Chapter: VI
Section: 1
Variables: \(A\) an alphabet
\(B\subseteq A\)
Kind: Ex

Question: How to write \((ab)^*\) star-free
Answer: \((b0^c+0^ca+0^caa0^c+0^cbb0^c)^c\)
Page: 133
Chapter: VI
Section: 1
Variables: \(A\) an alphabet
\(B\subseteq A\)

Name: An aperiodic monoid
Definition: for each \(x\in M\), \(x^n=x^{n+1}\) for some \(n>0\)
Page: 134
Chapter: VI
Section: 2
Index: 1
Kind: Prop
Definition2: there exists \(n>0\) such that \(x^n=x^{n+1}\) for each \(x\) (assuming \(M\) finite)
Conjdef: equivalently
Definition3: \(M\) is \(\mathcal H\)-trivial
Definition4: the groups in \(M\) are trivial
DefType: A monoid \(M\)

Name: Aperiodic monoid
Page: 134
Section: 2
Chapter: VI
Under: product
Condition: finite

Name: Aperiodic ordered monoid
Page: 134
Section: 2
Chapter: VI
Under: product
Condition: finite
CounterExample: Let \(A_n=(\{1,\dots,n\},(a,b)\mapsto\min(a+b,n))\), its aperiodic. In \(\prod_{i=1}^\infty A_i\), \((1)_{i=1}^\infty\) has no idempotent power.

Question: How to separate two distinct words
Answer: if their length is distinct, count modulo \(\mathbb Z/m\mathbb Z\), with \(m\) minimal such that [$]\abs{w}\not\equiv\abs{w'}\mod m[/$]
Page: 180
Chapter: X
Section: 2.1
Variables: \(w,w'\in A^*\)
Answer2: previous case, ignoring some letters of the alphabet
Index: 1
Kind: Ex

Smaller0: an open ball in \((A^*,d)\)
Greater0: recognisable
Page: 182
Chapter: X
Section: 2.1
Variables: \(A\) an alphabet
\(L\subseteq A^*\)
Index: 5
Kind: Prop
Prefix Greater: \(L\) is

Page: 133,135, 171
Chapter: VI,, IX
Section: 1, 2, 4.1
Variables: \(A\) an alphabet
\(L\subseteq A^*\)
Smaller to greater: star-free
Prefix Greater: \(L\) is
Greater1: rational