<h3>Definitions</h3>
<p>Let <span class="math-container">$G$</span> be a context free grammar over an alphabet <span class="math-container">$\Sigma$</span> with non-terminals <span class="math-container">$V$</span>.</p>
<ul>
<li>Define the locality <span class="math-container">$l(G)$</span> as the length of the longest word in <span class="math-container">$(V \cup \Sigma)^*$</span> that has a derivation tree in <span class="math-container">$G$</span> where no path contains the same non-terminal symbol twice. Since <span class="math-container">$V$</span> is finite, this number exists for every grammar <span class="math-container">$G$</span>.</li>
</ul>
<p>When a word in <span class="math-container">$L(G)$</span> that is longer than the locality of <span class="math-container">$G$</span> 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 <span class="math-container">$G$</span>. Such a word must have a loop, and extending this loop can only make the word so much longer.</p>
<ul>
<li><p>Define the locality <span class="math-container">$l(L)$</span> of a language <span class="math-container">$L$</span> as the smallest value <span class="math-container">$l(G)$</span> for any grammar <span class="math-container">$G$</span> with <span class="math-container">$L(G) = L$</span>, or <span class="math-container">$\infty$</span> if such a number does not exist. Clearly, a language is context free if and only if such a number exists.</p>
</li>
<li><p>For a language <span class="math-container">$L$</span> and <span class="math-container">$N \subseteq \mathbb{N} \ni 0$</span>, define <span class="math-container">$L^{\cap N} := \{ w \in L \; | \; |w| \in N \}$</span> as the set of words in <span class="math-container">$L$</span> whose lengths are in <span class="math-container">$N$</span>.</p>
</li>
<li><p>For a number <span class="math-container">$n$</span>, define <span class="math-container">$P_n := \{ w \in \Sigma^* \; | \; \forall v \in \Sigma^*: v^n \neq w \}$</span> as the set of words that are not the <span class="math-container">$n$</span>th power of another word.</p>
</li>
</ul>
<h3>Locality Upper Bound</h3>
<p>We can show that <span class="math-container">$P_n = \{ w \in \Sigma^* \; | \; |w| \not\in n\mathbb{N} \lor \exists i: w_i \neq w_{i+|w|/n}  \}$</span>.</p>
<p>With this insight, it is easy to show that <span class="math-container">$P_n$</span> is context free for all numbers <span class="math-container">$n$</span>. (Ensure that every word <span class="math-container">$w$</span> has the form <span class="math-container">$w = xaybz$</span> for different characters <span class="math-container">$a$</span> and <span class="math-container">$b$</span> and <span class="math-container">$(n - 1) \cdot |y| + (n - 2) = |xz|$</span>. To extend the word, add an arbitrary character to <span class="math-container">$y$</span> and <span class="math-container">$n - 1$</span> times many arbitrary characters to either <span class="math-container">$x$</span> or <span class="math-container">$z$</span>. This can easily be implemented as CFG)</p>
<p>The locality of this grammar is less than <span class="math-container">$2 \cdot n$</span>, which establishes an upper bound for <span class="math-container">$l(P_n)$</span>.</p>
<h3>Locality Lower Bound</h3>
<p>Because <span class="math-container">$0^k \in P_n$</span> for <span class="math-container">$k \not\in n\mathbb{N}$</span>, we can show that the locality of <span class="math-container">$P_n$</span> is at least <span class="math-container">$n$</span>, by pumping that word into <span class="math-container">$(\Sigma^*)^{\cap n\mathbb{N}}$</span> (<a href="https://cstheory.stackexchange.com/a/49187/34840">as described here</a>).
Unfortunately, this argument does not yield much insight and breaks for reasoning about the locality of <span class="math-container">$P_n \setminus (0^* | 1^*)$</span>.</p>
<h3>Open (?) Conjectures</h3>
<ol>
<li>Let <span class="math-container">$L$</span> be a language with <span class="math-container">$L^{\cap \{500\}} = P_5^{\cap \{500\}}$</span>. Then <span class="math-container">$l(L) \geq 5$</span>.</li>
</ol>
<p>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 <span class="math-container">$i$</span> such that <span class="math-container">$w_i \neq w_{i+100}$</span> (assuming the word-length is 500).
As <span class="math-container">$L$</span> could be finite, pumping arguments don't work directly.</p>
<ol start="2">
<li><span class="math-container">$l(P_n \setminus (0^* | 1^*)) \geq n$</span></li>
</ol>
<p>I believe this to be true and hope to find a more insightful argument than used for showing that <span class="math-container">$l(P_n) \geq n$</span>.</p>
<ol start="3">
<li>For a prime number <span class="math-container">$p$</span>, let <span class="math-container">$L$</span> be a language with <span class="math-container">$L^{\cap \{p^k \; | \;k \in \mathbb{N} \}} = P_p^{\cap \{p^k \; | \;k \in \mathbb{N} \}}$</span>. Then <span class="math-container">$l(L) \geq p$</span>.</li>
</ol>
<p>This conjecture would imply that the set of primitive words <span class="math-container">$Q$</span> has an infinite locality, i.e. is not context free, as <span class="math-container">$L$</span> in this conjecture can be instantiated with <span class="math-container">$Q$</span> for every <span class="math-container">$k$</span>.</p>
<hr />
<p>I consider this SE question answered when at least one of those conjectures has been proven or disproven, as they are all related.</p>

CC BY-SA 4.0
2023-01-24T12:17:54.497Z
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).
Marzio De Biasi
CC BY-SA 4.0
2023-01-25T13:07:20.047Z
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$
Henning
CC BY-SA 4.0
2023-01-25T21:10:46.547Z
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.
Marzio De Biasi
CC BY-SA 4.0
2023-01-26T08:34:40.680Z
I think it should be an intersection, not union, and I think this can be generalized for arbitrary prime factorization.
Henning
CC BY-SA 4.0
2023-01-26T09:52:02.313Z
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}$
Henning
CC BY-SA 4.0
2023-01-26T11:10:17.370Z
yes it's the intersection and it can be extended for arbitrary prime factorization ... nice!
Marzio De Biasi
<fl.formal-languages><context-free>
Context Free Grammar For Complement Of { wwwww | ... } With Minimal Locality?
Henning
# Context Free Grammar For Complement Of { wwwww | ... } With Minimal Locality?

(Asked by: username_0 on 2022-08-06)

### 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](https://cstheory.stackexchange.com/a/49187/34840)).
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.

2. $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$.

3. 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.

**Tags:** fl.formal-languages, context-free
> **Comments:**
> **username_1**: 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).  
> **username_0**: 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$  
> **username_1**: 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.  
> **username_0**: I think it should be an intersection, not union, and I think this can be generalized for arbitrary prime factorization.  
> **username_0**: 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}$  
> **username_1**: yes it's the intersection and it can be extended for arbitrary prime factorization ... nice!  

---

## 0 answers

