Проблема разделения слов - Separating words problem

Вопрос, Web Fundamentals.svgНерешенная проблема в информатике:
Сколько состояний нужно в детерминированный конечный автомат который ведет себя по-разному на двух заданных струны длины п?
(больше нерешенных проблем в информатике)

В теоретическая информатика, то проблема разделения слов проблема поиска наименьшего детерминированный конечный автомат который ведет себя по-разному на двух заданных струны, что означает, что он принимает одну из двух строк и отклоняет другую. Это открытая проблема насколько большим должен быть такой автомат в худшем случае в зависимости от длины входных строк.

Пример

Две строки 0010 и 1000 могут отличаться друг от друга автоматом с тремя состояниями, в котором переходы из начального состояния переходят в два разных состояния, оба из которых являются конечными в том смысле, что последующие переходы из этих двух состояний всегда возвращаются в такое же состояние. Состояние этого автомата записывает первый символ входной строки. Если одно из двух конечных состояний принимает, а другое отвергает, то автомат примет только одну из строк 0010 и 1000. Однако эти две строки не может различить ни один автомат с менее чем тремя состояниями.[1]

Упрощение предположений

Для доказательства границ этой проблемы можно без ограничения общности предположить, что входными данными являются строки в двухбуквенном алфавите. Ведь если две строки в большем алфавите различаются, то существует гомоморфизм струн который отображает их в двоичные строки одинаковой длины, которые также различаются. Любой автомат, который различает двоичные строки, может быть преобразован в автомат, который различает исходные строки, без увеличения количества состояний.[1]

Также можно предположить, что две строки имеют одинаковую длину. Для строк неравной длины всегда существует простое число п значение которой является логарифмическим от меньшего из двух входных значений длины, так что эти две длины различаются по модулю п. Автомат, который считает длину своего входа по модулю п в этом случае можно использовать, чтобы отличить две строки друг от друга. Следовательно, цепочки неравной длины всегда можно отличить друг от друга автоматами с несколькими состояниями.[1]

История и границы

Проблема ограничения размера автомата, различающего две заданные строки, была впервые сформулирована Горалчик и Коубек (1986), который показал, что размер автомата всегда сублинейен.[2] Потом, Робсон (1989) доказала лучшую известную верхнюю границу, О(п2/5(бревноп)3/5), от размера автомата, который может потребоваться.[3] Это было улучшено Чейз (2020) к О(п1/3(бревноп)7).[4]

Существуют пары входных данных, которые представляют собой двоичные строки длины п для которого любой автомат, различающий входы, должен иметь размер Ω (журнал п). Устранение разрыва между этой нижней границей и верхней границей Робсона остается открытой проблемой.[1] Джеффри Шаллит предложил приз в размере 100 британских фунтов за любое улучшение верхней границы Робсона.[5]

Особые случаи

Известно, что несколько частных случаев проблемы разделяющих слов разрешимы с использованием нескольких состояний:

  • Если два двоичных слова имеют разное количество нулей или единиц, то их можно отличить друг от друга, посчитав их Веса Хэмминга по модулю простого числа логарифмического размера с использованием логарифмического числа состояний. В более общем смысле, если образец длины k встречается в двух словах разное количество раз, их можно отличить друг от друга с помощью О(k бревно п) состояния.[1]
  • Если два двоичных слова отличаются друг от друга в пределах их первого или последнего k позиции, их можно отличить друг от друга с помощью k + О(1) состояния. Отсюда следует, что почти все пары двоичных слов можно отличить друг от друга с помощью логарифмического числа состояний, потому что только полиномиально малая часть пар не различается в своих начальных О(бревно п) позиции.[1]
  • Если два двоичных слова имеют Расстояние Хэмминга d, то существует простое число п с п = О(d бревно п) и должность я на котором две строки различаются, так что я не равно по модулю п на позицию любой другой разницы. Вычислив паритет входных символов в позициях конгруэнтных я по модулю п, можно различать слова с помощью автомата с О(d бревно п) состояния.[1]

Рекомендации

  1. ^ а б c d е ж грамм Демейн, Эрик Д.; Айзенстат, Сара; Шаллит, Джеффри; Уилсон, Дэвид А. (2011), «Замечания о разделении слов», Описание сложности формальных систем: 13-й международный семинар, DCFS 2011, Гиссен / Лимбург, Германия, 25-27 июля 2011 г., Труды, Конспект лекций по информатике, 6808, Heidelberg: Springer-Verlag, стр. 147–157, arXiv:1103.4513, Дои:10.1007/978-3-642-22600-7_12, МИСТЕР  2910373, S2CID  6959459.
  2. ^ Goralčík, P .; Кубек, В. (1986), «О распознавании слов автоматами», Автоматы, языки и программирование: 13-й международный коллоквиум, Ренн, Франция, 15–19 июля 1986 г., Труды, Конспект лекций по информатике, 226, Берлин: Springer-Verlag, стр. 116–122, Дои:10.1007/3-540-16761-7_61, МИСТЕР  0864674.
  3. ^ Робсон, Дж. М. (1989), "Разделение строк с помощью небольших автоматов", Письма об обработке информации, 30 (4): 209–214, Дои:10.1016/0020-0190(89)90215-9, МИСТЕР  0986823.
  4. ^ Чейз, З. (2020), «Новая верхняя граница для разделения слов», arXiv:2007.12097 [math.CO ].
  5. ^ Шаллит, Джеффри (2014), "Открытые проблемы в теории автоматов: индивидуальный взгляд", Британский коллоквиум теоретической информатики (BCTCS 2014), Университет Лафборо (PDF).