<p>Let <span class="math-container">$\Sigma$</span> be a finite alphabet. Let <span class="math-container">$L\subset \Sigma^*$</span> be a context-sensitive language containing a word of every length.</p>
<p>Can we always find <span class="math-container">$f:\Sigma^*\to L$</span> computable in polynomial time in length and such that <span class="math-container">$f(\Sigma^*)$</span> is infinite?</p>

CC BY-SA 4.0
2021-07-06T12:21:14.640Z
How would you certify for the input that $L$ indeed contains a word of every length?
Gamow
CC BY-SA 4.0
2021-07-06T17:08:46.953Z
Every nonempty recursively enumerable language $L$ is the image of a polynomial-time function $f\colon\Sigma^*\to L$.
Emil Jeřábek
CC BY-SA 4.0
2021-07-07T05:27:13.077Z
@EmilJeřábek Do you have a more detailed argument?
deryll
CC BY-SA 4.0
2021-07-07T05:36:22.220Z
@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
deryll
CC BY-SA 4.0
2021-07-07T07:58:49.393Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-07-07T11:21:45.730Z
@EmilJeřábek If there is several such $x$ you take the shortest one? And the time complexity is at most quadratic right?
deryll
CC BY-SA 4.0
2021-07-07T11:29:40.383Z
There can be only one $x$: the first configuration of the run of $M$ has $x$ on the input tape. Quadratic will do, but you can implement it even in linear time (on a multi-tape Turing machine).
Emil Jeřábek
<cc.complexity-theory><ds.algorithms><fl.formal-languages>
Parametrization of context-sensitive language in polynomial time
deryll
# Parametrization of context-sensitive language in polynomial time

(Asked by: username_0 on 2021-07-06)

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?

**Tags:** cc.complexity-theory, ds.algorithms, fl.formal-languages

> **Comments:**
> **username_1**: How would you certify for the input that $L$ indeed contains a word of every length?  
> **username_2**: Every nonempty recursively enumerable language $L$ is the image of a polynomial-time function $f\colon\Sigma^*\to L$.  
> **username_0**: @EmilJeřábek Do you have a more detailed argument?  
> **username_0**: @username_1 I don't have an example right now but it probably should be possible to give a constructive proof with performance worse than polynomial  
> **username_2**: 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.  
> **username_0**: @EmilJeřábek If there is several such $x$ you take the shortest one? And the time complexity is at most quadratic right?  
> **username_2**: There can be only one $x$: the first configuration of the run of $M$ has $x$ on the input tape. Quadratic will do, but you can implement it even in linear time (on a multi-tape Turing machine).  

---

## 0 answers

