6
$\begingroup$

Definitions

Let $G$ be a context free grammar over an alphabet $\Sigma$ with non-terminals $V$.

  • Define the locality $l(G)$ as the length of the longest word in $(V \cup \Sigma)^*$ that has a derivation tree in $G$ where no path contains the same non-terminal symbol twice. Since $V$ is finite, this number exists for every grammar $G$.

When a word in $L(G)$ that is longer than the locality of $G$ is pumped according to the pumping lemma for context free languages, there exists a pumped word that is not longer than the sum of the length of the previous word and the locality of $G$. Such a word must have a loop, and extending this loop can only make the word so much longer.

  • Define the locality $l(L)$ of a language $L$ as the smallest value $l(G)$ for any grammar $G$ with $L(G) = L$, or $\infty$ if such a number does not exist. Clearly, a language is context free if and only if such a number exists.

  • For a language $L$ and $N \subseteq \mathbb{N} \ni 0$, define $L^{\cap N} := \{ w \in L \; | \; |w| \in N \}$ as the set of words in $L$ whose lengths are in $N$.

  • For a number $n$, define $P_n := \{ w \in \Sigma^* \; | \; \forall v \in \Sigma^*: v^n \neq w \}$ as the set of words that are not the $n$th power of another word.

Locality Upper Bound

We can show that $P_n = \{ w \in \Sigma^* \; | \; |w| \not\in n\mathbb{N} \lor \exists i: w_i \neq w_{i+|w|/n} \}$.

With this insight, it is easy to show that $P_n$ is context free for all numbers $n$. (Ensure that every word $w$ has the form $w = xaybz$ for different characters $a$ and $b$ and $(n - 1) \cdot |y| + (n - 2) = |xz|$. To extend the word, add an arbitrary character to $y$ and $n - 1$ times many arbitrary characters to either $x$ or $z$. This can easily be implemented as CFG)

The locality of this grammar is less than $2 \cdot n$, which establishes an upper bound for $l(P_n)$.

Locality Lower Bound

Because $0^k \in P_n$ for $k \not\in n\mathbb{N}$, we can show that the locality of $P_n$ is at least $n$, by pumping that word into $(\Sigma^*)^{\cap n\mathbb{N}}$ (as described here). Unfortunately, this argument does not yield much insight and breaks for reasoning about the locality of $P_n \setminus (0^* | 1^*)$.

Open (?) Conjectures

  1. Let $L$ be a language with $L^{\cap \{500\}} = P_5^{\cap \{500\}}$. Then $l(L) \geq 5$.

I would find it equally interesting to see a proof or a counter-example of this very concrete conjecture. Intuitively it feels impossible that a grammar with a locality of 4 or less can check if there exists a position $i$ such that $w_i \neq w_{i+100}$ (assuming the word-length is 500). As $L$ could be finite, pumping arguments don't work directly.

  1. $l(P_n \setminus (0^* | 1^*)) \geq n$

I believe this to be true and hope to find a more insightful argument than used for showing that $l(P_n) \geq n$.

  1. For a prime number $p$, let $L$ be a language with $L^{\cap \{p^k \; | \;k \in \mathbb{N} \}} = P_p^{\cap \{p^k \; | \;k \in \mathbb{N} \}}$. Then $l(L) \geq p$.

This conjecture would imply that the set of primitive words $Q$ has an infinite locality, i.e. is not context free, as $L$ in this conjecture can be instantiated with $Q$ for every $k$.


I consider this SE question answered when at least one of those conjectures has been proven or disproven, as they are all related.

$\endgroup$
6
  • $\begingroup$ Note that proving 1. is not so easy because the set of primitive words $Q$ is such that: $\forall p,q \text{ primes } Q^{\cap pq}=P_p^{\cap pq}$ . So a "generic" technique for 1. would probably suffice to prove that Q is not CF (which is a long-standing open question). $\endgroup$ Jan 24, 2023 at 12:17
  • $\begingroup$ I think 1. is a much easier question. If I'm not mistaken, there are only finitely many languages with $l(L) < 5$ and theoretically all these cases could be checked by a computer. Also, your equality is incorrect, otherwise $P_p^{\cap pq} = P_q^{\cap pq}$, which is not the case for $p \neq q$ $\endgroup$
    – Henning
    Jan 25, 2023 at 13:07
  • 1
    $\begingroup$ yes you're right, they are not equal, $\forall p,q \text{ primes } Q^{\cap pq}=P_p^{\cap pq} \cup P_q^{\cap pq}$. There are finitely many languages with $l(L) < 5$ and you can check them one by one, but perhaps a more general technique could be applied to the primitive words problem. I'll think more about it. $\endgroup$ Jan 25, 2023 at 21:10
  • $\begingroup$ I think it should be an intersection, not union, and I think this can be generalized for arbitrary prime factorization. $\endgroup$
    – Henning
    Jan 26, 2023 at 8:34
  • 1
    $\begingroup$ I believe it is $Q^{\cap p_1^{v_1} \cdot ... \cdot ... p_n^{v_n} =: k} = P_{p_1}^k \cap ... \cap P^k_{p_n}$ $\endgroup$
    – Henning
    Jan 26, 2023 at 9:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.