Есть ли улучшения в алгоритме Даны Англюин для изучения регулярных наборов

В своей основополагающей работе 1987 года Дана Англуин представляет алгоритм полиномиального времени для изучения DFA из запросов членства и теоретических запросов (контрпримеры к предлагаемому DFA).

Она показывает, что если вы пытаетесь выучить минимальный DFA с состояниями, а ваш самый большой контрпример имеет длину , то вам нужно выполнить членских запросов и не более теоретических запросов.m O ( m n 2 ) n - $n$$m$$O(mn^2)$$n - 1$

Были ли значительные улучшения в количестве запросов, необходимых для изучения регулярного набора?

Ссылки и связанные вопросы

• Дана Англуин (1987) «Изучение регулярных множеств из запросов и контрпримеров», Infortmation and Computing 75: 87-106

• Нижние границы для обучения в запросе членства и модели контрпримеров

В своем ответе на cstheory.SE Лев Рейзин направил меня к тезису Роберта Шапира, который улучшает привязку к запросам на членство в разделе 5.4.5. Количество контрпримеров запросов остается неизменным. Алгоритм, который использует Schapire, отличается от того, что он делает после контрпримерного запроса.$O(n^2 + n\log m)$

Эскиз улучшения

На самом высоком уровне, Шапире заставляет из алгоритма Англуина иметь дополнительное условие, что для закрытых и каждого если то . Это гарантирует, что , а также делает консистенцию свойство алгоритма Angluin тривиальным удовлетворить. Чтобы обеспечить это, он должен по-разному обрабатывать результаты контрпримеров.( С , Е , Т ) с 1 , s 2 ∈ S s 1 ≠ с 2 г о ш ( с 1 ) ≠ г о ш ( с 2 ) | S | ≤ $(S,E,T)$$(S,E,T)$$s_1, s_2 \in S$$s_1 \neq s_2$$row(s_1) \neq row(s_2)$$|S| \leq n$

Учитывая контрпример , Angluin просто добавил и все префиксы к . Schapire делает что - то более тонкое путем вместо добавления одного элемента в . Этот новый сделает не закрытым в смысле Англуина, а обновление, чтобы получить замыкание, введет по крайней мере одну новую строку в , сохраняя при этом все строки различными. Условие на :z S e E e ( S , E , T ) S $z$$z$$S$$e$$E$$e$$(S,E,T)$$S$$e$

Где - выходная функция, - начальное состояние и правило обновления истинного «неизвестного» DFA. Другими словами, должен служить свидетелем, чтобы отличить будущее от .q 0 δ e s s ′$o$$q_0$$\delta$$e$$s$$s'a$

Чтобы выяснить это из мы выполняем двоичный поиск, чтобы выяснить подстроку такую ​​что итакое, что поведение нашей предполагаемой машины отличается в зависимости от одного входного символа. Более подробно, мы позволим быть строкой, соответствующей состоянию, достигнутому в нашей предполагаемой машине, после . Мы используем бинарный поиск (отсюда ), чтобы найти , для которого . Другими словами,z r i z = p i r i 0 ≤ | р я | = я < | z | s i p i log m k o ( δ ( q 0 , s k r k ) ) ≠ o ( δ ( q 0 , s k + 1 r k + 1 ) r $e$$z$$r_i$$z = p_ir_i$$0 \leq |p_i| = i < |z|$$s_i$$p_i$$\log m$$k$$o(\delta(q_0,s_kr_k)) \neq o(\delta(q_0,s_{k+1}r_{k+1})$ е$r_{k+1}$различает два государства наши машины высказал предположение находит эквивалентные и , таким образом , удовлетворяет условию на , поэтому мы добавим его в .$e$$E$

Я не знаю, актуален ли мой ответ. Недавно была описана реализация нового алгоритма под названием Observation Pack или, при некоторых обстоятельствах, дерева дискриминации Фалька Ховара. Этот алгоритм похож на L *, но использует Rivest-Shapire или другой метод (см. Steffen и Isberner) для разложения контрпримеров; и он использует структуру данных, дерево различения (двоичное дерево) для эффективного «просеивания», а именно вставки A-перехода (где A - каждый символ алфавита) нового состояния, найденного до тех пор, пока не будет закрытости , Этот алгоритм существует в двух версиях: OneGlobally и OneLocally в зависимости от того, добавлен ли суффикс, основанный в разложении, к каждому компоненту или нет (соотношение за алгоритмом состоит в том, что все префиксы в компоненте эквивалентны короткому префиксу и представляют одно и то же состояние в целевом объекте в соответствии с найденными суффиксами в это время. Позже с новым контрпримером будет найден новый суффикс, который различает как минимум 2 префикса одного и того же компонента. Это вызывает разделение этого компонента на два компонента). С OneLocally гораздо меньше запросов на членство, но количество запросов на эквивалентность может резко возрасти с большим целевым DFA. Скорее OneGlobally имеет количество запросов на членство всегда ниже, чем L * (но больше, чем OneLocally) и такое же количество запросов эквивалентностей, что и L * Позже с новым контрпримером будет найден новый суффикс, который различает как минимум 2 префикса одного и того же компонента. Это вызывает разделение этого компонента на два компонента). С OneLocally гораздо меньше запросов на членство, но количество запросов на эквивалентность может резко возрасти с большим целевым DFA. Скорее OneGlobally имеет количество запросов на членство всегда ниже, чем L * (но больше, чем OneLocally) и такое же количество запросов эквивалентностей, что и L * Позже с новым контрпримером будет найден новый суффикс, который различает как минимум 2 префикса одного и того же компонента. Это вызывает разделение этого компонента на два компонента). С OneLocally гораздо меньше запросов на членство, но количество запросов на эквивалентность может резко возрасти с большим целевым DFA. Скорее OneGlobally имеет количество запросов на членство всегда ниже, чем L * (но больше, чем OneLocally) и такое же количество запросов эквивалентностей, что и L *

Я знаю, что существует и другой алгоритм: алгоритм TTT, который лучше, чем Observation Pack, но я не очень хорошо его знаю. Алгоритм TTT должен быть современным