Унификација (информатика)
У логици и рачунарству, посебно аутоматизованом закључивању, унификација је алгоритамски процес решавања једначина између симболичких израза, сваки у облику Лева страна = Десна страна. На пример, користећи x,y,з као променљиве и узимајући ф као неинтерпретирану функцију, скуп једноструких једначина { ф(1,y) = ф(x,2) } је синтаксички проблем обједињавања првог реда који има замену { x ↦ 1, y ↦ 2 } као њено једино решење.
Конвенције се разликују по томе које вредности могу да имају променљиве и који изрази се сматрају еквивалентним. У синтаксичком обједињавању првог реда, променљиве су у опсегу чланова првог реда, а еквивалентност је синтаксичка. Ова верзија обједињавања има јединствени „најбољи“ одговор и користи се у логичком програмирању и имплементацији типских система програмског језика, посебно у Хиндли–Милнеровим алгоритмима за типско закључивање. У обједињавању вишег реда, могуће ограниченом на обједињавање патерна вишег реда, термини могу укључивати ламбда изразе, а еквивалентност је до нивоа бета редукције. Ова верзија се користи у помоћницима за проверу и логичком програмирању вишег реда, на пример Исабелле, Тwелф, и ламбдаПролог. Коначно, у семантичком обједињавању или Е-унификацији, једнакост је подложна основном знању и променљиве се крећу у различитим доменима. Ова верзија се користи у СМТ решавачима, алгоритмима за замену чланова и анализи криптографских протокола.
Формална дефиниција
уредиПроблем уједињења је коначан скуп Е={ л1 ≐ р1, ..., лн ≐ рн } једначина које треба решити, где су ли, ри у скупу чланова или израза. У зависности од тога који изрази или чланови су дозвољени у скупу једначина или проблему обједињавања, и који се изрази сматрају једнаким, разликује се неколико оквира унификације. Ако су променљиве вишег реда, односно променљиве које представљају функције, дозвољене у изразу, процес се назива обједињавање вишег реда, иначе се ради о обједињавању првог реда. Ако је потребно решење да обе стране сваке једначине буду дословно једнаке, процес се назива синтаксичко или слободно уједињење, иначе семантичко или једначинско уједињење, или Е-унификација, или теорија унификације по модулу.
Ако је десна страна сваке једначине затворена (нема слободних променљивих), проблем се назива подударање (патерна). Лева страна (са променљивима) сваке једначине се назива патерн.[1]
Референце
уреди- ^ Доwек, Гиллес (1. 1. 2001). „Хигхер-ордер унифицатион анд матцхинг”. Хандбоок оф аутоматед реасонинг. Елсевиер Сциенце Публисхерс Б. V. стр. 1009—1062. ИСБН 978-0-444-50812-6. Архивирано из оригинала 15. 5. 2019. г. Приступљено 15. 5. 2019.
Литература
уреди- Франз Баадер анд Wаyне Снyдер (2001). "Унифицатион Тхеорy". Ин Јохн Алан Робинсон анд Андреи Воронков, едиторс, Хандбоок оф Аутоматед Реасонинг, волуме I, пагес 447–533. Елсевиер Сциенце Публисхерс.
- Гиллес Доwек (2001). "Хигхер-ордер Унифицатион анд Матцхинг" Архивирано 2019-05-15 на сајту Wayback Machine. In Handbook of Automated Reasoning.
- Franz Baader and Tobias Nipkow (1998). Term Rewriting and All That. Cambridge University Press.
- Franz Baader and de (1993). "Unification Theory". In Handbook of Logic in Artificial Intelligence and Logic Programming.
- Jean-Pierre Jouannaud and Claude Kirchner (1991). "Solving Equations in Abstract Algebras: A Rule-Based Survey of Unification". In Computational Logic: Essays in Honor of Alan Robinson.
- Nachum Dershowitz and Jean-Pierre Jouannaud, Rewrite Systems, in: Jan van Leeuwen (ed.), Handbook of Theoretical Computer Science, volume B Formal Models and Semantics, Elsevier, 1990, pp. 243–320
- Jörg H. Siekmann . Claude Kirchner (editor), ур. (1990). „Unification Theory”. Unification. Academic Press..
- Kevin Knight (март 1989). „Unification: A Multidisciplinary Survey” (PDF). ACM Computing Surveys. 21 (1): 93—124. CiteSeerX 10.1.1.64.8967
. S2CID 14619034. doi:10.1145/62029.62030. - Gérard Huet and Derek C. Oppen (1980). "Equations and Rewrite Rules: A Survey". Technical report. Stanford University.
- Raulefs, Peter; Siekmann, Jörg; Szabó, P.; Unvericht, E. (1979). „A short survey on the state of the art in matching and unification problems”. ACM SIGSAM Bulletin. 13 (2): 14—20. S2CID 17033087. doi:10.1145/1089208.1089210.
- Claude Kirchner and Hélène Kirchner. Rewriting, Solving, Proving. In preparation.
