|
6
Поступила в редакцию 16.05.2018
Подписана в печать
05.06.2017
19 с.
/r2/pdf.jpg)
PDF |
А. Н.
Непейвода
Заметка об автоматическом решении квадратичных уравнений в словах
При анализе программ, оперирующих строками, естественным образом
возникает задача решения уравнений в словах. На практике часто
встречаются такие уравнения, содержащие, самое большее, два
вхождения каждой переменной, — так называемые квадратичные
уравнения. Для
их решения Ю.И. Хмелевским в 1971 году предложен интуитивно ясный
алгоритм, имеющий экспоненциальную сложность. В 1999 году В.
Дьекертом показано, что задача решения квадратичного уравнения
является NP-трудной.
В данной заметке изложены и показаны на примерах способы упрощения
классического алгоритма Хмелевского, позволяющие добиться лучшей его
применимости в автоматическом анализе программ.
Ключевые слова: суперкомпиляция, уравнения в словах, анализ
программ. |
/r1/pdf.jpg){kind=small}
.