Языки, которые мы не можем (не) доказать, что не зависят от контекста

21

Я ищу языки, которые "вероятно, не являются контекстно-свободными", но мы не можем (не) доказать это, используя известные стандартные методы.

Есть недавний опрос на предмет или открытый проблемный раздел от недавней конференции?

Вероятно, не так много языков, которые не известны как CF, поэтому, если вы знаете один, вы также можете опубликовать его в качестве ответа.

Примеры, которые я нашел:

Примечание : как показал Арье в своем ответе, вы можете построить целый класс таких языков, если «связать» язык с неизвестной гипотезой о (не) конечности или (не) пустоте некоторых множеств (например, LграммоLdбaсчасзнак равно{12N|2N не может быть выражено как сумма двух простых чисел } ). Я не совсем заинтересован в таких примерах.

Марцио де Биаси
источник
1
Для вашего второго примера я написал статью из моего ответа, который находится на рассмотрении (и первый отзыв был положительным): arxiv.org/abs/1901.03913
domotorp
Есть много вариантов первого примера, которые, как известно, не являются контекстно-независимыми, я не знаю, хотите ли вы включить их в качестве отдельных примеров; см. главу 10 связанной книги (теория Касоньи-Кацура).
Домоторп
@domotorp: я только что посмотрел (я все еще читаю главу 2) ... они кажутся мне более техническими попытками решить главную проблему.
Марцио Де Биаси

Ответы:

14

Другим хорошим дополнением является дополнение множества S смежных подслов (или «факторов») последовательности Туэ-Морса Tзнак равно0110100110010110 . Чтобы дать некоторый контекст, Жан Berstel доказал , что дополнение множества T из префиксов от слова Туэ- Морзе является контекстно-свободной (и на самом деле что - то более общее , чем это). Но соответствующий результат для подслов все еще открыт.

Джеффри Шаллит
источник
Большое спасибо! Если вы видели, что это где-то указано (возможно, в одной из ваших многочисленных статей о последовательности Туэ-Морса? ;-), вы можете добавить ссылку (даже если она указана в форме повторного морфизма).
Марцио де Биаси
12

Как насчет языка LTп двойных простых чисел? Т.е. все пары натуральных чисел (п,п') (представленные, скажем, в унарном виде), такие, что п,п' и простые, и п'знак равноп+2 ? Если гипотеза двойных простых чисел верна, то LTп не является контекстно-свободной; в противном случае это конечно.

Редактировать: Позвольте мне дать быстрый набросок доказательства того, что гипотеза двойных простых чисел подразумевает, что LTп не является контекстно-свободным. Свяжите с любым языком L его последовательность длины 0a1a2... , где целое число появляется в последовательности, если в L есть слово длины . Следствием леммы накачки является то, что для L, которые являются регулярными или CFL, последовательность длины удовлетворяет свойству ограниченных разностей: существует R > 0 такое, что a n +LLр>0aN+1-aNрдля всехN. В теории чисел легко и хорошо известно, что простые числа не имеют ограниченных различий. Наконец, любая бесконечная подпоследовательность последовательности, нарушающая само свойство ограниченных разностей, должна ее нарушать.

Арье
источник
3
Хорошо, спасибо! Но меня не очень интересуют языки, которые связаны с неизвестными предположениями о (не) конечности некоторых множеств. Кстати, если эти предположения верны, результирующий язык также является регулярным :-)
Марцио Де Биаси
Если бесконечно много простых чисел-близнецов, как вы видите, что регулярно? LTп
Арье
1
Если бесконечно много простых чисел-близнецов, как показать, что не является контекстно-свободным? LTп
Эмиль Йержабек поддерживает Монику
1
Ой, простите, я не заметил, что вы представляете числа в одинарных. Тогда понятно. (Я считаю, что доказательство этого для двоичного представления потребовало бы значительного прогресса в гипотезе о двойных простых числах.)
Эмиль Йержабек поддерживает Монику
5
Напротив, Эмиль, «стандартное» доказательство того, что простые числа в двоичном коде не являются свободными от контекста, легко достаточно, чтобы доказать, что каждое бесконечное множество простых чисел не является свободным от контекста. Так что если бесконечно много простых чисел-близнецов, результат будет немедленным.
Джеффри Шаллит