Title: Theory / Unimportant / CS / Fundamental / Automata / Infinite / Perrin Pin+10 / 09 Bi infinite words
Tags: fromMath mathToDef toBinaryFunction
On every note of this deck, unless a note says otherwise:
Chapter: IX
Section: 2

Name: Bi-infinite word
Definition: An element of \(A^{\mathbb Z}\).
Page: 382
Variables: \(A\) an alphabet

Name: The shift of \(w\)
Definition: \(i\mapsto w_{i-1}\).
Page: 382
Variables: \(A\) an alphabet
\(w\) a bi-infinite word
Notation: \(\sigma(w)\)

Definition: A language of infinite word closed under \(\sigma\)
Page: 382
Variables: \(A\) an alphabet
Notation: Shift-invariant language

Definition: \(u_i\dots u_j\).
Page: 382
Variables: \(A\) an alphabet and \(w\) a bi-infinite word, \(i\le j\in \mathbb Z\)
Notation: \(w[i,j]\)

Smaller0: \(U\) is open
Greater0: \(U\) is the shifts of \(\{u\in A^{\mathbb Z}\mid u[0,+\infty[\in XA^\omega\}\) for some \(X\subseteq A^*\)
Page: 382
Chapter: IX
Section: 2
Variables: \(A\) an alphabet and
\(U\) a set of bi-infinite words
Smaller to greater: iff

Name: Left infinite word
Definition: An element of \(A^{-\mathbb N}\).
Page: 382
Variables: \(A\) an alphabet.

Definition: The left infinite word \(v\) such that \(v_{-n}=u_n\).
Page: 382
Variables: \(A\) an alphabet and \(u\in A^\omega\)
Notation: \(\overline u\)

Definition: The set of reversals \(\overline x\) for \(x\in X\).
Page: 382
Variables: \(A\) an alphabet and \(X\subseteq A^+\)
Notation: \(\overline X\)

Definition: \(\overline{\left(\tilde X\right)^\omega}\).
Page: 383
Variables: \(A\) an alphabet and \(X\subseteq A^+\)
Notation: \(X^{\overline \omega}\)

Definition: \(\overrightarrow{\left(\widetilde{\left(\tilde X \right)}\right)}\).
Page: 383
Variables: \(A\) an alphabet
\(X\subseteq A^+\)
Notation: \(\overleftarrow X\)
Extra: It is indeed rightarrow

Definition: \(\{y\in A^*\mid uy\in X\}\)
Page: 383
Variables: \(A\) an alphabet,
\(X\subseteq A^+\)
a left-infinite word
Notation: \(u^{-1}X\)

Definition: The function sending \(i\ge 0\) to \(u_i\) and \(i<0\) to \(v_{i+1}\)
Page: 383
Variables: \(A\) an alphabet,
\(u\in A^{\mathbb N}\),
\(v\in A^{-\mathbb N}\)
Notation: \([v,u]\)
Intuition: concatenation of \(v\) and \(u\)

Definition: The closure of \([V,U]\) under the shift operator.
Page: 383
Variables: \(A\) an alphabet,
\(U\subseteq A^{\mathbb N}\)
\(V\subseteq A^{-\mathbb N}\)
Context: Infinite word
Notation: \(VU\)

Definition: Equivalently \((VW)U\) and \(V(WU)\).
Page: 383
Variables: \(A\) an alphabet,\(U\subseteq A^{\mathbb N}, V\subseteq A^{-\mathbb N}, W\subseteq A^*\)
Notation: \(VWU\)

Definition: \(X^{\overline \omega}X^\omega\).
Page: 383
Variables: \(A\) an alphabet,
\(X\subseteq A^*\)
Notation: \(X^\zeta\)

Definition: The quotient of \(A^{\mathbb Z}\) by the equivalence generated by the shift function.
Page: 384
Variables: \(A\) an alphabet
Notation: \(A^\zeta\)

Definition: The set of words of the form \(uv_1v_2\dots\) with \(u\) left-infinite and \(v_i\) finite, such that \(uv_1\dots v_i\in U\) for all \(i\in\mathbb N\).
Page: 384
Variables: \(A\) an alphabet and
\(U\subseteq A^{-\mathbb N}\).
Notation: \(\overrightarrow U\)

Definition: The set of words \(\dots u_1u_0v_0v_1\dots\) such that \(u_i\dots u_0v_0\dots v_i\in X\) for all \(i\in \mathbb N\).
Page: 384
Variables: \(A\) an alphabet
\(U\subseteq A^{*}\).
Notation: \(\overleftrightarrow U\)

Page: 382
Section: 2
Notation: \(d(u,v)\)
Variables: \(A\) an alphabet and
\(u,v\) bi-infinite words
Chapter: IX
Definition: \(2^{\text{sup}\{i\ge0\mid u[-i,i]=v[-i,i]\} }\).

Question: \(\overleftrightarrow{a^*b^*}\)
Answer: equals \(a^\zeta+b^\zeta+a^{\bar\omega}b^\omega\)
Page: 385
Chapter: IX
Section: 2

Smaller0: \(\overrightarrow{U^{\bar\omega}V}\)
Greater0: \(U^{\bar\omega}\overrightarrow{(U^*V)}\)
Page: 385
Chapter: IX
Section: 2
Variables: \(A\) an alphabet,
\(U,V\subseteq A^+\) recognisable
Smaller to greater: =

Smaller0: \(X\) is a prefix or suffix recognisable set
Greater0: \(=\emptyset\)
Page: 385
Chapter: IX
Section: 2
Variables: \(A\) an alphabet,
\(X\subseteq A^+\) recognisable
Prefix Greater: \(\overleftrightarrow X\)

Name: A bi-infinite path in the automaton
Definition: A bi-infinite sequence of consecutive arrows.
Page: 386
Variables: \(A\) an alphabet,
\(\mathcal A=(Q,A,E,I,F)\) an automaton
Denoted by: \((p_n,a_n,p_{n+1})_{n\in\mathbb Z}\)

Name: The label of \(p\)
Definition: \((a_n)_{n\in\mathbb Z}\)
Page: 386
Variables: \(A\) an alphabet,
\(\mathcal A=(Q,A,E,I,F)\) an automaton,
\(p=(p_n,a_n,p_{n+1})_{n\in\mathbb Z}\) a bi-infinite path

Name: A successfull bi-infinite path
Definition: A bi-infinite path \((p_n,a_n,p_{n+1})_{n\in\mathbb Z}\) which is succesfull left-infinite and successfull right-infinite
Page: 386
Variables: \(A\) an alphabet,
\(\mathcal A=(Q,A,E,I,F)\) an automaton,

Name: A successfull left-infinite path
Definition: A left-infinite path \((p_n,a_n,p_{n+1})_{n\in-\mathbb N}\) with \(p_i\in I\) for infinitely many \(i\)
Page: 386
Variables: \(A\) an alphabet,
\(\mathcal A=(Q,A,E,I,F)\) an automaton,

Name: A recognisable subset of \(A^\zeta\)
Definition: A set of the form \(L^\zeta(\mathcal A)\)
Page: 386
Variables: \(A\) an alphabet
Typ: Shift-invariant language

Definition: The set of bi-infinite words recognized by \(\mathcal A\)
Page: 386
Variables: \(A\) an alphabet,
\(\mathcal A=(Q,A,E,I,F)\) an automaton
Notation: \(L^\zeta(\mathcal A)\)

Name: A \(\zeta\)-rational language
Definition: A language of the form \(X^{\bar\omega}YZ^\omega\) for \(X,Y,Z\in Rec(A^*)\)
Page: 386
Variables: \(A\) an alphabet