Closure of regular languages are closed under certain cut operations

Question

Let $f : \mathbb{N} \to \mathbb{N}$ be an integer function. For a language $L$, define

$$f(L) = \{w \mid \exists x : |x| = f(|w|) \text{ and } wx \in L\}$$

For example, if $f(n) = n$ this is just the "halving" operation, and regular languages are well known to be closed under this -- just simultaneously walk forwards and backwards (where the backwards walk tries all possible paths, like in the subset construction).

According to HMU, regular languages are also closed under taking the functions $2n, n^2, 2^n$. It is easy to see for $2n$, or any linear function for that matter - just walked backwards with whatever the speed. How can this be done for $n^2$ or $2^n$? It doesn't seem feasible to just increase the speed, since that would require remembering the number of steps taken so far.

Also, can we adapt the solution to get some general sufficient conditions on which $f$ has this property? (I doubt there are necessary and sufficient conditions, but would love to be proved wrong)

Answer 1

Take a DFA $\langle Q,q_0,F,\delta \rangle$ for $L$. For every state $q \in Q$, it is known that $$ N_q = \{ n : \delta(q,x) \in F \text{ for some $|x|=n$} \} $$ is an eventually periodic set. In these terms, we have $$ f(L) = \bigcup_{q \in Q} \{ w : \delta(q_0,w) = q \text{ and } |w|+f(|w|) \in N_q\}. $$ A few simple arguments show that $f$ is admissible (the set of regular languages is closed under $f$) if for every modulus $m$, there is a DFA $\langle Q',q'_0,\delta' \rangle$ over the alphabet $\{0\}$ which "computes" $|w|+f(|w|) \bmod m$, in the sense that on input $0^n$, you can recover $n+f(n) \bmod{m}$ from $\delta'(q'_0,0^n)$. This, in turn, happens if for every modulus $m$, the function mapping $n$ to $n+f(n) \bmod{m}$ is eventually periodic. Since $n \bmod{m}$ itself is periodic, we conclude that:

A function $f$ is admissible iff for all $m$, the function $\psi_{f,m}(n) = f(n) \bmod{m}$ is eventually periodic.

The Chinese Remainder Theorem shows that it suffices to consider values of $m$ which are prime powers.

All polynomials are clearly admissible: if $f$ is a polynomial, then $\psi_{f,m}$ has period $m$. Exponential functions $a^n$ are also admissible: if $m=p^k$, then either $p \mid a$, in which case $\psi_{f,m}$ is eventually zero, or $(p,a)=1$, in which case Euler's formula shows that $\psi_{f,m}$ has period $\varphi(m)$.

I'm not sure if the set of admissible functions can be characterized any further – this is an interesting research direction.