4.1.1 Codes with Bounded Delay

Let us write \(\Gamma :=\{ x_1, \dots, x_n \} = X\). By definition, \(X\) is a code if the map \(\beta \colon \Gamma^* \to \Sigma^*\) defined by \(\beta(x_i) = x_i\) is injective.

A set \(X \subseteq \Sigma^*\) is a prefix code if no word of \(X\) is a prefix of another word of \(X\).

A code with bounded delay \(d\) is a code \(X\) such that for all \(u \in \Gamma^{d+1}\), for all \(v \in \Gamma^*\) if \(\beta(u) \mathrel{\sqsubseteq_{\mathsf{prefix}}}\beta(v)\) then \(u_1 = v_1\).

4.2.1 Regular Language

A regular language is a language that is recognized by a deterministic finite automaton.

4.2.2 Mealy Machine

Let \(\Sigma\) and \(\Gamma\) be two alphabets. A Mealy Machine \(\mathcal{M}\) is a tuple \((q_0, Q, \delta, \lambda)\) such that

1. \(Q\) is a finite set of states.
2. \(q_0 \in Q\) is the initial state.
3. \(\delta \colon Q \times \Sigma \to Q\) is a transition function.
4. \(\lambda \colon Q \times \Sigma \to \Gamma\) is an output function.

The semantics of a Mealy Machine is given by the following inductive equations: \[ \mathcal{M}(w) :=\mathcal{M}(q_0, w) \quad \mathcal{M}(q,\varepsilon) :=\varepsilon \quad \mathcal{M}(q,au) :=\lambda(q,a) \mathrel{\cdot}\mathcal{M}(\delta(q,a), u) \]

4.2.3 Mealy Machine With Lookahead

Let \(\Sigma\) and \(\Gamma\) be two alphabets. A Mealy Machine with Lookahead \(\mathcal{M}\) is a tuple \((q_0, Q, \delta, \lambda)\) such that

1. \(Q\) is a finite set of states.
2. \(q_0 \in Q\) is the initial state.
3. \(\delta \subseteq Q \times \Sigma \times Q\) is a transition relation.
4. \(\lambda \colon Q \times \Sigma \times Q \to \Gamma\) is an output function.

In addition to this syntactic definition, we furthermore assume that for each \(w \in \Sigma^*\), there exists at most one path in the automaton \((q_0, Q, \delta)\) starting from \(q_0\) and reading \(w\).

The semantics of the Mealy Machine is given by considering potential runs of the machine. Because of the absence of ambiguity, it defines a partial map \(\mathcal{M} \colon \Sigma^* \rightharpoonup\Gamma^*\).

4.2.4 Sequential Functions

Let \(\Sigma\) and \(\Gamma\) be two alphabets. A sequential transducer \(A\) is a tuple \((q_0, Q, \delta, \lambda)\) such that

1. \(Q\) is a finite set of states.
2. \(q_0 \in Q\) is the initial state.
3. \(\delta \colon Q \times \Sigma \rightharpoonup Q\) is a partial transition function.
4. \(\lambda \colon Q \times \Sigma \to \Gamma^*\) is an output function.

The semantics is defined as for Mealy Machines.

Warning: this is sometimes called pure sequential functions. In this document, we call impure sequential functions those that also have an output function \(\rho \colon Q \to \Gamma^*\) that is called at the end of the computation.

4.2.5 Eilenberg Bimachines

An Eilenberg Bimachine is a tuple \((A, B, \pi, u)\) where \(A\) and \(B\) are two deterministic finite automata, and \(u \in \Gamma^*\), together with a production function \(\pi \colon Q_A \times Q_B \times \Sigma \to \Gamma^*\).with a production function

The semantics of an Eilenberg Bimachine over non-empty words is given as follows:

1. We run \(A\) on the input from left to right
2. We run \(B\) on the input from right to left
3. We replace every letter \(a_i\) of the input by the word \(\pi(q^A_i, q^B_i, a_i)\) where \(q^A_i\) and \(q^B_i\) are respectively the states of \(A\) after the letter \(a_i\) and \(B\) before the letter \(a_i\).

For empty words, the bimachine outputs \(u\).

4.3.1 Graph of a Function

Let \(f \colon X \to Y\) be a function. The graph of \(f\) is the set \(\mathsf{graph}(f) :=\left\{(x, f(x)) \mid x \in X\right\}\).

4.3.2 Topology and Continuous functions

Let \(X\) be a set. A topology over \(X\) is a subset \(\tau\) of \(\mathop{\mathcal{P}}(X)\) closed under finite intersections and arbitrary unions. In a topological space \((X, \tau)\), the subsets in \(\tau\) are called open subsets, and their complement are called closed subsets.

A function \(f \colon (X, \tau) \to (Y,\theta)\) is continuous whenever for all open subset \(U \in \theta\), its pre-image \({f}^{-1}\left(U\right)\) is an open subset of \(\tau\). Equivalently, it is continuous if the pre-image of closed subsets are closed subsets.

4.3.3 Lipschitz functions

A function \(f \colon (X,d_X) \to (Y, d_Y)\) is Lipschitz if there exists a constant \(K \geq 0\) such that for all \(x_1,x_2 \in X^2\), \(d_Y(f(x_1), f(x_2)) \leq K d_X(x_1, x_2)\).

4.3.4 Prefix Distance

Let \(\Sigma^*\) be a finite alphabet. The prefix distance between two words \(u,v\) is \(\left| u \right|_{} + \left| v \right|_{} - 2 \left| w \right|_{}\) where \(w\) is the longest common prefix of \(u\) and \(v\).

4.3.5 Regular Topology

Let \(\Sigma\) be a finite alphabet. We equip \(\Sigma^*\) with a metric distance as follows: to a pair of words \(u,w\), we associate the minimal size \(s(u,w)\) of a deterministic automaton that separates \(u\) from \(w\). The distance between two words \(u\) and \(w\), is defined as \(d(u,w) :=2^{-s(u,w)}\). The regular topology is the topology defined by this metric on \(\Sigma^*\).

Equivalently, the regular topology is the coarsest topology containing the regular languages as closed subsets.