211
правок
Изменения
м
Нет описания правки
Опишем алгоритм для нахождения лексиграфически минимальной строки <tex>x</tex>, удовлетворяющей формулу <tex>\phi</tex>.
Пусть <tex>n=|\phi|, r=r(|\phi|)</tex>. Изначально область поиска для <tex>x</tex> это все строки длины <tex>n</tex>. Опишем одну итерацию поиска.
Разобьём множество на <tex>r+1</tex> подотрезок примерно равной длины. Обозначим концы полученных подотрезков <tex>w_0,...,w_{r+1}</tex>. Пусть теперь <tex>z_i=f(\langle\phi,w_i\rangle)</tex>.
