2.1 Invertible functions

Let \(f \colon \Sigma^* \to \Gamma^*\) be an injective function. Is it true that if \(f\) is linear regular, then so is the partial inverse \(f^{-1}\)? What about polyregular?

2.2 Context-free languages

Let \(L\) be a context-free language, and \(f\) be a polyregular function. Is it decidable whether \(f^{-1}(L) \neq \emptyset\)?

2.3 Image Intersection

Let \(f_1\) and \(f_2\) be two polyregular functions from \(\Sigma^*\) to \(\Gamma^*\). Is it decidable whether \(f_1\left(\Sigma^*\right) \cap f_2\left(\Sigma^*\right) = \emptyset\)?

2.4 Image of linear regular

Let \(f\) be a linear regular function from \(\Sigma^*\) to \(\Gamma^*\). We define \(\mathsf{growth}_f(n)\) to be the maximum among all words \(w \in \Sigma^{\leq n}\) of the length of \(f(w)\). Prove that one of the following holds:

1. The function \(\mathsf{growth}_f\) is bounded.
2. There exists a \(\alpha > 0\), for large enough \(n \in \mathbb{N}\), \(\mathsf{growth}_f (n)\) is at least \(\alpha n\).

2.5 Polyregular Reductions

Consider two decision problems (which is the same thing as a language) \(A \subseteq \Sigma^*\) and \(B \subseteq \Gamma^*\). A polyregular reduction from a problem \(A\) to a problem \(B\) is a polyregular function \(f \colon \Sigma^* \to \Gamma^*\) such that for all \(w \in \Sigma^*\), \(w \in A\) if and only if \(f(w) \in B\).

We write boolean formulas as strings over the alphabet \(\Sigma :=\{ a, \neg, \land, \lor, (, ) \}\). Variables are encoded as \(a^n\) for some \(n\). For instance, \((a \land \neg( aa \vee aaaa))\) is a valid formula which uses three variables \(a\), \(aa\) and \(aaaa\). The language of valid formulas is given by the following grammar: \(F \mapsto ( F \land F ) \mid ( F \lor F ) \mid \neg F \mid V\) and \(V \mapsto aV \mid a\). In particular, valid formulas are well-bracketed expressions.

We call \(\mathsf{SAT}\) the list of satisfiable boolean formulas written over this alphabet. We call \(\mathsf{CNFSAT}\) the list of satisfiable boolean formulas where the formula is in conjunctive normal form (CNF), that is, it is a conjunction of disjunctions of variables or their negations.

Construct a polyregular reduction from \(\mathsf{SAT}\) to \(\mathsf{CNFSAT}\).