# Parametrization of context-sensitive language in polynomial time

Let $$\Sigma$$ be a finite alphabet. Let $$L\subset \Sigma^*$$ be a context-sensitive language containing a word of every length.

Can we always find $$f:\Sigma^*\to L$$ computable in polynomial time in length and such that $$f(\Sigma^*)$$ is infinite?

• How would you certify for the input that $L$ indeed contains a word of every length? Jul 6, 2021 at 12:21
• Every nonempty recursively enumerable language $L$ is the image of a polynomial-time function $f\colon\Sigma^*\to L$. Jul 6, 2021 at 17:08
• @EmilJeřábek Do you have a more detailed argument? Jul 7, 2021 at 5:27
• @Gamow I don't have an example right now but it probably should be possible to give a constructive proof with performance worse than polynomial Jul 7, 2021 at 5:36
• Fix $x_0\in L$, and a TM $M$ such that $M(x)$ halts iff $x\in L$. Define $f(w)$ as $x$ if $w$ is a sequence of configurations encoding a halting run of $M$ on an input $x$, and as $x_0$ if $w$ is not such a sequence. Jul 7, 2021 at 7:58