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

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



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.