<p>This is true (for all reasonable functions, not just <span class="math-container">$n\log n$</span>) if <span class="math-container">$\phi$</span> is <em><span class="math-container">$\epsilon$</span>-free</em>. You do not need to compute <span class="math-container">$\phi(w)$</span> explicitly, you just need to simulate a TM <span class="math-container">$M$</span> deciding <span class="math-container">$L$</span> on <span class="math-container">$\phi(w)$</span> using the original input <span class="math-container">$w=w_0\dots w_{n-1}$</span>.</p>
<p>To do this, use a mixed-length encoding: let the <span class="math-container">$i$</span>th cell of the tape represent <span class="math-container">$k_i=|\phi(w_i)|$</span> cells of the simulated tape (if <span class="math-container">$i$</span> is past the end of the original input, put e.g. <span class="math-container">$k_i=1$</span>). Choose the representation of <span class="math-container">$k$</span>-tuples of symbols of <span class="math-container">$M$</span> by symbols of the alphabet of the simulating machine such that a symbol <span class="math-container">$a$</span> of the input alphabet represents <span class="math-container">$\phi(a)$</span>, so that the original input <span class="math-container">$w$</span> directly represents <span class="math-container">$\phi(w)$</span>. The state of the simulating machine will record the state of the simulated machine <span class="math-container">$M$</span> and the simulated head position within the current <span class="math-container">$k$</span>-tuple. In this way, each step of the computation of <span class="math-container">$M$</span> is simulated by one step of the simulating machine.</p>
<p>This does not work if <span class="math-container">$\phi(a)=\epsilon$</span> for some symbol <span class="math-container">$a$</span>, because then a simulation of one step of <span class="math-container">$M$</span> may involve skipping over a long subword that maps to <span class="math-container">$\epsilon$</span>, raising the overall time bound by a factor of <span class="math-container">$n$</span>.</p>

CC BY-SA 4.0
2023-04-06T18:19:39.830Z
If $\phi(a)=\epsilon$, you can simply remove the symbol $a$ from the input $w$ and apply your TM, isn't it?
QMath
CC BY-SA 4.0
2023-04-06T18:24:19.350Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-04-08T17:22:18.670Z
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?
QMath
CC BY-SA 4.0
2023-04-08T17:43:19.837Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2023-04-09T08:15:40.047Z
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.
Emil Jeřábek
CC BY-SA 4.0
2023-04-09T10:13:35.743Z
Let us consider $L=\{0^nww^{R}: w\in\{a,b\}^{*}, |w|\leq \log n\}$. Then $L\in\textrm{DTIME}_1(n\log n)$. But $0^nw1^nw^R$ should probably require $n(\log n)^2$ time, I guess.
QMath
CC BY-SA 4.0
2023-04-09T10:39:37.237Z
As far as I can see, this is in $\mathrm{DTIME}_1(n\log n)$. It can be verified by $\log n$ passes over the whole string, each of which deletes every other 0 and 1 (while checking their parity), the first nondeleted symbol of $w$, and the last nondeleted symbol of $w^R$.
Emil Jeřábek
CC BY-SA 4.0
2023-04-09T12:47:58.630Z
But if you change it to $\{0^nww^R:|w|\le(\log n)^2\}$, I think it should work.
Emil Jeřábek
CC BY-SA 4.0
2023-04-06T16:25:31.763Z
2023-04-06T16:25:31.763Z
Emil Jeřábek
<p>The class of regular languages <span class="math-container">$\textrm{REG}$</span> is closed under inverse homomorphisms. The class <span class="math-container">$\textrm{TIME}(n^k)$</span> of languages solvable by a one-tape TM is also closed under inverse homomorphisms for <span class="math-container">$k\geq 2$</span>: we can replace every input symbol <span class="math-container">$a$</span> by <span class="math-container">$\phi(a)$</span> using shifting the string, this takes time <span class="math-container">$O(n^2)$</span>, and then run the TM for the language. I am wondering if one can compute homomorphic image in time <span class="math-container">$o(n^2)$</span> on a one-tape TM.</p>
<p>For example, let us consider some language in <span class="math-container">$\textrm{TIME}(n\log n)$</span>, for instance <span class="math-container">$L=\{0^n1^n : n\geq 0\}$</span> or <span class="math-container">$L=\{w\in\{0,1\}^{*} : |w|_0=|w|_1\}$</span>.</p>
<p><strong>Question</strong>: Is <span class="math-container">$\phi^{-1}(L)\in \textrm{TIME}(n\log n)$</span> for all homomorphisms <span class="math-container">$\phi$</span>?</p>

<time-complexity><turing-machines><homomorphism>
Time complexity of computing homomorphic image
QMath
# Time complexity of computing homomorphic image

(Asked by: username_0 on 2023-04-05)

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$?

**Tags:** time-complexity, turing-machines, homomorphism


---

## 1 answers

### Answer by username_1 on 2023-04-06. Score: 1

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$.

> **Comments:**
> **username_0**: If $\phi(a)=\epsilon$, you can simply remove the symbol $a$ from the input $w$ and apply your TM, isn't it?  
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: 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$.  
> **username_1**: 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.  
> **username_0**: Let us consider $L=\{0^nww^{R}: w\in\{a,b\}^{*}, |w|\leq \log n\}$. Then $L\in\textrm{DTIME}_1(n\log n)$. But $0^nw1^nw^R$ should probably require $n(\log n)^2$ time, I guess.  
> **username_1**: As far as I can see, this is in $\mathrm{DTIME}_1(n\log n)$. It can be verified by $\log n$ passes over the whole string, each of which deletes every other 0 and 1 (while checking their parity), the first nondeleted symbol of $w$, and the last nondeleted symbol of $w^R$.  
> **username_1**: But if you change it to $\{0^nww^R:|w|\le(\log n)^2\}$, I think it should work.  

---

