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

  • 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$
0

0

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.