3
$\begingroup$

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.

$\endgroup$

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.