Langues que nous ne pouvons pas (dé) prouver comme étant sans contexte

Je recherche des langages qui ne sont "probablement pas sans contexte" mais nous ne sommes pas en mesure de le (dé) prouver en utilisant des techniques standard connues.

Y a-t-il une enquête récente sur le sujet ou une section de problème ouvert d'une conférence récente?

Il n'y a probablement pas beaucoup de langues qui ne sont pas connues pour être CF, donc si vous en connaissez une, vous pouvez également la poster comme réponse.

Les exemples que j'ai trouvés sont:

le langage bien connu des mots primitifs $Q = \{ w \mid w \neq u^i (|u| > 1) \}$ (il y a tout un beau livre récent à ce sujet: les langages sans contexte et les mots primitifs )
les représentations Base-k du co-domaine d'un polynôme (voir question " Représentations Base-k du co-domaine d'un polynôme - est-il hors contexte? " sur cstheory, qui a peut-être été résolu par domotorp, voir son préimpression )

Remarque : comme l'a montré Aryeh dans sa réponse, vous pouvez créer toute une classe de ces langues si vous "liez" une langue à une conjecture inconnue sur la (non) finitude ou la (non) vacuité de certains ensembles (par exemple $L_{Goldbach} = \{ 1^{2n} \mid 2n$ ne peut pas être exprimé comme une somme de deux nombres premiers $\}$ ). Je ne suis pas tout à fait intéressé par de tels exemples.

reference-request big-list context-free Marzio De Biasi
la source

Pour votre deuxième exemple, j'ai écrit un article de ma réponse qui est en cours de révision (et les premiers commentaires étaient positifs): arxiv.org/abs/1901.03913

domotorp

Il existe de nombreuses variantes du premier exemple qui ne sont pas connues comme étant sans contexte, je ne sais pas si vous voulez les inclure comme exemples séparés; voir le chapitre 10 du livre lié (théorie de Kászonyi-Katsura).

domotorp

@domotorp: Je viens de lui donner un coup d'oeil (je lis toujours le chapitre 2) ... ils me semblent des tentatives plus techniques pour attaquer le problème principal.

Marzio De Biasi

Réponses:

Un autre bon est le complément de l'ensemble $S$ de sous-mots contigus (aka "facteurs") de la séquence de Thue-Morse ${\bf t} = 0110100110010110 \cdots$ . Pour donner un peu de contexte, Jean Berstel a prouvé que le complément de l'ensemble $T$ des préfixes du mot Thue-Morse est hors contexte (et en fait quelque chose de plus général que cela). Mais le résultat correspondant pour les sous-mots est toujours ouvert.

Jeffrey Shallit
la source

Grand merci! Si vous l'avez vu indiqué quelque part (peut-être dans l'un de vos nombreux articles sur la séquence Thue-Morse? ;-) vous pouvez ajouter la référence (même si elle est indiquée dans la forme de morphisme itéré).

Marzio De Biasi

$L_{TP}$ $(p,p')$ $p,p'$ $p'=p+2$ $L_{TP}$

$L_{TP}$ $L$ $0\le a_1\le a_2\le\ldots$ $\ell$ $\ell$ $L$ $L$ $R>0$ $a_{n+1}-a_n\le R$ $n$

Aryeh
la source

Bien, merci! Mais je ne suis pas très intéressé par les langages liés à des conjectures inconnues sur la (non) finitude de certains ensembles. BTW si ces conjectures sont vraies, la langue résultante est également régulière :-)

Marzio De Biasi

L_{T P}

$L_{TP}$

L_{T P}

$L_{TP}$

Oh, désolé, je n'ai pas remarqué que vous représentiez les chiffres à l'unaire. Alors c'est clair. (Je crois que prouver cela pour la représentation binaire nécessiterait un progrès considérable sur la conjecture des nombres premiers jumeaux.)

Emil Jeřábek soutient Monica le

Au contraire, Emil, la preuve "standard" que les nombres premiers en binaire ne sont pas sans contexte suffit à prouver que tout ensemble infini de nombres premiers n'est pas sans contexte. Donc, s'il y a une infinité de nombres premiers jumeaux, le résultat est immédiat.

Jeffrey Shallit