# Closure of context-sensitive languages under inverse language substitution

We define language substitution for a Context-Sensitive Language (CSL) $$S$$ over an alphabet $$\Sigma$$ is a map from $$\Sigma$$ into CSL's, for example: $$f(abc) = L_1(a) L_2(b) L_3(c)$$ such that (I guess) the union of all $$L(s)$$ for $$s \in f(S)$$ is defined to be $$L(f(S))$$ and $$L(f(S))$$ is known to be a CSL itself.

That is my interpretation of language substitution for CSL's. Well languages are also closed under inverse of string homomorphisms, homomorphisms $$f$$ being a special case of language substitution in which each $$a \in \Sigma$$ gets mapped to a singleton language $$L_1(a) = \{f(a)\}$$.

So my question is simple, yet probably hard or interesting to prove. That is, are CSL's closed under inverse of language substitution? Wikipedia is silent on this topic.

Let $$f$$ be a language substitution taking $$S$$ to $$f(S)$$. Then $$f^{-1}(S) := \bigcup f^{-1}(s)$$ I'm assuming. Is that a CSL?

Fix a universal Turing machine $$T$$.
Let $$L_1$$ be the language of all sequences of configurations $$c_1 \# c_2 \# \cdots \# c_\ell$$ which describe a valid computation of $$T$$, starting with an arbitrary initial configuration $$c_1 \neq \epsilon$$, and ending with a halting state; we do not allow any further configurations to appear. This language is clearly context-sensitive (it can be accepted in linear space even deterministically).
Let $$L_2$$ be the language of all sequences of configurations $$c_1 \# c_1 \# c_2 \# \cdots \# c_\ell$$ such that $$c_1 \# c_2 \# \cdots \# c_\ell \in L_1$$ (notice the initial configuration is repeated twice). This language is also context-sensitive.
Define a function $$f$$ from $$\Sigma$$ to CSLs by $$f(\sigma) = \{ \sigma \}$$ for $$\sigma \neq \#$$ and $$f(\#) = \{ \#w : w \in L_1 \}$$.
Notice that $$f^{-1}(L_2)$$ consists of strings $$c_1\#$$, where $$c_1$$ is an initial configuration of $$T$$ on which $$T$$ eventually halts. Thus $$f^{-1}(L_2)$$ is not computable.
• It seems we can as well take $f(\#) = \{\#w \mid w\in C\}$ where $C$ is a (regular!) set of sequences of configurations, not necessarily forming a valid computation. I assume that the initial $c_1\#$ is over a different alphabet than $C$. Now again $f^{-1}(L_2)$ consists of strings $c_1\#$ for which there exists a valid computation, since $f$ must be able to assign a string in $L_2$. If correct, that would mean even inverse regular substitutions lead out of context-sensitive. Jun 3 at 19:55