1 First Order Logic
1.1 Some Examples
Provide first-order transductions that represent the following functions:
- The function that maps a word \(w\) to its reverse.
- The function that maps a word \(ab^na\) to \((ab)^n (ba)^n\), \(ba^nb\) to \((ba)^n (ab)^n\), and \(w\) to \(w\) otherwise.
- The function that sorts the letter in a word.
1.2 Some Non-Examples
Prove that the following functions are not representable by first-order transductions:
- The function that maps \(w\) to \(a\) if \(w\) is of odd length and \(b\) otherwise.
- The function that maps \(w\) to \(w^2\) if \(w\) is of even length and \(w^3\) otherwise.
- Given a non-trivial group \((G, \cdot)\), the function that maps a word \(w\) to its image in \(G\).
2 Lambda Terms
2.1 Extra Functions
Prove that the lambda-calculus becomes strictly more expressive when adding the following functions:
- The trace operator \(\mathsf{trace} \colon (A \times B \to A \times B) \to (B \to 1 + B)\) that computes the trace of a function.
- The fold operator \(\mathsf{fold} \colon (Q \times \Sigma \to Q) \to Q \times \Sigma^* \to Q\).
3 Blind again
3.1 Pumping lemma for regular functions
Let \(f\) be a regular function. Prove that there exists \(N \geq 0\) such that for all \(w \in A^*\) with \(|w| \geq N\), there exist \(v_0, v_1 \in A^*\), \(u \in A^+\), \(n \geq 0\), \(\alpha_0, \dots, \alpha_n \in B^*\), \(\beta_1, \dots, \beta_n \in B^+\) such that \(w = v_0 u v_1\) and
\[ f(v_0 u^{X + 1} v_1) = \alpha_0 \beta_1^X \alpha_1 \dots \beta_n^X \alpha_n \quad ,\quad \text{for all } X \geq 0 \quad . \]
Hint: Idempotent transition monoid
Look at idempotent words in the transition monoid of the function \(f\).
Solution: Self-contained proof
One version of the full proof is given by (Douéneau-Tabot 2023, Proposition 2.16).
3.2 Prefixes is not blind
Our goal is to prove that the function prefixes is
not computable by a polyblind
function.
- Let \(f_1, \cdots, f_n\) be regular functions. Is it possible that \(f_1(w) f_2(w) \cdots f_n(w)\) computes a factor of \(\mathsf{prefixes}(w)\) with a number of hashes that tends to \(+\infty\) as \(|w|\) grows?
- Let \(f\) be a regular function. Is it possible that \(f(w)^{|w|}\) computes a factor of \(\mathsf{prefixes}(w)\) with a number of hashes that tends to \(+\infty\) as \(|w|\) grows?
- Using an induction on the polyblind depth and leveraging the pumping lemma of regular functions prove that the function \(\mathsf{prefixes}\) is not polyblind.
Hint: For the first
Note that \(f_1(w) \dots f_n(w)\) is of linear output size.
Hint: For the second
Notice that if \(f(w)\) outputs a word with at least two hashes, then \(f(w)^2\) cannot be a factor of \(\mathsf{prefixes}(w)\). If it has only one hash, then \(f(w)^X = (f(w)^2)^{X/2}\) and we conclude similarly for even \(X\)s.
Hint: For the third
The statement is clear for regular functions. Let us now consider a function obtained by a composition by substitution. Leveraging the pumping lemma for regular functions, conclude that some factor of \(\mathsf{prefixes}(w)\) should be computed by a function lower polyblind depth.
Solution: Self-contained proof
A complete proof of the result can be found in (Douéneau-Tabot 2023, Proposition 3.14).
4 Cheat-Sheet
4.1 Regular functions
A function \(f: A^* \to B^*\) is called a regular function if there exists a two-way deterministic finite automaton with outputs (2DFT) that computes \(f\). Such an automaton has a finite set of states \(Q\) with a distinguished initial state \(q_0\), a transition function function over an extended input alphabet \(\Sigma = A \cup \{ \vdash , \dashv \}\) to delimit the endpoints of the input word. The transition function has the following type \(\delta \colon \Sigma \times Q \to Q \times \{ \leftarrow, \downarrow, \rightarrow, \uparrow \}\). That is, it can read a letter, change state, move left \(\leftarrow\), right \(\rightarrow\), stay in place \(\downarrow\), or exit the computation \(\uparrow\).
The output of the automaton is guided by a production function \(\lambda \colon Q \times \Sigma \to B^*\). That is, for every state and current letter, the automaton can produce some word in \(B^*\).
A run of a 2DFT is a sequence of configurations \((q_i, p_i)\) where \(q_i\) is the ith state of the computation, and \(p_i\) is the ith position of the head over an extended input word \(\vdash w \dashv\). The run starts in the initial state \(q_0\), and the initial position \(p_0 = 0\) (so on the letter \(\vdash\)). The unique run is defined inductively as one expects using the transition function \(\delta\). Note that a regular function should guarantee that the run does not go out of bounds nor loops forever.
The production of a run \(\rho\) of a 2DFT is the word obtained by concatenating the outputs produced by each transition.
4.2 The prefixes function
The prefixes function is defined inductively as follows \(\mathsf{prefixes}(w)\) is the list of non-empty prefixes of \(w\) separated by hashes. For instance, \(\mathsf{prefixes}(abc) = a \# ab \# abc\).
4.3 Composition by substitution
Let \(f\) be a function from \(\Sigma^*\) to \(\{ 1,\dots,k \}^*\), and \(g_1, \dots, g_k\) be functions from \(\Sigma^* \to \Gamma^*\). The composition by substitution of \(f\) by \(g_1, \dots, g_k\) is the function
\[ \mathsf{cbs}(f,g_1, \dots, g_k)(w) = \mathsf{map}(\lambda x. g_x (w)) (f(w)) \quad . \]
4.4 Polyblind functions
The class of polyblind functions is defined as the smallest class of functions containing the regular functions and closed under composition by substitution. The polyblind depth of a function is the smallest \(k\) such that the function can be obtained by composition by substitution of nesting depth at most \(k\).