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

21

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:

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 LGoldbach={12n2n ne peut pas être exprimé comme une somme de deux nombres premiers } ). Je ne suis pas tout à fait intéressé par de tels exemples.

Marzio De Biasi
la source
1
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:

14

Un autre bon est le complément de l'ensemble S de sous-mots contigus (aka "facteurs") de la séquence de Thue-Morse t=0110100110010110 . 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
12

LTP(p,p)p,pp=p+2LTP

LTPL 0a1a2LLR>0an+1anRn

Aryeh
la source
3
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
LTP
1
LTP
1
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
5
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