2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ If $\phi(a)=\epsilon$, you can simply remove the symbol $a$ from the input $w$ and apply your TM, isn't it? $\endgroup$
    – QMath
    Apr 6 at 18:19
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Apr 6 at 18:24
  • $\begingroup$ 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? $\endgroup$
    – QMath
    Apr 8 at 17:22
  • $\begingroup$ 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$. $\endgroup$
    – Emil Jeřábek
    Apr 8 at 17:43
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Apr 9 at 8:15

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.