Anti-unifikace (počítačová věda) - Anti-unification (computer science) - Wikipedia

Anti-sjednocení je proces konstrukce generalizace společné pro dva dané symbolické výrazy. Jako v unifikace, rozlišuje se několik rámců podle toho, které výrazy (nazývané také termíny) jsou povoleny a které výrazy jsou považovány za rovnocenné. Pokud jsou ve výrazu povoleny proměnné představující funkce, proces se nazývá „anti-unifikace vyššího řádu“, jinak „anti-unifikace prvního řádu“. Pokud je nutné zobecnění, aby instance měla doslova stejnou hodnotu jako každý vstupní výraz, proces se nazývá „syntaktická anti-unifikace“, jinak „E-anti-unifikace“ nebo „anti-unifikace modulo theory“.

Algoritmus proti sjednocení by měl pro dané výrazy vypočítat úplnou a minimální generalizační sadu, tj. Sadu pokrývající všechny zobecnění a neobsahující žádné nadbytečné členy. V závislosti na rámci může mít úplná a minimální generalizační sada jednoho, konečně mnoho nebo možná nekonečně mnoho členů, nebo nemusí vůbec existovat;^{[poznámka 1]} nemůže být prázdná, protože v každém případě existuje triviální zobecnění. Pro syntaktickou anti-unifikaci prvního řádu, Gordon Plotkin^[1][2] poskytl algoritmus, který počítá úplnou a minimální sadu zobecnění ojedinělých obsahující takzvanou „nejméně obecnou zobecnění“ (lgg).

Proti sjednocení by se nemělo zaměňovat un-unification. To druhé znamená proces řešení systémů nerovnice, tj. hledání hodnot proměnných tak, aby byly splněny všechny dané nerovnice.^{[poznámka 2]} Tento úkol se zcela liší od hledání zobecnění.

Předpoklady

Formálně předpokládá přístup proti sjednocení

• Nekonečná sada PROTI z proměnné. Pro anti-sjednocení vyššího řádu je vhodné zvolit PROTI disjunkt ze sady lambda-term vázané proměnné.
• Sada T z podmínky takhle PROTI ⊆ T. Pro anti-sjednocení prvního řádu a vyššího řádu, T je obvykle soubor podmínky prvního řádu (výrazy vytvořené z variabilních a funkčních symbolů) a lambda podmínky (termíny obsahující některé proměnné vyššího řádu).
• An vztah ekvivalence ${ displaystyle equiv}$ na ${ displaystyle T}$, označující, které výrazy jsou považovány za rovnocenné. Obvykle pro anti-sjednocení vyššího řádu ${ displaystyle t equiv u}$ -li ${ displaystyle t}$ a ${ displaystyle u}$ jsou alfa ekvivalent. Pro E-anti-sjednocení prvního řádu, ${ displaystyle equiv}$ odráží základní znalosti o určitých funkčních symbolech; například pokud ${ displaystyle oplus}$ je považován za komutativní ${ displaystyle t equiv u}$ -li ${ displaystyle u}$ výsledky z ${ displaystyle t}$ záměnou argumentů ${ displaystyle oplus}$ při některých (možná všech) událostech.^{[Poznámka 3]} Pokud vůbec žádné znalosti na pozadí neexistují, pak pouze doslovně nebo syntakticky jsou stejné pojmy považovány za rovnocenné.

Termín prvního řádu

Vzhledem k sadě ${ displaystyle V}$ variabilních symbolů, sada ${ displaystyle C}$ konstantních symbolů a množin ${ displaystyle F_ {n}}$ z ${ displaystyle n}$-ary funkční symboly, nazývané také operátorské symboly, pro každé přirozené číslo ${ displaystyle n geq 1}$, sada termínů (netříděného prvního řádu) ${ displaystyle T}$ je rekurzivně definované být nejmenší sada s následujícími vlastnostmi:^[3]

• každý variabilní symbol je pojem: PROTI ⊆ T,
• každý konstantní symbol je pojem: C ⊆ T,
• od každého n podmínky t₁,…,t_na všechny n- symbol funkční funkce F ∈ F_n, větší termín ${ displaystyle f (t_ {1}, ldots, t_ {n})}$ lze postavit.

Například pokud X ∈ PROTI je variabilní symbol, 1 ∈ C je konstantní symbol a přidejte ∈ F₂ je tedy symbol binární funkce X ∈ T, 1 ∈ T, a (tedy) přidat (X,1) ∈ T podle pravidla pro první, druhý a třetí termín. Druhý termín se obvykle píše jako X+1, použití Infixová notace a pro větší pohodlí běžnější symbol operátora +.

Termín vyššího řádu

Střídání

A substituce je mapování ${ displaystyle sigma: V longrightarrow T}$ od proměnných k pojmům; zápis ${ displaystyle {x_ {1} mapsto t_ {1}, ldots, x_ {k} mapsto t_ {k} }}$ označuje substituci mapující každou proměnnou ${ displaystyle x_ {i}}$ k termínu ${ displaystyle t_ {i}}$, pro ${ displaystyle i = 1, ldots, k}$a každá další proměnná sama o sobě. Použití této substituce na výraz t je psáno v postfixové notaci jako ${ displaystyle t {x_ {1} mapsto t_ {1}, ldots, x_ {k} mapsto t_ {k} }}$; znamená to (současně) nahradit každý výskyt každé proměnné ${ displaystyle x_ {i}}$ v termínu t podle ${ displaystyle t_ {i}}$. Výsledek tσ uplatnění náhrady σ na termín t se nazývá instance tohoto termínu t.Jako příklad prvního řádu, použití substituce ${ displaystyle {x mapsto h (a, y), z mapsto b }}$ k termínu

F(	X	, A, G(	z	), y)	výnosy
F(	h(A,y)	, A, G(	b	), y)	.

Zobecnění, specializace

Pokud termín ${ displaystyle t}$ má instanci ekvivalentní pojmu ${ displaystyle u}$, tedy pokud ${ displaystyle t sigma equiv u}$ pro nějaké střídání ${ displaystyle sigma}$, pak ${ displaystyle t}$ je nazýván obecnější než ${ displaystyle u}$, a ${ displaystyle u}$ je nazýván zvláštnější než, nebo zahrnut podle, ${ displaystyle t}$. Například, ${ displaystyle x oplus a}$ je obecnější než ${ displaystyle a oplus b}$ -li ${ displaystyle oplus}$ je komutativní, od té doby ${ displaystyle (x oplus a) {x mapsto b } = b oplus a equiv a oplus b}$.

Li ${ displaystyle equiv}$ je doslovná (syntaktická) identita termínů, termín může být obecnější i zvláštnější než jiný, pouze pokud se oba termíny liší pouze názvy proměnných, nikoli syntaktickou strukturou; takové termíny se nazývají variantynebo přejmenování navzájem. Například ${ displaystyle f (x_ {1}, a, g (z_ {1}), y_ {1})}$ je varianta ${ displaystyle f (x_ {2}, a, g (z_ {2}), y_ {2})}$, od té doby ${ displaystyle f (x_ {1}, a, g (z_ {1}), y_ {1}) {x_ {1} mapsto x_ {2}, y_ {1} mapsto y_ {2}, z_ {1} mapsto z_ {2} } = f (x_ {2}, a, g (z_ {2}), y_ {2})}$ a ${ displaystyle f (x_ {2}, a, g (z_ {2}), y_ {2}) {x_ {2} mapsto x_ {1}, y_ {2} mapsto y_ {1}, z_ {2} mapsto z_ {1} } = f (x_ {1}, a, g (z_ {1}), y_ {1})}$.Nicméně, ${ displaystyle f (x_ {1}, a, g (z_ {1}), y_ {1})}$ je ne varianta ${ displaystyle f (x_ {2}, a, g (x_ {2}), x_ {2})}$, protože žádná substituce nemůže transformovat druhý termín na ten první ${ displaystyle {x_ {1} mapsto x_ {2}, z_ {1} mapsto x_ {2}, y_ {1} mapsto x_ {2} }}$ dosáhne obráceného směru. Druhý termín je tedy řádně zvláštnější než ten první.

Střídání ${ displaystyle sigma}$ je zvláštnější než, nebo zahrnut nahrazením ${ displaystyle tau}$ -li ${ displaystyle x sigma}$ je zvláštnější než ${ displaystyle x tau}$ pro každou proměnnou ${ displaystyle x}$.Například, ${ displaystyle {x mapsto f (u), y mapsto f (f (u)) }}$ je zvláštnější než ${ displaystyle {x mapsto z, y mapsto f (z) }}$, od té doby ${ displaystyle f (u)}$ a ${ displaystyle f (f (u))}$ je zvláštnější než ${ displaystyle z}$ a ${ displaystyle f (z)}$, resp.

Anti-unification problem, generalizace set

An problém proti sjednocení je pár ${ displaystyle langle t_ {1}, t_ {2} rangle}$ termínů. Termín ${ displaystyle t}$ je běžné zobecněnínebo anti-unifikátor, z ${ displaystyle t_ {1}}$ a ${ displaystyle t_ {2}}$ -li ${ displaystyle t sigma _ {1} equiv t_ {1}}$ a ${ displaystyle t sigma _ {2} equiv t_ {2}}$ pro některé substituce ${ displaystyle sigma _ {1}, sigma _ {2}}$Pro daný problém proti sjednocení sada ${ displaystyle S}$ volá se anti-unifikátor kompletní pokud každá generalizace zahrnuje nějaký termín ${ displaystyle t v S}$; sada ${ displaystyle S}$ je nazýván minimální pokud žádný z jejích členů neobjedná jiného.

Syntaktická anti-sjednocení prvního řádu

Rámec syntaktické anti-sjednocení prvního řádu je založen na ${ displaystyle T}$ je soubor podmínky prvního řádu (přes nějakou danou sadu ${ displaystyle V}$ proměnných, ${ displaystyle C}$ konstant a ${ displaystyle F_ {n}}$ z ${ displaystyle n}$-ary funkční symboly) a dále ${ displaystyle equiv}$ bytost syntaktická rovnostV tomto rámci každý problém proti sjednocení ${ displaystyle langle t_ {1}, t_ {2} rangle}$ má kompletní a samozřejmě minimální jedináček sada řešení ${ displaystyle {t }}$. Jeho člen ${ displaystyle t}$ se nazývá nejméně obecné zobecnění (lgg) problému má syntakticky stejnou instanci ${ displaystyle t_ {1}}$ a další syntakticky rovna ${ displaystyle t_ {2}}$Jakékoli společné zobecnění ${ displaystyle t_ {1}}$ a ${ displaystyle t_ {2}}$ subsumy ${ displaystyle t}$.Gg je jedinečný až do variant: if ${ displaystyle S_ {1}}$ a ${ displaystyle S_ {2}}$ jsou tedy úplné i minimální sady řešení stejného syntaktického problému proti sjednocení ${ displaystyle S_ {1} = {s_ {1} }}$ a ${ displaystyle S_ {2} = {s_ {2} }}$ pro některé termíny ${ displaystyle s_ {1}}$ a ${ displaystyle s_ {2}}$, to jsou přejmenování navzájem.

Plotkin^[1][2] dal algoritmus pro výpočet lgg dvou daných termínů. Předpokládá injektivní mapování ${ displaystyle phi: T krát T longrightarrow V}$, tj. mapování přiřazující každý pár ${ displaystyle s, t}$ termínů vlastní proměnná ${ displaystyle phi (s, t)}$, takže žádné dva páry nesdílejí stejnou proměnnou.^{[poznámka 4]}Algoritmus se skládá ze dvou pravidel:

${ displaystyle f (s_ {1}, tečky, s_ {n}) sqcup f (t_ {1}, ldots, t_ {n})}$	${ displaystyle rightsquigarrow}$	${ displaystyle f (s_ {1} sqcup t_ {1}, ldots, s_ {n} sqcup t_ {n})}$
${ displaystyle s sqcup t}$	${ displaystyle rightsquigarrow}$	${ displaystyle phi (s, t)}$	pokud předchozí pravidlo neplatí

Například, ${ Displaystyle (0 * 0) sqcup (4 * 4) rightsquigarrow (0 sqcup 4) * (0 sqcup 4) rightsquigarrow phi (0,4) * phi (0,4) rightquigarrow x *X}$; toto nejméně obecné zobecnění odráží společnou vlastnost obou vstupů bytí čtvercových čísel.

Plotkin použil svůj algoritmus k výpočtu „relativní nejméně obecná generalizace (rlgg) "ze dvou sad klauzí v logice prvního řádu, která byla základem Golem přístup k induktivní logické programování.

Teorie anti-sjednocení prvního řádu prvního řádu

Tato sekce potřebuje expanzi s: vysvětlete hlavní výsledky z níže uvedených článků, vztahujte se k sobě navzájem. Můžete pomoci přidávat k tomu. (Červen 2020)

• Jacobsen, Erik (červen 1991), Sjednocení a anti-sjednocení (PDF), Technická zpráva
• Østvold, Bjarte M. (duben 2004), Funkční rekonstrukce anti-sjednocení (PDF), NR Note, DART / 04/04, Norské výpočetní středisko
• Boytcheva, Svetla; Markov, Zdravko (2002). „Algoritmus pro vyvolání nejméně generalizace pod relativní implikací“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)
• Kutsia, Temur; Levy, Jordi; Villaret, Mateu (2014). „Anti-Unification for Unranked Terms and Hedges“ (PDF). Journal of Automated Reasoning. 52 (2): 155–190. doi:10.1007 / s10817-013-9285-6. Software.

Rovnicové teorie

• Jedna asociativní a komutativní operace: Pottier, Loic (únor 1989), Algoritmy des dokončení a generalizace en logic du premier ordre; Pottier, Loic (1989), Generalizace de termes en theorie equationelle - Cas associatif-commutatifZpráva INRIA, 1056, INRIA
• Komutativní teorie: Baader, Franz (1991). „Unification, Weak Unification, Upper Bound, Lower Bound, and Generisation Problémy“. Proc. 4. konf. o technikách a aplikacích přepisování (RTA). LNCS. 488. Springer. str. 86–91.
• Zdarma monoidy: Biere, A. (1993), Normalisierung, Unifikation und Antiunifikation in Freien Monoiden (PDF), Univ. Karlsruhe, Německo
• Pravidelné třídy shody: Heinz, Birgit (prosinec 1995), Anti-Unifikation modulo Gleichungstheorie und deren Anwendung zur LemmagenerierungGMD Berichte, 261, TU Berlín, ISBN  978-3-486-23873-0; Burghardt, Jochen (2005). „E-generalizace pomocí gramatik“. Umělá inteligence. 165 (1): 1–35. arXiv:1403.8118. doi:10.1016 / j.artint.2005.01.008.
• Teorie A-, C-, AC-, ACU s uspořádanými druhy: Alpuente, Maria; Escobar, Santiago; Espert, Javier; Meseguer, Jose (2014). „Modulární algoritmus ekvalizační generalizace seřazený podle pořadí“ (PDF). Informace a výpočet. 235: 98–136. doi:10.1016 / j.ic.2014.01.006. hdl:2142/25871.
• Čistě idempontentní teorie: Černá, David; Kutsia, Temur (2019). „Idempotentní anti-sjednocení“. Transakce ACM ve výpočetní logice. 21 (2). hdl:10.1145/3359060.

Tříděná anti-sjednocení prvního řádu

• Taxonomické druhy: Frisch, Alan M .; Page, David (1990). "Zobecnění s taxonomickými informacemi". AAAI: 755–761.; Frisch, Alan M .; Page Jr., C. David (1991). „Zobecnění atomů v logice omezení“. Proc. Konf. o reprezentaci znalostí.; Frisch, A.M .; Page, C.D. (1995). "Vytváření teorií do instance". V Mellish, CS (ed.). Proc. 14. IJCAI. Morgan Kaufmann. s. 1210–1216.
• Podmínky funkce: Plaza, E. (1995). „Případy jako pojmy: Hlavní pojmový přístup ke strukturovanému znázornění případů“. Proc. 1. mezinárodní konference o uvažování na základě případů (ICCBR). LNCS. 1010. Springer. 265–276. ISSN  0302-9743.
• Idestam-Almquist, Peter (červen 1993). "Zobecnění pod implikací rekurzivní anti-unifikace". Proc. 10. konf. na strojovém učení. Morgan Kaufmann. 151–158.
• Fischer, Cornelia (květen 1994), PAntUDE - Algoritmus proti sjednocení pro vyjádření rafinovaných generalizací, Výzkumná zpráva, TM-94-04, DFKI
• Teorie A-, C-, AC-, ACU s uspořádanými druhy: viz výše

Nominální anti-sjednocení

• Baumgartner, Alexander; Kutsia, Temur; Levy, Jordi; Villaret, Mateu (červen 2013). Nominální anti-sjednocení. Proc. RTA 2015. Sv. 36 z LIPIcs. Schloss Dagstuhl, 57-73. Software.

Aplikace

• Analýza programu: Bulychev, Peter; Minea, Marius (2008). „Detekce duplicitních kódů pomocí Anti-Unification“. Citovat deník vyžaduje | deník = (Pomoc); Bulychev, Peter E .; Kostylev, Egor V .; Zakharov, Vladimir A. (2009). "Algoritmy proti sjednocení a jejich aplikace v programové analýze". Citovat deník vyžaduje | deník = (Pomoc)
• Factoring kódu: Cottrell, Rylan (září 2008), Poloautomatizace opětovného použití zdrojového kódu malého rozsahu prostřednictvím strukturální korespondence (PDF), Univ. Calgary
• Indukce indukce: Heinz, Birgit (1994), Lemma Discovery Anti-Unification of Regular Sorts, Technická zpráva, 94-21, TU Berlin
• Extrakce informací: Thomas, Bernd (1999). „Učení T-Wrapperů pro extrakci informací založené na sjednocení“ (PDF). Technická zpráva AAAI. WS-99-11: 15–20.
• Zdůvodnění podle případu: Armengol, Eva; Plaza, Enric (2005). „Použití symbolických popisů k vysvětlení podobnosti u CBR“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)
• Syntéza programu: Myšlenku zobecnění pojmů s ohledem na teorii rovnice lze vysledovat zpět k Manně a Waldingerovi (1978, 1980), kteří ji chtěli použít při syntéze programů. V části „Zobecnění“ navrhují (na str. 119 článku z roku 1980) zobecnit zvrátit(l) a zvrátit(ocas(l))<>[hlava(l)] získat reverzní (l ') <> m' . Toto zobecnění je možné pouze v případě rovnice pozadí u<>[]=u je považován.

Zohar Manna; Richard Waldinger (Prosinec 1978). Deduktivní přístup k syntéze programu (PDF) (Technická poznámka). SRI International. - předtisk článku z roku 1980

Zohar Manna a Richard Waldinger (leden 1980). „Deduktivní přístup k syntéze programu“. Transakce ACM v programovacích jazycích a systémech. 2: 90–121. doi:10.1145/357084.357090.

Anti-unifikace stromů a jazykové aplikace

• Analyzovat stromy protože věty mohou podléhat nejméně obecné generalizaci, aby se odvodilo maximální společné subparse stromy pro studium jazyků. Existují aplikace ve vyhledávání a klasifikaci textu.^[4]
• Analyzovat houštiny pro odstavce, protože grafy mohou podléhat nejméně obecné generalizaci.^[5]
• Provoz generalizace dojíždí s operací přechodu ze syntaktické (syntaktické stromy) na sémantickou (symbolické výrazy) úrovně. Ten pak může být předmětem konvenční anti-sjednocení.^[6][7]

Anti-sjednocení vyššího řádu

Tato sekce potřebuje expanzi s: (jak je uvedeno výše). Můžete pomoci přidávat k tomu. (Červen 2020)

• Počet konstrukcí: Pfenning, Franku (Červenec 1991). „Sjednocení a anti-sjednocení v počtu staveb“ (PDF). Proc. 6. LICS. Springer. str. 74–85.
• Kalkul lambda s jednoduchým zadáním (Vstup: Termíny v beta-normální formě eta-long. Výstup: vzory vyššího řádu): Baumgartner, Alexander; Kutsia, Temur; Levy, Jordi; Villaret, Mateu (červen 2013). Varianta anti-sjednocení vyšších řádů. Proc. RTA 2013. Sv. 21 z LIPIcs. Schloss Dagstuhl, 113-127. Software.
• Kalkulus lambda s jednoduchým zadáním (Vstup: Termíny v beta-normální formě eta-long. Výstup: Různé fragmenty kalkulátoru lambda s jednoduchým zadáním včetně vzorů): Černá, David; Kutsia, Temur (červen 2019). „Obecný rámec pro zobecnění vyšších řádů“ (PDF). 4. mezinárodní konference o formálních strukturách pro výpočet a odpočet, FSCD, 24. – 30. Června 2019, Dortmund, Německo. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. str. 74–85.
• Omezené substituce vyšších řádů: Wagner, Ulrich (duben 2002), Kombinatoricky omezená anti-unifikace vyšších objednávek, TU Berlín; Schmidt, Martin (září 2010), Omezená anti-sjednocení vyšších řádů pro heuristickou projekci teorie (PDF), PICS-Report, 31-2010, Univ. Osnabrück, Německo, ISSN  1610-5389

Poznámky

Reference