Suppose, $A$ is a finite alphabet. $L \subset A^*$ is a language. Let's call $L$ concatenation-free iff $\forall u, v \in L$ we have $uv \notin L$.

Does there exist some function $c: \mathbb{N} \to (0; 1)$, such that for any finite language $L \subset A^*$, there exists a concatenation-free sublanguage $L_0 \subset L$, such that $|L_0| \geq c(|A|)|L|$?

The only thing I currently know about this problem, is that we can take $c(1) = \frac{1}{3}$. That is a direct consequence of Erdos-Sidon theorem, that states:

$\forall A \subset \mathbb{Z}$ $\exists$ a sum-free $A_0 \subset A$, such that $|A_0| \geq \frac{|A|}{3}$

However, I do not know how to deal with $|A| \geq 2$.


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.