Idiomas que não podemos (des) provar ser livres de contexto

21

Estou procurando idiomas que "provavelmente não são livres de contexto", mas não podemos (des) provar isso usando técnicas padrão conhecidas.

Existe uma pesquisa recente sobre o assunto ou uma seção de problemas abertos de uma conferência recente?

Provavelmente, não existem muitos idiomas que não são conhecidos por CF, portanto, se você conhece um, também pode publicá-lo como resposta.

Os exemplos que encontrei são:

Nota : como mostrado por Aryeh em sua resposta, você pode construir toda uma classe de tais idiomas se "vincular" um idioma a uma conjectura desconhecida sobre a (não) finitude ou (não) vazio de alguns conjuntos (por exemplo, LGoldbach={12n2n não pode ser expresso como uma soma de dois números primos } ). Não estou muito interessado nesses exemplos.

Marzio De Biasi
fonte
11
Para o seu segundo exemplo, escrevi um artigo da minha resposta que está em revisão (e o primeiro feedback foi positivo): arxiv.org/abs/1901.03913
domotorp
Existem muitas variantes do primeiro exemplo que não são conhecidas por serem livres de contexto; não sei se você deseja incluí-las como exemplos separados; veja o capítulo 10 do livro vinculado (Teoria Kászonyi-Katsura).
domotorp 7/04
@domotorp: Acabei de dar uma olhada (ainda estou lendo o capítulo 2) ... eles me parecem tentativas mais técnicas de atacar o problema principal.
Marzio De Biasi

Respostas:

14

Outra boa é o complemento do conjunto S de subpalavras contíguas (também conhecidas como "fatores") da sequência de Thue-Morse t=0110100110010110 . Para dar algum contexto, Jean Berstel provou que o complemento do conjunto T de prefixos da palavra Thue-Morse é livre de contexto (e na verdade algo mais geral que isso). Mas o resultado correspondente para subpalavras ainda está aberto.

Jeffrey Shallit
fonte
Ótimo, obrigado! Se você o viu declarado em algum lugar (talvez em um de seus muitos trabalhos sobre a sequência Thue-Morse? ;-), você pode adicionar a referência (mesmo que declarada no formulário de morfismo iterado).
Marzio De Biasi
12

E a linguagem LTP dos primos gêmeos? Ou seja, todos os pares de números naturais (p,p) (representados, digamos, em unários), de modo que p,p sejam primos e p=p+2 ? Se a conjectura de primos gêmeos for verdadeira, então LTP não é livre de contexto; caso contrário, é finito.

Edit: Deixe-me dar um esboço de prova rápida de que a conjectura dos primos gêmeos implica que LTP não seja livre de contexto. Associado a qualquer linguagem L sua seqüência de comprimento 0a1a2 , onde o inteiro aparece na sequência sse há uma palavra de comprimento em L . É uma conseqüência do (s) lema (s) de bombeamento que, para L regulares ou CFL, a sequência de comprimento satisfaz a propriedade de diferenças limitadas: existe um R>0 tal que an+1anRpara todos osn. É um fato fácil e bem conhecido na teoria dos números que os primos não têm diferenças limitadas. Finalmente, qualquer subsequência infinita de uma sequência que viole a propriedade de diferenças limitadas em si deve violá-la.

Aryeh
fonte
3
Bom obrigado! Mas não estou muito interessado em linguagens vinculadas a conjecturas desconhecidas sobre a (não) finitude de alguns conjuntos. BTW, se essas conjecturas são verdadeiras, a linguagem resultante também é regular :-)
Marzio De Biasi
Se existem infinitos números primos gêmeos, como você vê que é regular? LTP
Aryeh
11
Se houver infinitos primos gêmeos, como você mostra que não é livre de contexto? LTP
Emil Jeřábek apoia Monica em 5/04
11
Oh, desculpe, eu não notei que você representa os números em unário. Então está claro. (Acredito que provar isso para representação binária exigiria um progresso considerável na conjectura de primos gêmeos.)
Emil Jeřábek apoia Monica em
5
Pelo contrário, Emil, a prova "padrão" de que os primos binários não são livres de contexto é suficiente para provar que todo conjunto infinito de primos não é livre de contexto. Portanto, se houver infinitos primos gêmeos, o resultado será imediato.
Jeffrey Shallit 05/04