Проблема с разделением слов
В теоретической информатике проблема разделения слов — это проблема поиска наименьшего детерминированного конечного автомата , который ведет себя по-разному с двумя заданными строками , то есть принимает одну из двух строк и отклоняет другую строку. остается открытым Вопрос о том, насколько большим должен быть такой автомат в худшем случае в зависимости от длины входных строк, .
Пример
[ редактировать ]Две строки 0010 и 1000 можно отличить друг от друга по автомату с тремя состояниями, в котором переходы из начального состояния переходят в два разных состояния, оба из которых являются терминальными в том смысле, что последующие переходы из этих двух состояний всегда возвращаются в то же самое состояние. Состояние этого автомата записывает первый символ входной строки. Если одно из двух терминальных состояний принимает, а другое отклоняет, то автомат примет только одну из строк 0010 и 1000. Однако эти две строки не может различить ни один автомат с менее чем тремя состояниями. [1]
Упрощение предположений
[ редактировать ]Для доказательства границ этой проблемы можно без ограничения общности предположить, что входные данные представляют собой строки двухбуквенного алфавита. Ведь если две строки в большем алфавите различаются, то существует гомоморфизм строк , который отображает их в двоичные строки одинаковой длины, которые также различаются. Любой автомат, распознающий двоичные строки, можно перевести в автомат, распознающий исходные строки, без увеличения числа состояний. [1]
Также можно предположить, что две строки имеют одинаковую длину. Для строк неравной длины всегда существует простое число p , значение которого является логарифмическим по меньшей из двух входных длин, так что две длины различны по модулю p . автомат, который подсчитывает длину своего входного сигнала по модулю p В этом случае для того, чтобы отличить две строки друг от друга, можно использовать . Поэтому строки неравной длины всегда можно отличить друг от друга автоматами с малым числом состояний. [1]
История и границы
[ редактировать ]Проблема ограничения размера автомата, различающего две заданные строки, была впервые сформулирована Горальчиком и Коубеком (1986) , которые показали, что размер автомата всегда сублинейен. [2] Позже Робсон (1989) доказал лучшую известную верхнюю оценку O ( n 2/5 (журнал n ) 3/5 ) , от размера автомата, который может потребоваться. [3] Это было улучшено Чейзом (2020) до O ( n 1/3 (журнал n ) 7 ) . [4] [5]
Существуют пары входных данных, которые представляют собой двоичные строки длины n , для которых любой автомат, различающий входные данные, должен иметь размер Ω(log n ) . Устранение разрыва между этой нижней границей и верхней границей Чейза остается открытой проблемой. Джеффри Шалит предложил приз в размере 100 британских фунтов за любое улучшение верхней границы Робсона. [6]
Особые случаи
[ редактировать ]Известно, что несколько особых случаев проблемы разделения слов можно решить с использованием нескольких состояний:
- Если два двоичных слова имеют разное количество нулей или единиц, то их можно отличить друг от друга, подсчитав их веса Хэмминга по модулю простого числа логарифмического размера, используя логарифмическое количество состояний. В более общем смысле, если образец длины k встречается в двух словах разное количество раз, их можно отличить друг от друга с помощью O ( k log n ) . состояний [1]
- Если два двоичных слова отличаются друг от друга в пределах своих первых или последних k позиций, их можно отличить друг от друга с помощью k + O (1) состояний. Это означает, что почти все пары бинарных слов можно отличить друг от друга с помощью логарифмического числа состояний, поскольку только полиномиально малая часть пар не имеет различий в своих начальных O (log n ) . позициях [1]
- Если два двоичных слова имеют расстояние Хэмминга d , то существует простое число p с p = O ( d log n ) и позиция i , в которой две строки различаются, так что i не равно по модулю p положению любой другой разности. . Вычисляя четность входных символов в позициях, соответствующих i по модулю p , можно различать слова, используя автомат с O ( d log n ) . состояниями [1]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д и ж Демейн, Эрик Д .; Эйзенштат, Сара; Шалит, Джеффри ; Уилсон, Дэвид А. (2011), «Замечания о разделении слов», « Описательная сложность формальных систем: 13-й международный семинар», DCFS 2011, Гиссен/Лимбург, Германия, 25–27 июля 2011 г., Труды , конспекты лекций по информатике, том. 6808, Гейдельберг: Springer-Verlag, стр. 147–157, arXiv : 1103.4513 , doi : 10.1007/978-3-642-22600-7_12 , MR 2910373 , S2CID 6959459 .
- ^ Горальчик, П.; Коубек, В. (1986), «О распознавании слов автоматами», Автоматы, языки и программирование: 13-й международный коллоквиум, Ренн, Франция, 15–19 июля 1986 г., Труды , конспекты лекций по информатике, том. 226, Берлин: Springer-Verlag, стр. 116–122, doi : 10.1007/3-540-16761-7_61 , MR 0864674 .
- ^ Робсон, Дж. М. (1989), «Разделение строк с помощью небольших автоматов», Information Processing Letters , 30 (4): 209–214, doi : 10.1016/0020-0190(89)90215-9 , MR 0986823 .
- ^ Чейз, З. (2020), «Новая верхняя граница разделения слов», arXiv : 2007.12097 [ math.CO ] .
- ^ Чейз, Закари (15 июня 2021 г.). «Разделение слов и реконструкция следов» . Материалы 53-го ежегодного симпозиума ACM SIGACT по теории вычислений . STOC 2021. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники: 21–31. дои : 10.1145/3406325.3451118 . ISBN 978-1-4503-8053-9 .
- ^ Шалит, Джеффри (2014), «Открытые проблемы теории автоматов: идиосинкразический взгляд», Британский коллоквиум по теоретической информатике (BCTCS 2014), Университет Лафборо (PDF) .