📝

1 Combinators

1.1 Playing with combinators

Write the following functions using the combinators and prime functions for regular functions.

  1. The identity map.
  2. \(f_1 \colon w \mapsto ww\).
  3. \(f_2 \colon (ab)^n \mapsto a^n b^n\) and does anything on inputs that do not belong to \((ab)^*\).

1.2 Size restrictions

Let \(f \colon X \to Y\) be a function that can be expressed using the combinators. We define inductively the size of an element in \(X\) as you would expect. Prove that the size of \(f(x)\) is bounded by an affine function on the size of \(x\).

1.3 Higher order constructors

Representing booleans as \(\mathbb{B} :=1 + 1\), write the following functions:

  1. The map \(\land \colon \mathbb{B}^2 \to \mathbb{B}\),
  2. The map \(\lor \colon \mathbb{B}^2 \to \mathbb{B}\),
  3. The map \(\mathsf{if} \colon \mathbb{B} \times X \times X \to X\),
  4. The map \(\mathsf{any} \colon \mathbb{B}^* \to \mathbb{B}\),
  5. The map \(\mathsf{all} \colon \mathbb{B}^* \to \mathbb{B}\).

1.4 Internal regular languages

Write a function \(f \colon \Sigma^* \to \mathbb{B}\) that recognizes the language \((ab)^*\).

1.5 Binding of variables

Write a function \(f \colon xwy \mapsto (xy)^{|w|}\), where \(x\) and \(y\) are letters. Is it possible to define the function \(g \colon (u,w) \mapsto u^{|w|}\)?

2 Previously

2.1 Recursive Invisible Pebbles

We define a recursive invisible pebble transducer as follows: it is a collection of 2DFTs over the same input alphabet \(\Sigma\) and the same output alphabet \(\Gamma\), where the transitions are defined as usual, except that some transitions can perform a recursive call to another 2DFT in the family. This recursive call is launched over the whole input word, with a distinguished position where the head was placed before the call. Once this computation terminates, the control goes back to the calling transducer, and its run continues.

Prove that the class of functions computed by recursive invisible pebble transducers with unary output alphabets is the same as the class of functions computed by rational series.

2.2 Linear Growth

Prove that the following are equivalent in the case of \(\mathbb{N}\)-weighted automata:

  1. Weighted automata with linear growth.
  2. 2DFTs with unary output.

What about the case of \(\mathbb{Z}\)?

2.3 Minimising growth

Recall that in \(\mathbb{MSO}\)-transductions, we introduced a duplication function \(d_{\alpha, \beta}\) that maps \(w\) to \(\diamond^\beta \prod_{i = 1}^{|w|} w_i (\#)^{\alpha - 1}\). Any regular function is written as the composition of an \(\mathbb{MSO}\)-intepretation (without copies) with a duplication. As a consequence, \(|f(w)| \leq \alpha |w| + \beta\) for some \(\alpha, \beta \in \mathbb{N}\).

Question: assume that there exists \(\alpha', \beta' \in \mathbb{N}\) such that \(|f(w)| \leq \alpha' |w| + \beta'\) for all \(w\). Is it possible to represent \(f\) using \(d_{\alpha',\beta'}\) followed by an \(\mathbb{MSO}\)-intepretation.

References