Застосування генетичних алгоритмів для уніфікації термів другого порядку з одномісними функціоналтьними символами
Loading...
Date
2014
Authors
Болгар, Ю.
Жежерун, Олександр
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Задача уніфікації другого порядку у загальному випадку є нерозв’язною, хоча для окремої лямбда-алгебри термів другого порядку із одномісними функціональними символами її розв’язність доведено. Стандартний алгоритм уніфікації термів другого порядку має експоненційну складність, а генетичний алгоритм із використанням спеціальних метрик як функцій пристосованості є альтернативним способом ефективного знаходження уніфікатора.
Description
Second-order unification problem is undecidable in general case, but the decidability has been proven for lambda-algebra of second-order terms with unary functional symbols. The standard algorithm of second-order unification has an exponential complexity, while genetic algorithm with the use of special
metrics as fitness function is an alternative and effective way of finding a unificator.
Keywords
лямбда-алгебра, уніфікація другого порядку, генетичний алгоритм, відстань Дамерау-Левенштейна, відстань Джаро-Уінклера, стаття, lambda-algebra, second-order unification, genetic algorithm, Damarau-Levenshtein distance, Jaro-Winkler distance
Citation
Болгар Ю. О. Застосування генетичних алгоритмів для уніфікації термів другого порядку з одномісними функціоналтьними символами / Болгар Ю. О., Жежерун О. П. // Наукові записки НаУКМА. - 2014. - Т. 163 : Комп'ютерні науки. - С. 19-24.