Title: Theory / Unimportant / CS / Fundamental / Automata / Finite / Pin{ / B Historical results / 07 Piecewise testable languages+50
Tags: fromMath mathToDef toBinaryFunction toBinaryRelation

Page: 145
Section: 2
Notation: \(f\between g\)
Variables: \(A\) an alphabet,
\(f,g\in A^*\)
Chapter: VII
Name: The shuffle of \(f\) and \(g\)
Definition: \(\{f_1g_1\dots f_ng_n\mid f_i,g_i\in A^*, f_1\dots f_n=f, g_1\dots g_n=g\}\)
Associative: Associative
Notation2: [$]f\textvisiblespace\textvisiblespace g[/$]

Name: \(u\) is a subword of \(v\)
Definition: \(u=u_1\dots u_k\) and \(v=v_0u_0v_1\dots u_kv_k\) with \(u_i,v_i\in A^*\)
Page: 141
Chapter: XI
Section: 1
Variables: \(A\) an alphabet
\(u,v\in A^*\)
Name2: \(v\) is a superword of \(u\)

Question: \(L\)'s elements are pair-wise incomparable for the subword relation implies
Answer: \(L\) is finite
Page: 141
Chapter: XI
Section: 1
Variables: \(A\) an alphabet
\(L\subseteq A^*\)
Kind: theo

Name: A subword-free sequence
Definition: A sequence \((u_n)_{n\ge 0}\) if for all \(i<j\), \(u_i\) is not a subword of \(u_j\)
Page: 141
Chapter: XI
Section: 1
Variables: \(A\) an alphabet
\(L\subseteq A^*\)
Kind: theo
Typ: Necessarily finite

Page: 142
Definition: The relations over words containing the same set of subwords of size at most \(i\)
Chapter: XI
Section: 1
Variables: \(A\) an alphabet
Notation: \(\sim_i\)
Kind: , Prop
Index: , 2
Cardinal: Congruence of finite index

Name: The content of \(u\)
Definition: The set of letters occuring in \(u\)
Page: 142
Chapter: XI
Section: 1
Variables: \(A\) an alphabet
\(u\in A^*\)
Index: 4
Kind: Prop
Abbreviation: \(c(u)\)

Definition: The greatest common prefix of \(u\) and \(v\)
Page: 143
Chapter: XI
Section: 1
Variables: \(A\) an alphabet
\(u, v\in A^*\)
\(n\in\mathbb N\)
Notation: \(u\land v\)
Index: 11
Kind: Cor

Smaller0: \(uav\sim_{2n-1}uv\)
Greater0: \(ua\sim_nu\) or \(av\sim_nv\)
Page: 142
Chapter: VII
Section: 1
Variables: \(A\) alphabet
\(u,v\in A^*\)
\(a\in A\)
Construction: take the contraposite:
assume \(xa\) and \(ay'\) are subword of length at most \(n\) of \(ua\) and \(av\) reciprocally, but not of \(u\) and \(v\)
then \(xay\) is a subword of length at most \(2n-1\) of \(uav\) and not of \(av\)

Smaller0: \(u\sim_nvu\)
Greater0: \(c(v)\subseteq c(u_1)\dots,c(u_n)\) when \(u=u_1\dots u_n\)
Page: 142
Chapter: VII
Section: 1
Variables: \(A\) alphabet
\(u,v\in A^*\)
\(a\in A\)
Index: 4
Kind: Prop
Construction: Trivial if \(u=1\)
By induction on \(n\), trivial if \(n=1\)
\(u_{n}\) shortest suffix such that \(c(u)=c(u_{n})\)

Smaller0: \((uv)^nu\) and \(v(uv)^n\)
Greater0: \((uv)^n\)
Page: 143
Chapter: VII
Section: 1
Variables: \(A\) alphabet
\(u,v\in A^*\)
\(a\in A\)
Index: 5
Kind: Cor
Smaller to greater: \(\sim_n\)
Construction: \((uv)^n\sim_nv(uv)^n\) from prop 4, using \(v=v\), \(u_1,\dots,u_n=uv\)

Smaller0: \(u\sim_nv\)
Greater0: there exists \(h\), superword of \(u\) and \(v\), such that \(u\sim_nh\sim_ng\)
Page: 143
Chapter: VII
Section: 1
Variables: \(A\) alphabet
\(u,v\in A^*\)
Index: 5
Kind: Cor
Smaller to greater: iff
Construction: induction on [$]\abs{f}+\abs{g}-2\abs{f\land g}[/$] where \(f\land g\) is their longest common prefix.
Either this number is 0, and \(f=g=h\)
-or one word is suffix of the other, and then \(h\) is the longest of both word
-let \(f=h'af'\), \(g=h'bg'\) with \(b\ne a\), then either \(h'baf'\sim_n h'bg'\) or \(h'abg'\sim_nh'af'\), use the induction on this new pair

Smaller0: \(uav\sim_nubw\)
Greater0: \(ubw\sim_nubav\) or \(uav\sim_nuabw\)
Page: 143
Chapter: VII
Section: 1
Variables: \(A\) alphabet
\(u,v,w\in A^*\)
\(a,b\in A\)
Index: 6
Kind: Prop
Assuming: \(a\ne b\)