📝

1 Deciding Growth of Unary Output

The goal of this longer exercise is to prove the following statement relating the growth rate of a function to its dimension in a specific case.

Let \(f\) be an N-polyregular function. The following are equivalent

  1. \(f\) is computed by an \(\mathbb{MSO}\)-interpretation of dimension \(d\).
  2. The growth rate of \(f\) is \(O(n^d)\).

1.1 Playing with unary output

Prove the following equivalence:

  1. \(f\) is N-polyregular (resp. Z-polyregular) of dimension \(d\)
  2. \(f\) is a \(\mathbb{Z}\)-linear combination (resp. \(\mathbb{N}\)-linear combination) of of functions of the form \(\# \varphi\) where \(\varphi\) is an \(\mathbb{MSO}\)-formula with at most \(d\) variables.

1.2 A non-result

Is the following function N-polyregular? Z-polyregular?

\[ f(w) :=(\left| w \right|_{a} - \left| w \right|_{b})^2 \quad . \]

1.3 Simple operations

Let \(f\) and \(g\) be two N-polyregular functions. Prove that \(f \times g\) is N-polyregular, where \(f \times g\) is defined by \((f \times g)(w) := f(w) \times g(w)\). Similarly, prove that \(f \otimes g\) is N-polyregular, where \(f \otimes g\) is defined by \((f \otimes g)(w) :=\sum_{uv = w} f(u) \times g(v)\).

1.4 Alternative definition

Prove that for all \(n \in \mathbb{N}\), we have \(\mathsf{Z}\text{-}\mathsf{Poly}_{n+1} = \mathsf{Span}_{}(\left\{ \mathbf{1}_{L} \otimes f \mid f \in \mathsf{Z}\text{-}\mathsf{Poly}_{n} \right\})\).

1.5 Polyregular Functions and Matrices

Let \(f\) be a Z-rational series defined by a minimal representation \((I, \mu, F)\). Let \(w \in \Sigma^*\) and \(\lambda \in \mathsf{Spec}(\mu(w))\). There exist coefficients \(\alpha_{i,j} \in \mathbb{C}\) and words \(u_1, v_1, \dots, u_n, v_n \in \Sigma^*\) such that

\[ \lambda^X = \sum_{i,j = 1}^n \alpha_{i,j} f(v_i w^X u_j) \quad \forall X \geq 0 \quad . \]

To prove the statement, you can use the fact that in a minimal representation, and therefore that \(\mathsf{Span}_{\mathbb{Q}}(\left\{ \mu(w)F \mid u \in \Sigma^*\right\})\) equals \(\mathbb{Q}^n\). Similarly, for a minimal representation, \(\mathsf{Span}_{\mathbb{Q}}(\left\{ I\mu(w) \mid u \in \Sigma^* \right\})\) equals \(\mathbb{Q}^n\).

1.6 Series of Polynomial Growth

Let \(f\) be a Z-rational series of growth rate \(O(n^d)\). Prove that \(f\) is Z-polyregular of dimension \(d\).

You may use the following corollary of (Berstel and Reutenauer 2010, Corollary 2.6 page 159) stating

Let \(f\) be a Z-rational series of growth rate \(O(n^d)\). Then \(f\) belongs to span of the products of at most \(q + 1\) characteristic series of rational languages.

1.7 Ultimately polynomial functions

Let \(f\) be a function from \(\Sigma^*\) to \(\mathbb{Z}\). Prove that the following are equivalent:

  1. \(f\) is a Z-rational series that has polynomial growth,
  2. \(f\) is a Z-rational series that is ultimately N-polynomial,
  3. \(f\) is a Z-rational series with eigenvalues in \(\mathbb{U} \cup \{ 0 \}\),
  4. \(f\) is a Z-rational series with eigenvalues in \(B(0,1)\).

Where ultimately N-polynomial means that for all pumping patterns, there exists a polynomial \(P\) such that

\[ f( \alpha_0 w_1^{NX_1} \alpha_1 w_2^{NX_2} \dots \alpha_{n-1} w_n^{NX_n} \alpha_n) = P(X_1, \dots, X_n) \quad \text{when the $X_i$'s are large enough} \quad . \]

You may use the following corollary of (Bell 2005, Theorem 2.6) stating

Let \(A\) be a finite set of \(d \times d\) complex matrices and \(\langle A \rangle\) be the semigroup generated by \(A\). Assume that all the eigenvalues of the elements of \(\langle A \rangle\) are in or on the unit disc. Then for any matrix norm \(\| \cdot \|\), and product \(P\) of at most \(n\) matrices in \(A\), \(\| P \| = O(n^{d-1})\).

1.8 Growth of Unary Output

Let \(f\) be an N-polyregular function. Prove the following equivalences:

  1. \(f\) is computed by an \(\mathbb{MSO}\)-interpretation of dimension \(d\),
  2. \(f\) is not \((d+1)\)-pumpable,
  3. \(f\) has growth rate \(O(n^d)\).

Where a function is \(d\)-pumpable if there exists a family of words such that

\[ f(\alpha_0 w_1^{X_1} \alpha_1 w_2^{X_2} \dots \alpha_{n-1} w_n^{X_n} \alpha_n) = \Omega(|X_1 + \dots + X_n|^d) \quad . \]

To that end, you may use the forest factorisation theorem of Simon, which states that for all N-polyregular functions \(f\), there exists a regular function \(g\) from \(\Sigma^*\) to trees of bounded depth such that \(f(w) = h \circ g(w)\) where \(h\) counts the number of patterns of certain shapes in the tree.

1.9 Growth when negative values are allowed

Let \(f\) be a Z-polyregular function. Prove the following equivalences:

  1. \(f\) is computed by an \(\mathbb{MSO}\)-interpretation of dimension \(d\),
  2. \(f\) is not \((d+1)\)-pumpable,
  3. \(f\) has growth rate \(O(n^d)\).

Use the following decomposition of \(f\) into \(f_\text{dep} + f_{\text{indep}}\) where \(f_{\text{dep}}\) counts independent tuples of variables, and \(f_{\text{indep}}\) counts dependent tuples of variables. Then, conclude by induction.

2 Compression

2.1 Straight line program evaluation

Let \(e\) be the evaluation function from straight line programs to strings. Is \(e\) a polyregular function?

Solution: Solution

The function \(e\) is not polyregular, because \(e\) can have exponential size output, for instance by compressing \(a^n\) into \(O(\log(n))\) operations.

2.2 Efficient compression

What is the minimal size (number of instructions) needed to express \(\mathsf{prefixes}(a^n)\) as a straight line program?

Hint: What about variables containing two hashes?

Let \(x_i\) be a variable in a straight line program that evaluates to \(\mathsf{prefixes}(a^n)\) and that contains a string with two hashes. Can it be used twice?

Solution: Solution

We prove that a straight line program that evaluates to a factor of \(\mathsf{prefixes}(a^n)\) having \(k\) hashes must contain at least \(k\) variables evaluating to words containing at least two hashes.

Let us first remark that every variable in the straight line program containing more than one hash can only be used once, as otherwise the output word contains two hash-separated words of the same size, which contradicts the definition of \(\mathsf{prefixes}(a^n)\).

For the base case, if the factor contains at least one hash, then the straight line program must contain at least one instruction.

For the induction, let \(x_\ell\) be the last variable of the straight line program. It cannot be a constant assignment because the factor contains at least two hashes. Therefore, \(x_\ell = x_i x_j\) for some \(i,j < \ell\). By the induction hypothesis, \(x_i\) and \(x_j\). If \(x_i\) contains at least two hashes, then it can only be used once, and \(x_i \neq x_j\), otherwise, \(x_j\) contains a factor of \(\mathsf{prefixes}(a^n)\) with at least \(k\) hashes, but of smaller size and we proceed by induction. Now, because \(x_i\) and \(x_j\) are distinct variables, and because every variable containing at least two hashes can only be used once, we can partition the variables of the straight line program into three sets: the ones containing at most one hash, the ones containing at least two hashes used to build \(x_i\), and the ones containing at least two hashes used to build \(x_j\). Using the induction hypothesis we conclude as desired.

2.3 Straight-line homomorphic programs

A function \(f\) is straight-line homomorphic if there exists a polynomial time algorithm \(P\) such that for all straight line program \(X\), \(f(e(X)) = e(P(X))\), where \(e\) is the expansion function.

  1. Prove that \(\mathsf{prefixes}\) is not straight-line homomorphic.
  2. Prove that regular functions are straight-line homomorphic.
Solution: Proof of the first implication

It is clear that \(\mathsf{prefixes}\) is not straight-line homomorphic because \(\mathsf{prefixes}(a^n)\) cannot be compressed in less than \(n\) instructions, while \(a^n\) can be compressed in \(O(\log(n))\) instructions. If \(\mathsf{prefixes}\) were straight-line homomorphic, then the compression of \(\mathsf{prefixes}(a^n)\) would be doable in \(O(P(\log(n)))\) instructions.

Solution: Sketch of the second implication using Monoids

For the second part. Let \(f\) be computed by a copyless SST with states \(Q\), registers \(\{ 1, \dots, n \}\), and output function \(F\). The sketch of the proof is as follows: we construct the transition monoid of the SST, and prove that we can encode it inside a straight line program.

To a word \(w\) we associate the function from \(Q \times (\Gamma^*)^n \to Q \times (\Gamma^*)^n\) that maps a state \(q\) and a tuple of registers \(r\) to the state \(q'\) and the tuple of registers \(r'\) that the SST would be in after reading \(w\) starting in state \(q\) and with registers \(r\). Note that this monoid is finitely generated, but is not finite, because of the unbounded values in the registers.

However, the program is copyless, meaning that the value in a register is a function of the form \(r_i' \leftarrow \alpha_0 r_{j_0} \alpha_1 r_{j_1} \dots\) where the \(\alpha\)’s are constants in \(\Gamma^*\), and the indices \(j_k\) are distinct. In particular, since we can only use each register once, we have at most \(n+1\) words \(\alpha_0, \dots, \alpha_n\) in the update function.

Now, we will encode the transition of a word \(w\) in a straight line program by using variables \(y_{i,q,r}\) that encode the \(i\)th word \(\alpha\) in the update function of the register \(r\) after reading \(w\) if starting in state \(q\). These can be composed to simulate the transition of the SST on the input word.

This new straight-line program is constructed in polynomial time.

Solution: Proof of the second implication using Krohn–Rhodes decompositions

Remark that functions that can be efficiently evaluated over compressed strings are closed under composition. Therefore, it is enough to prove that the basic functions in a Krohn–Rhodes decomposition can be evaluated efficiently.

It is clear that any homomorphism can be efficiently evaluated. For mealy machines, it is very simple, as one can encode the transition monoid inside the decomposition. For map-duplicate and map-reverse, a simple straight-line program can be constructed.

3 Cheat-Sheet

3.1 Rational Series

Recall that a rational series is a triple \((I, \mu, F)\) where \(I\) is a vector of initial values, \(\mu\) is a matrix of transitions, and \(F\) is a vector of final values. The function \(f\) associated to the rational series is defined by

\[ f(w) :=I \mu(w) F \quad . \]

If the coefficients are restricted to belong to \(\mathbb{N}\), \(\mathbb{Z}\) or \(\mathbb{Q}\), we call them respectively N-rational series, Z-rational series, and Q-rational series.

3.2 Grwoth rate

Let \(f \colon \Sigma^* \to \Gamma^*\), its growth rate is a function that maps \(n \in \mathbb{N}\) to the maximal value of \(\left| f(w) \right|\) for \(w \in \Sigma^n\).

3.3 Dimension

In this exercise sheet, an interpretation of dimension \(d\) is an \(\mathbb{MSO}\)-interpretation where the maximal arity of the polynomial functor describing the domain is \(d\).

3.4 Z-Polyregular Functions

A function \(f\) is Z-polyregular if there exists a polyregular function \(g \colon \Sigma^* \to \{ -1,+1 \}^*\) such that \(f(w) = \sum(g(w))\) for all \(w \in \Sigma^*\). If the function \(g\) has outputs in \(\{ 1 \}^*\), then it is called N-polyregular. Furthermore, if the function \(g\) is star-free (i.e., first-order) then we say that \(f\) is Z-star-free (resp. N-star-free).

This provides us with the following table of functions

\(\{ -1,+1 \}^*\) \(\{ 1 \}^*\)
Polyregular Z-polyregular (\(\mathsf{Z}\text{-}\mathsf{Poly}_{}\)) N-polyregular (\(\mathsf{N}\text{-}\mathsf{Poly}_{}\))
Star-free Z-star-free (\(\mathsf{Z}\text{-}\mathsf{SF}_{}\)) N-star-free (\(\mathsf{N}\text{-}\mathsf{SF}_{}\))

3.5 Straight line program

A straight line program over an alphabet \(\Sigma\) is a finite sequence of instructions of the form \(x_i := u\) where \(u\) is a single letter, or \(x_i := x_j x_k\) with \(i > j,k\). The value of a straight line program is the value of the last variable.

References

Bell, Jason P. 2005. ‘A Gap Result for the Norms of Semigroups of Matrices’. Linear Algebra and Its Applications 402: 101–10. https://doi.org/https://doi.org/10.1016/j.laa.2004.12.007.
Berstel, Jean, and Christophe Reutenauer. 2010. Noncommutative Rational Series with Applications (Encyclopedia of Mathematics and Its Applications). 1st ed. Encyclopedia of Mathematics and Its Applications 137. Cambridge University Press. https://doi.org/10.1017/CBO9780511760860.002.