Sprachen, die wir nicht als kontextfrei (dis) beweisen können

Ich suche nach Sprachen, die "wahrscheinlich nicht kontextfrei" sind, aber wir können sie mit bekannten Standardtechniken nicht (dis) beweisen.

Gibt es eine aktuelle Umfrage zu diesem Thema oder einen offenen Problembereich einer aktuellen Konferenz?

Wahrscheinlich gibt es nicht viele Sprachen, von denen nicht bekannt ist, dass sie CF sind. Wenn Sie eine Sprache kennen, können Sie sie auch als Antwort posten.

Die Beispiele, die ich gefunden habe, sind:

• die bekannte Sprache der primitiven Wörter (es gibt ein ganz schönes aktuelles Buch darüber: Kontextfreie Sprachen und primitive Wörter )$Q = \{ w \mid w \neq u^i (|u| > 1) \}$
• die Base-k-Darstellungen der Co-Domäne eines Polynoms (siehe Frage " Base-k-Darstellungen der Co-Domäne eines Polynoms - ist es kontextfrei? ") auf cstheory, die vielleicht durch domotorp gelöst wurde, siehe seine Preprint )

Hinweis : Wie Aryeh in seiner Antwort gezeigt hat, können Sie eine ganze Klasse solcher Sprachen aufbauen, wenn Sie eine Sprache mit einer unbekannten Vermutung über die (Nicht-) Endlichkeit oder (Nicht-) Leere einiger Mengen "verknüpfen" (z. B. kann nicht als Summe zweier Primzahlen ausgedrückt werden ). Solche Beispiele interessieren mich nicht so sehr.$L_{Goldbach} = \{ 1^{2n} \mid 2n$$\}$

Ein weiteres gutes ist das Komplement der Menge $S$ zusammenhängender Unterwörter (auch "Faktoren" genannt) der Thue-Morse-Folge ${\bf t} = 0110100110010110 \cdots$ . Um einige Kontext zu geben, erwies sich Jean Berstel , dass das Komplement der Menge $T$ von Präfixen des Thue-Morse Wort ist kontextfrei (und tatsächlich etwas allgemeiner als das). Das entsprechende Ergebnis für Unterwörter ist jedoch noch offen.

Wie wäre es mit der Sprache $L_{TP}$ der Doppelprimzahlen? Das heißt, alle Paare natürlicher Zahlen $(p,p')$ (beispielsweise unär dargestellt), so dass $p,p'$ beide Primzahlen sind und $p'=p+2$ ? Wenn die Vermutung der doppelten Primzahlen wahr ist, dann ist $L_{TP}$ nicht kontextfrei; sonst ist es endlich.

Edit: Lassen Sie mich kurz skizzieren, dass die Vermutung der Doppelprimzahlen impliziert, dass $L_{TP}$ nicht kontextfrei ist. Ordnen Sie jeder Sprache $L$ ihre Längenfolge $0\le a_1\le a_2\le\ldots$ , wobei die ganze Zahl $\ell$ in der Folge erscheint, wenn es in L ein Wort der Länge $\ell$ . Es ist eine Konsequenz des (der) Pump-Lemma (s), dass für L , die regulär oder CFL sind, die Längensequenz die Eigenschaft der begrenzten Differenzen erfüllt: Es gibt ein R > 0, so dass ein n +$L$$L$$R>0$$a_{n+1}-a_n\le R$für alle$n$. Es ist eine einfache und bekannte Tatsache in der Zahlentheorie, dass die Primzahlen keine begrenzten Unterschiede aufweisen. Schließlich muss jede unendliche Folge einer Sequenz, die die Eigenschaft der begrenzten Unterschiede selbst verletzt, diese verletzen.