7
$\begingroup$

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)

$\endgroup$
3
  • 2
    $\begingroup$ What is "HMU"? A certain textbook? $\endgroup$ Mar 1, 2017 at 17:19
  • $\begingroup$ Please state the question in your title. $\endgroup$ Mar 1, 2017 at 17:29
  • $\begingroup$ @YuvalFilmus. Presumably Hopcroft, Motwani, Ullman, Introduction to Automata Theory . . . $\endgroup$ Mar 1, 2017 at 18:39

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Your "admissible" functions are what Dexter Kozen calls "regularity-preserving". (I got the hint from the "talk" page of wikipedia.) I think he gives a characterization of these functions, in terms of mappings that preserve ultimately periodic sets. This seems to match your approach. His note is originally published in the Bulletin of the EATCS, at that time not online. But is easy to find at his site (for now). $\endgroup$ Mar 1, 2017 at 23:08
  • $\begingroup$ @HendrikJan Kozen has an extra condition that I seem to have missed, C4(ii). My condition is only C4(i). Perhaps C4(ii) appears when doing all the proofs carefully. In any case, C4(ii) is not needed if $f$ is monotone. $\endgroup$ Mar 2, 2017 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.