# Time complexity of computing homomorphic image

The class of regular languages $$\textrm{REG}$$ is closed under inverse homomorphisms. The class $$\textrm{TIME}(n^k)$$ of languages solvable by a one-tape TM is also closed under inverse homomorphisms for $$k\geq 2$$: we can replace every input symbol $$a$$ by $$\phi(a)$$ using shifting the string, this takes time $$O(n^2)$$, and then run the TM for the language. I am wondering if one can compute homomorphic image in time $$o(n^2)$$ on a one-tape TM.

For example, let us consider some language in $$\textrm{TIME}(n\log n)$$, for instance $$L=\{0^n1^n : n\geq 0\}$$ or $$L=\{w\in\{0,1\}^{*} : |w|_0=|w|_1\}$$.

Question: Is $$\phi^{-1}(L)\in \textrm{TIME}(n\log n)$$ for all homomorphisms $$\phi$$?

This is true (for all reasonable functions, not just $$n\log n$$) if $$\phi$$ is $$\epsilon$$-free. You do not need to compute $$\phi(w)$$ explicitly, you just need to simulate a TM $$M$$ deciding $$L$$ on $$\phi(w)$$ using the original input $$w=w_0\dots w_{n-1}$$.
To do this, use a mixed-length encoding: let the $$i$$th cell of the tape represent $$k_i=|\phi(w_i)|$$ cells of the simulated tape (if $$i$$ is past the end of the original input, put e.g. $$k_i=1$$). Choose the representation of $$k$$-tuples of symbols of $$M$$ by symbols of the alphabet of the simulating machine such that a symbol $$a$$ of the input alphabet represents $$\phi(a)$$, so that the original input $$w$$ directly represents $$\phi(w)$$. The state of the simulating machine will record the state of the simulated machine $$M$$ and the simulated head position within the current $$k$$-tuple. In this way, each step of the computation of $$M$$ is simulated by one step of the simulating machine.
This does not work if $$\phi(a)=\epsilon$$ for some symbol $$a$$, because then a simulation of one step of $$M$$ may involve skipping over a long subword that maps to $$\epsilon$$, raising the overall time bound by a factor of $$n$$.
• If $\phi(a)=\epsilon$, you can simply remove the symbol $a$ from the input $w$ and apply your TM, isn't it? Apr 6 at 18:19
• Remove all occurrences of such symbols and shift everything to get rid of the holes. This is no easier than expanding the input when some $|\phi(a)|\ge2$, and likely requires quadratic time on a one-tape machine. Apr 6 at 18:24
• You are right. But still, if we just add a new letter at any place, it seems that the complexity of the language does not increase. If $w$ has length $n$ and contains $k$ letters $\neq a$, then your MT will take at most $f(k)n/k$, where $f(n)$ is the time complexity of $L$. Assuming $f(k)/k$ is increasing, this gives again f(n)n/n=f(n). Right? Apr 8 at 17:22
• No, there is no reason to assume that all the gaps have length about $n/k$. It may well be there is a handful of gaps of length $\Omega(n)$, and many gaps of small length. If it so happens that the algorithm spends most of the time crossing back and forth the long gaps, it will take time about $f(k)n$. Apr 8 at 17:43
• I suspect that $\mathrm{DTIME}_1(n\log n)$ is, in fact, not closed under $\phi^{-1}$ where $\phi(a)=\epsilon$. Although I do not know an explicit counterexample, I think it's too good to be true that every $L\in\mathrm{DTIME}_1(n\log n)$ would be computable by a one-tape TM that crosses each position only $O(\log n)$ times. If $L$ is a counterexample, then $\phi^{-1}(L)$ should require time $\omega(n\log n)$ on inputs where we insert $a^n$ at a position that requires $\omega(\log n)$ crossings. Apr 9 at 8:15