Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally $\mid w_i\mid=n$ for all $i$, then set $w'\approx w$ if also $\mid w'_i\mid=n$ for all $i$ and there are permutations $\pi_1,\pi_2$ such that $w_i[j]=w'_{\pi_1(i)}[\pi_2(j)]$. $L$ is closed under $\sim$ and $\approx$.

For example, if $100\#0000\#$ is in $L$, so is $0000\#100\#$. If $100\#110\#$ is in $L$, so are $110\#100\#$, $010\#011\#$, $011\#010\#$, etc.

Additionally, set $w'\bowtie w$ if $w'\sim w$ and $\mid w_i\mid_1=\mid w'_{\pi_1(i)}\mid_1$ for all $i$ ($\mid \cdot\mid_1$ means ``number of 1's"). $L$ is not closed under $\bowtie$.

My question is: Are there context-free languages $L$ with these properties such that $L$ can not be written as a substitution $s(L_1)$ where $s(a)=L_a\#$ for some $L_1$ and $L_a$? Is it true that such an $L$ is context-free if and only if it is a substitution? I think this in fact equivalent to the conjecture that if $L$ is closed under $\sim$ and $\approx$ and context-free, then it is in fact closed under $\bowtie$. (The intuition being: how else could the permutation invariance be enforced context-freely unless a side effect of $\bowtie$-closure?).

I have been trying to think about this in terms of matching relations ([1]). The idea is that a language is context-free if and only if for every string there is a matching (non-crossing pairing relation) and a first-order sentence that they together satisfy (so this sentence basically says that the arcs of the matching correspond to productions).

If $L$ can be written as a substitution, every string will have matching where $\#$'s are paired and the symbols of every $w_i$ are paired up with symbols in the same $w_i$. I'm trying to show that if there are arcs that cross over a $\#$, (which means there are productions that generate symbols in distinct subwords), then there is a contradiction with the invariance properties.

[1] Lautemann, Clemens, Thomas Schwentick, and Denis Thérien. "Logics for context-free languages." Computer science logic. Springer Berlin Heidelberg, 1995.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.