Sjednocení (počítačová věda) - Unification (computer science)

V logice a informatice je sjednocení algoritmický proces řešení rovnic mezi symbolickými výrazy .

V závislosti na tom, které výrazy (také nazývané termíny ) se mohou vyskytovat v sadě rovnic (také nazývané problém sjednocení ) a které výrazy jsou považovány za stejné, se rozlišuje několik rámců sjednocení. Pokud jsou ve výrazu povoleny proměnné vyššího řádu, tj. Proměnné představující funkce , tento proces se nazývá unifikace vyššího řádu , jinak unifikace prvního řádu . Pokud je požadováno řešení, aby se obě strany každé rovnice staly doslova rovnocennými, nazývá se tento proces syntaktickým nebo volným sjednocením , jinak sémantickým nebo rovníkovým sjednocením nebo E-unifikací nebo unifikační teorií modulo .

Řešení problému sjednocení je označován jako substituce , to znamená, je mapování přiřazení symbolickou hodnotu pro každou proměnnou výrazů je problém je. Alifikační algoritmus by měl pro daný problém vypočítat úplnou a minimální sadu substitucí, tj. Sadu pokrývající všechna jeho řešení a neobsahující žádné nadbytečné členy. V závislosti na rámci může mít úplná a minimální substituční sada nejvýše jednoho, maximálně konečného počtu členů nebo možná nekonečně mnoho členů, nebo nemusí vůbec existovat. V některých rámcích je obecně nemožné rozhodnout, zda nějaké řešení existuje. Pro syntaktické sjednocení prvního řádu poskytli Martelli a Montanari algoritmus, který hlásí neřešitelnost nebo vypočítá úplnou a minimální sadu substitucí singletonů, která obsahuje takzvaný nejobecnější unifikátor .

Například pomocí x , y , z jako proměnných je sada singletonových rovnic { cons ( x , cons ( x , nil )) = cons (2, y )} syntaktickým problémem sjednocení prvního řádu, který má substituci { x ↦ 2, y ↦ cons (2, nil )} jako jediné řešení. Syntaktický problém sjednocení prvního řádu { y = cons (2, y )} nemá řešení přes množinu konečných výrazů ; má však jediné řešení { y ↦ cons (2, cons (2, cons (2, ...)))} přes množinu nekonečných stromů . Sémantický problém sjednocení prvního řádu { a ⋅ x = x ⋅ a } má každou substituci tvaru { x ↦ a ⋅ ... ⋅ a } jako řešení v poloskupině , tj. Pokud (⋅) je považován za asociativní ; stejný problém, nahlížený v abelianské skupině , kde (⋅) je také považován za komutativní , má jako řešení jakoukoli substituci. Singletonová sada { a = y ( x )} je syntaktický problém sjednocení druhého řádu, protože y je funkční proměnná. Jedním z řešení je { x ↦ a , y ↦ ( funkce identity )}; další je { y ↦ ( konstantní funkce mapující každou hodnotu na a ), x ↦ (libovolná hodnota) }.

Algoritmus sjednocení byl poprvé objeven Jacquesem Herbrandem , zatímco první formální vyšetřování lze přičíst Johnu Alanovi Robinsonovi , který použil syntaktickou unifikaci prvního řádu jako základní stavební kámen svého postupu řešení logiky prvního řádu, což je velký krok vpřed v technologie automatizovaného uvažování , protože eliminovala jeden zdroj kombinatorické exploze: hledání instance výrazů. V dnešní době je automatické uvažování stále hlavní aplikační oblastí unifikace. V logickém programování a implementaci systému typu programovací jazyk se používá syntaktické sjednocení prvního řádu , zejména v odvozovacích algoritmech typu založených na Hindley-Milnerovi . Sémantické sjednocení se používá v řešeních SMT , algoritmech pro přepisování termínů a analýze kryptografického protokolu . U důkazních asistentů, například Isabelle a Twelf , se používá sjednocení vyššího řádu a v některých implementacích programovacích jazyků, jako je lambdaProlog , se používají omezené formy sjednocení vyššího řádu (sjednocení vzorů vyššího řádu ) , protože vzory vyššího řádu jsou expresivní , přesto jejich přidružený postup sjednocení zachovává teoretické vlastnosti blíže unifikaci prvního řádu.

Společné formální definice

Předpoklady

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

• Nekonečná množina z proměnných . Pro sjednocení vyššího řádu je vhodné vybrat disjunktní ze sady proměnných vázaných na lambda termín .${\ displaystyle V}$${\ displaystyle V}$
• Sada z hlediska taková, že . Pro sjednocení prvního řádu a sjednocení vyššího řádu je obvykle sada termínů prvního řádu (termíny postavené z variabilních a funkčních symbolů) a lambda termínů (termíny obsahující některé proměnné vyššího řádu).${\ displaystyle T}$${\ Displaystyle V \ subseteq T}$${\ displaystyle T}$
• Mapování proměnnými : , přiřazení každého výrazu sadu z volných proměnných vyskytujících se v .${\ Displaystyle T \ rightarrow}$ ${\ displaystyle \ mathbb {P}}$${\ displaystyle (V)}$${\ displaystyle t}$${\ displaystyle {\ text {vars}} (t) \ subsetneq V}$${\ displaystyle t}$
• Relace ekvivalence na , uvádějící, které termíny jsou považovány za rovnocenné. Pro sjednocení vyššího řádu, obvykle pokud a jsou ekvivalentní alfa . U E-unifikace prvního řádu odráží znalosti na pozadí o určitých funkčních symbolech; pokud je například považován za komutativní, pokud je výsledkem záměny argumentů u některých (možná všech) výskytů. Neexistuje -li vůbec žádná znalost pozadí, pak pouze doslovně nebo syntakticky jsou identické termíny považovány za rovnocenné; V tomto případě ≡ se nazývá volné teorii (protože se jedná o volný objekt ) je prázdná teorie (protože množina Ekvacionální vět , nebo znalosti pozadí, prázdný) je teorie uninterpreted funkce (z důvodu sjednocení se provádí na neinterpretované termíny ) nebo teorii konstruktorů (protože všechny funkční symboly pouze vytvářejí datové termíny, místo aby s nimi operovaly).${\ displaystyle \ equiv}$${\ displaystyle T}$${\ Displaystyle t \ equiv u}$${\ displaystyle t}$${\ displaystyle u}$${\ displaystyle \ equiv}$${\ displaystyle \ oplus}$${\ Displaystyle t \ equiv u}$${\ displaystyle u}$${\ displaystyle t}$${\ displaystyle \ oplus}$

Termín prvního řádu

Vzhledem k tomu, soubor proměnných symbolů, sada konstantních symbolů a sestav z n -ary funkčních symbolů, také nazývaných operátora symbolů pro každý přirozené číslo , je množina (netříděný prvního řádu), pokud jde se rekurzivně definována jako nejmenší souprava s následující vlastnosti: ${\ displaystyle V}$${\ displaystyle C}$${\ displaystyle F_ {n}}$${\ Displaystyle n \ geq 1}$${\ displaystyle T}$

• každý variabilní symbol je termín: ,${\ Displaystyle V \ subseteq T}$
• každý konstantní symbol je termín: ,${\ Displaystyle C \ subseteq T}$
• z každých n termínů a každého symbolu n -ary funkce lze sestavit větší termín .${\ displaystyle t_ {1}, ... t_ {n}}$${\ displaystyle f \ v F_ {n}}$${\ displaystyle f (t_ {1}, ..., t_ {n})}$

Například pokud je variabilní symbol, je konstantní symbol a je symbolem binární funkce, pak (a tedy) podle prvního, druhého a třetího pravidla budování termínu. Druhý termín je obvykle napsán jako , s použitím infixového zápisu a běžnějšího symbolu operátora + pro pohodlí. ${\ displaystyle x \ v V}$${\ Displaystyle 1 \ v C}$${\ displaystyle {\ text {add}} \ v F_ {2}}$${\ Displaystyle x \ v T, 1 \ v T}$${\ displaystyle {\ text {add}} (x, 1) \ v T}$${\ displaystyle x+1}$

Termín vyššího řádu

Střídání

Substituce je mapování z proměnných, které je z hlediska; zápis se týká substituce mapující každou proměnnou na výraz , pro a každou další proměnnou na sebe. Použití této náhrady na výraz je zapsáno v postfixové notaci jako ; to znamená, že se (současně) nahradit každý výskyt každé proměnné v termínu od . Výsledek aplikace substituce na termín se nazývá instance tohoto výrazu . Jako příklad prvního řádu, použití substituce { x ↦ h ( a , y ), z ↦ b } na výraz ${\ Displaystyle \ sigma: V \ rightarrow T}$${\ Displaystyle \ {x_ {1} \ mapsto t_ {1}, ..., x_ {k} \ mapsto t_ {k} \}}$${\ displaystyle x_ {i}}$${\ displaystyle t_ {i}}$${\ Displaystyle i = 1, ..., k}$${\ displaystyle t}$${\ Displaystyle t \ {x_ {1} \ mapsto t_ {1}, ..., x_ {k} \ mapsto t_ {k} \}}$${\ displaystyle x_ {i}}$${\ displaystyle t}$${\ displaystyle t_ {i}}$${\ Displaystyle t \ tau}$${\ displaystyle \ tau}$${\ displaystyle t}$${\ displaystyle t}$

	${\ displaystyle f (}$	${\ displaystyle {\ textbf {x}}}$	${\ displaystyle, a, g (}$	${\ displaystyle {\ textbf {z}}}$	${\ displaystyle), y)}$
výnosy
	${\ displaystyle f (}$	${\ displaystyle {\ textbf {h}} ({\ textbf {a}}, {\ textbf {y}})}$	${\ displaystyle, a, g (}$	${\ displaystyle {\ textbf {b}}}$	${\ Displaystyle), y).}$

Zobecnění, specializace

Pokud má výraz instanci ekvivalentní výrazu , to znamená, že je -li pro nějakou substituci , pak se nazývá obecnější než a je nazýván zvláštnějším než nebo zahrnut do . Od té doby je například obecnější, než když je ⊕ komutativní . ${\ displaystyle t}$${\ displaystyle u}$${\ Displaystyle t \ sigma \ equiv u}$${\ Displaystyle \ sigma}$${\ displaystyle t}$${\ displaystyle u}$${\ displaystyle u}$${\ displaystyle t}$${\ displaystyle x \ oplus a}$${\ Displaystyle a \ oplus b}$${\ Displaystyle (x \ oplus a) \ {x \ mapsto b \} = b \ oplus a \ equiv a \ oplus b}$

Je -li ≡ doslovná (syntaktická) identita výrazů, může být výraz obecnější i zvláštnější než jiný pouze tehdy, pokud se oba termíny liší pouze názvy proměnných, nikoli syntaktickou strukturou; tyto termíny se nazývají varianty nebo vzájemná přejmenování . Například je varianta , protože ${\ Displaystyle f (x_ {1}, a, g (z_ {1}), y_ {1})}$${\ Displaystyle f (x_ {2}, a, g (z_ {2}), y_ {2})}$

a

Není to však varianta , protože žádná substituce nemůže transformovat druhý termín na bývalý. Druhý termín je tedy mnohem zvláštnější než ten předchozí. ${\ Displaystyle f (x_ {1}, a, g (z_ {1}), y_ {1})}$${\ Displaystyle f (x_ {2}, a, g (x_ {2}), x_ {2})}$

Pro libovolný termín může být obecnější i zvláštnější než strukturálně odlišný výraz. Pokud je například ⊕ idempotentní , tj. Pokud vždy , pak je výraz obecnější než a naopak, i když a mají odlišnou strukturu. ${\ displaystyle \ equiv}$${\ Displaystyle x \ oplus x \ equiv x}$${\ Displaystyle x \ oplus y}$${\ Displaystyle z}$${\ Displaystyle x \ oplus y}$${\ Displaystyle z}$

Substituce je speciálnější než substituce , nebo je zahrnuta , pokud je substituce specifičtější než pro každý výraz . Také říkáme, že je to obecnější než . Například je zvláštnější než , ale není, protože není zvláštnější než . ${\ Displaystyle \ sigma}$${\ displaystyle \ tau}$${\ Displaystyle t \ sigma}$${\ Displaystyle t \ tau}$${\ displaystyle t}$${\ displaystyle \ tau}$${\ Displaystyle \ sigma}$${\ displaystyle \ {x \ mapsto a, y \ mapsto a \}}$${\ Displaystyle \ tau = \ {x \ mapsto y \}}$${\ Displaystyle \ sigma = \ {x \ mapsto a \}}$${\ Displaystyle f (x, y) \ sigma = f (a, y)}$${\ Displaystyle f (x, y) \ tau = f (y, y)}$

Problém sjednocení, sada řešení

Problém sjednocení je konečná množina { l ₁ ≐ r ₁ , ..., l _n ≐ r _n } potenciálních rovnic, kde l _i , r _i ∈ T . Substituce σ je řešením tohoto problému, pokud l _i σ ≡ r _i σ pro . Taková náhrada se také nazývá sjednotitel problému sjednocení. Pokud je například ⊕ asociativní , má problém sjednocení { x ⊕ a ≐ a ⊕ x } řešení { x ↦ a }, { x ↦ a ⊕ a }, { x ↦ a ⊕ a ⊕ a } atd., zatímco problém { x ⊕ a ≐ a } nemá řešení. ${\ Displaystyle i = 1, ..., n}$

Pro daný problém sjednocení se množina S sjednocovačů nazývá úplná, pokud je každá substituce řešení subsumována nějakou substitucí σ ∈ S ; množina S se nazývá minimální, pokud žádný z jejích členů nezahrnuje jiného.

Syntaktické sjednocení podmínek prvního řádu

Schematický trojúhelníkový diagram syntakticky sjednocujících členů t ₁ a t ₂ substitucí σ

Syntaktická unifikace termínů prvního řádu je nejpoužívanější unifikační rámec. Je založen na T je množina prvního řádu, pokud jde (kvůli nějaké dané nastavené V proměnných, C konstant a F _n o n -ary funkční symboly) a na ≡ že syntaktické rovnosti . V tomto rámci má každý řešitelný problém sjednocení { l ₁ ≐ r ₁ , ..., l _n ≐ r _n } úplnou a zjevně minimální sadu singletonových řešení { σ } . Jeho člen σ se nazývá nejobecnějším sjednotitelem ( mgu ) problému. Termíny na levé a pravé straně každé potenciální rovnice se syntakticky rovnají, když se použije mgu, tj. L ₁ σ = r ₁ σ ∧ ... ∧ l _n σ = r _n σ . Jakýkoli unifikátor problému je zahrnut v mgu σ . Mgu je jedinečný až do variant: pokud jsou S ₁ a S ₂ úplné a minimální sady řešení stejného syntaktického unifikačního problému, pak S ₁ = { σ ₁ } a S ₂ = { σ ₂ } pro některé substituce σ ₁ a σ ₂ , a xσ ₁ je varianta xσ ₂ pro každou proměnnou x vyskytující se v problému.

Například, problém sjednocení { x ≐ z , y ≐ f ( x )} má unifikátorem { x ↦ z , y ↦ f ( z )}, protože

X	{ x ↦ z , y ↦ f ( z )}	=	z	=	z	{ x ↦ z , y ↦ f ( z )}	, a
y	{ x ↦ z , y ↦ f ( z )}	=	f ( z )	=	f ( x )	{ x ↦ z , y ↦ f ( z )}	.

Toto je také nejobecnější unifikátor. Dalšími unifikátory pro stejný problém jsou např. { X ↦ f ( x ₁ ), y ↦ f ( f ( x ₁ )), z ↦ f ( x ₁ )}, { x ↦ f ( f ( x ₁ )), y ↦ f ( f ( f ( x ₁ ))), z ↦ f ( f ( x ₁ ))} atd.; podobných nekonečných prostředků je nekonečně mnoho.

Jako další příklad, problém g ( x , x ) ≐ f ( y ) nemá řešení, pokud jde o ≡ doslovnou identitu, protože jakákoli substituce aplikovaná na levou a pravou stranu udrží nejvzdálenější g a f , a termíny s různými krajními funkčními symboly jsou syntakticky odlišné.

Algoritmus sjednocení

První algoritmus daný Robinsonem (1965) byl poměrně neefektivní; srov. krabice. Následující rychlejší algoritmus pochází z Martelli, Montanari (1982). Tento článek také uvádí předchozí pokusy najít účinný syntaktický unifikační algoritmus a uvádí, že algoritmy lineárního času byly objeveny nezávisle Martelli, Montanari (1976) a Paterson, Wegman (1978).

Vzhledem k omezené množině potenciálních rovnic algoritmus použije pravidla k jeho transformaci na ekvivalentní sadu rovnic tvaru { x ₁ ≐ u ₁ , ..., x _m ≐ u _m } kde x ₁ , ..., x _m jsou odlišné proměnné a u ₁ , ..., u _m jsou termíny neobsahující žádné z x _i . Soubor tohoto formuláře lze číst jako náhradu. Pokud neexistuje řešení, algoritmus končí ⊥; jiní autoři v takovém případě používají „Ω“, „{}“ nebo „ fail “. Operace nahrazení všech výskytů proměnné x v problému G termínem t se označuje G { x ↦ t }. Pro jednoduchost jsou konstantní symboly považovány za funkční symboly s nulovými argumenty. ${\ Displaystyle G = \ {s_ {1} \ doteq t_ {1}, ..., s_ {n} \ doteq t_ {n} \}}$

${\ Displaystyle G \ cup \ {t \ doteq t \}}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle G}$		vymazat
${\ Displaystyle G \ cup \ {f (s_ {0}, ..., s_ {k}) \ doteq f (t_ {0}, ..., t_ {k}) \}}$	${\ displaystyle \ Rightarrow}$	${\ Displaystyle G \ cup \ {s_ {0} \ doteq t_ {0}, ..., s_ {k} \ doteq t_ {k} \}}$		rozložit
${\ Displaystyle G \ cup \ {f (s_ {0}, \ ldots, s_ {k}) \ doteq g (t_ {0}, ..., t_ {m}) \}}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle \ bot}$	jestli nebo${\ Displaystyle f \ neq g}$${\ Displaystyle k \ neq m}$	konflikt
${\ Displaystyle G \ cup \ {f (s_ {0}, ..., s_ {k}) \ doteq x \}}$	${\ displaystyle \ Rightarrow}$	${\ Displaystyle G \ cup \ {x \ doteq f (s_ {0}, ..., s_ {k}) \}}$		vyměnit
${\ Displaystyle G \ cup \ {x \ doteq t \}}$	${\ displaystyle \ Rightarrow}$	${\ Displaystyle G \ {x \ mapsto t \} \ cup \ {x \ doteq t \}}$	kdyby a${\ displaystyle x \ not \ in {\ text {vars}} (t)}$${\ displaystyle x \ in {\ text {vars}} (G)}$	odstranit
${\ Displaystyle G \ cup \ {x \ doteq f (s_ {0}, ..., s_ {k}) \}}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle \ bot}$	-li ${\ displaystyle x \ in {\ text {vars}} (f (s_ {0}, ..., s_ {k}))}$	šek

Probíhá kontrola

Pokus sjednotit proměnnou x termínem obsahujícím x jako přísný podzáklad x ≐ f (..., x , ...) by vedl k nekonečnému pojmu jako řešení pro x , protože x by se vyskytovalo jako podzáklad sebe sama . V množině (konečných) termínů prvního řádu, jak jsou definovány výše, rovnice x ≐ f (..., x , ...) nemá řešení; proto je odstranit pravidlo může být použita pouze tehdy, když x ∉ Vars ( t ). Protože tato dodatečná kontrola, nazývaná kontrola výskytu , zpomaluje algoritmus, je ve většině systémů Prolog vynechána. Z teoretického hlediska, vynechání kontrolních částek k řešení rovnic nad nekonečnými stromy, viz níže .

Doklad o ukončení

Pro důkaz ukončení algoritmu zvažte trojici, kde n _var je počet proměnných, které se vyskytují více než jednou v sadě rovnic, n _lhs je počet funkčních symbolů a konstant na levé straně potenciálních rovnic, a n _eqn je počet rovnic. Když je aplikováno vyloučení pravidel , n _var klesá, protože x je eliminováno z G a ponecháno pouze v { x ≐ t }. Použití jakéhokoli jiného pravidla již nikdy nemůže zvýšit n _var . Když se použije rozklad , konflikt nebo swap pravidla , n _{lhs se} sníží, protože zmizí alespoň vnější f levé strany . Použitím některého ze zbývajících pravidel mazání nebo kontrola nelze zvýšit n _lhs , ale snížit n _eqn . Jakákoli aplikace pravidel tedy snižuje trojnásobek vzhledem k lexikografickému řádu , což je možné jen konečný počet opakování. ${\ Displaystyle \ langle n_ {var}, n_ {lhs}, n_ {eqn} \ rangle}$${\ Displaystyle \ langle n_ {var}, n_ {lhs}, n_ {eqn} \ rangle}$

Conor McBride poznamenává, že „vyjádřením struktury, kterou unifikace využívá“ v závisle napsaném jazyce, jako je Epigram , lze Robinsonův algoritmus provést rekurzivně podle počtu proměnných , přičemž v takovém případě je samostatný důkaz ukončení zbytečný.

Příklady syntaktického sjednocení termínů prvního řádu

V syntaktické konvenci Prolog je symbol začínající velkými písmeny název proměnné; symbol, který začíná malým písmenem, je funkční symbol; čárka se používá jako logický a operátor. Pro matematický zápis se jako proměnné používají x, y, z , f, g jako funkční symboly a a, b jako konstanty.

Zápis prologu	Matematický zápis	Sjednocující substituce	Vysvětlení
a = a	{ a = a }	{}	Uspěje. ( tautologie )
a = b	{ a = b }	⊥	a a b se neshodují
X = X	{ x = x }	{}	Uspěje. ( tautologie )
a = X	{ a = x }	{ x ↦ a }	x je sjednoceno s konstantou a
X = Y	{ x = y }	{ x ↦ y }	x a y jsou aliasy
f(a,X) = f(a,b)	{ f ( a , x ) = f ( a , b )}	{ x ↦ b }	funkce a konstantní symboly se shodují, x je sjednoceno s konstantou b
f(a) = g(a)	{ f ( a ) = g ( a )}	⊥	f a g se neshodují
f(X) = f(Y)	{ f ( x ) = f ( y )}	{ x ↦ y }	x a y jsou aliasy
f(X) = g(Y)	{ f ( x ) = g ( y )}	⊥	f a g se neshodují
f(X) = f(Y,Z)	{ f ( x ) = f ( y , z )}	⊥	Selže. K f funkční symboly mají různé aritu
f(g(X)) = f(Y)	{ f ( g ( x )) = f ( y )}	{ y ↦ g ( x )}	Sjednocuje y s výrazem${\ displaystyle g (x)}$
f(g(X),X) = f(Y,a)	{ f ( g ( x ), x ) = f ( y , a )}	{ x ↦ a , y ↦ g ( a )}	Sjednocuje x s konstantou a , y s termínem${\ displaystyle g (a)}$
X = f(X)	{ x = f ( x )}	mělo by být ⊥	Vrátí ⊥ v logice prvního řádu a mnoha moderních dialogy Prolog (vynucené kontrolou výskytu ). Úspěch v tradičním Prologu a v Prologu II, sjednocení x s nekonečným termínem x=f(f(f(f(...)))).
X = Y, Y = a	{ x = y , y = a }	{ x ↦ a , y ↦ a }	Oba x a y jsou sjednoceny s konstantou a
a = Y, X = Y	{ a = y , x = y }	{ x ↦ a , y ↦ a }	Jak je uvedeno výše (na pořadí rovnic v množině nezáleží)
X = a, b = X	{ x = a , b = x }	⊥	Selže. a a b se neshodují, takže x nelze sjednotit s oběma

Dva termíny s exponenciálně větším stromem pro jejich nejméně běžnou instanci. Jeho dag reprezentace (úplně vpravo, oranžová část) má stále lineární velikost.

Nejobecnější unifikátor syntaktického problému sjednocení prvního řádu velikosti n může mít velikost 2 ⁿ . Problém má například nejobecnější unifikátor , srov. obrázek. Aby se předešlo exponenciální časové složitosti způsobené takovou explozí , pokročilé unifikační algoritmy pracují spíše na řízených acyklických grafech (dags) než na stromech. ${\ Displaystyle ((((a*z)*y)*x)*w \ doteq w*(x*(y*(z*a)))}$${\ Displaystyle \ {z \ mapsto a, y \ mapsto a*a, x \ mapsto (a*a)*(a*a), w \ mapsto ((a*a)*(a*a))*( (a*a)*(a*a)) \}}$

Aplikace: unifikace v logickém programování

Koncept sjednocení je jednou z hlavních myšlenek logického programování , nejlépe známou z jazyka Prolog . Představuje mechanismus vazby obsahu proměnných a lze jej považovat za jakési jednorázové přiřazení. V Prologu je tato operace označena symbolem rovnosti =, ale provádí se také při vytváření instancí proměnných (viz níže). To je také používáno v jiných jazycích pomocí symbolu rovnosti =, ale také ve spojení s mnoha operací včetně +, -, *, /. Algoritmy odvozování typů jsou obvykle založeny na unifikaci.

V Prologu:

1. Proměnná , která je uninstantiated-tedy žádné předchozí unifikace byly provedeny na to, mohou být sjednoceny s atomem, termín, nebo jiného uninstantiated proměnné, tak účinně stává jeho alias. V mnoha moderních prologských dialektech a logice prvního řádu nelze proměnnou sjednotit s termínem, který ji obsahuje; toto je takzvaná kontrola výskytu .
2. Dva atomy lze sjednotit pouze tehdy, jsou -li identické.
3. Podobně, termín může být sjednoceny s jiným termínem, pokud horní funkční symboly a aritami termínů jsou identické a v případě, že parametry mohou být sjednoceny současně. Všimněte si, že se jedná o rekurzivní chování.

Použití: odvození typu

Sjednocení se používá při odvozování typu, například ve funkčním programovacím jazyce Haskell . Na jedné straně programátor nemusí poskytovat informace o typu pro každou funkci, na druhé straně slouží k detekci překlepů. Výraz Haskell True : ['x', 'y', 'z']není zadán správně. Funkce konstrukce seznamu (:)je typu a -> [a] -> [a]a pro první argument musí být Trueproměnná polymorfního typu asjednocena s Truetypem ', Bool. Druhý argument,, ['x', 'y', 'z']je typu [Char], ale anemůže být obojí Boola Charsoučasně.

Stejně jako pro Prolog lze zadat algoritmus pro odvozování typů:

1. Libovolná typová proměnná se sjednotí s jakýmkoli výrazovým typem a bude vytvořena pro tento výraz. Specifická teorie může toto pravidlo omezit kontrolou výskytu.
2. Dvě typové konstanty se sjednotí, pouze pokud jsou stejného typu.
3. Konstrukce dvou typů se sjednocují pouze v případě, že se jedná o aplikace stejného typu konstruktoru a všechny jejich typy komponent se rekurzivně sjednocují.

Vzhledem ke své deklarativní povaze je pořadí v pořadí sjednocení (obvykle) nedůležité.

Všimněte si, že v terminologii logiky prvního řádu je atom základním tvrzením a je sjednocen podobně jako prologský termín.

Sjednocení seřazené podle objednávek

Objednávek řazeny logiky dovolí jednoho přiřadit druh nebo typ , aby každý termín, a prohlásit jakýsi s ₁ subsort o jiný druh s ₂ , obyčejně psán jak s ₁ ⊆ s ₂ . Například když uvažujeme o biologických stvořeních, je užitečné prohlásittřídicího psa za podřazený druh nějakého zvířecího druhu. Všude tam, kde termín jakýsi s je zapotřebí, což je termín z jakéhokoliv subsort ze sa mohou být dodány místo. Například za předpokladu deklarace funkce matka : zvíře → zvíře a konstantní deklarace lassie : pes je termín matka ( lassie ) dokonale platný a má třídicí zvíře . Aby bylo možné dodat informaci, že matka psa je pes, může být vydánodalší prohlášení matka : pes → pes ; tomu se říká přetížení funkcí , podobné přetížení v programovacích jazycích .

Walther poskytl unifikační algoritmus pro termíny v logice seřazené podle pořadí, který požaduje, aby byly deklarovány také libovolné dva deklarované druhy s ₁ , s _{2, přičemž} jejich průsečík s ₁ ∩ s ₂ : pokud x ₁ a x ₂ je proměnná druhu s ₁ a s ₂ , rovnice x ₁ ≐ x ₂ má řešení { x ₁ = x , x ₂ = x }, kde x : s ₁ ∩ s ₂ . Poté, co tento algoritmus začlenil do klauzule automatizovaného ověřovače teorém, mohl vyřešit problém benchmarku jeho překladem do logiky seřazené podle řádů, čímž jej uvaril o řád, protože mnoho unárních predikátů se změnilo v druhy.

Smolka zobecnil logiku seřazenou podle pořadí, aby umožnil parametrický polymorfismus . V jeho rámci jsou deklarace podtřídy šířeny do výrazů komplexního typu. Jako příklad programování může být deklarován parametrický třídicí seznam ( X ) (přičemž X je parametr typu jako v šabloně C ++ ) a z deklarace podtřídy int ⊆ float se seznam relací ( int ) ⊆ list ( float ) automaticky odvozeno, což znamená, že každý seznam celých čísel je také seznamem plováků.

Schmidt-Schauß zobecnila logiku seřazenou podle pořadí, aby umožňovala deklarace termínů. Například za předpokladu deklarací podtřídy sudých ⊆ int a lichých ⊆ int , termínové deklarace jako ∀ i  : int . ( i + i ): dokonce umožňuje deklarovat vlastnost sčítání celých čísel, která nemohla být vyjádřena běžným přetížením.

Sjednocení nekonečných pojmů

Pozadí na nekonečných stromech:

• B. Courcelle (1983). „Základní vlastnosti nekonečných stromů“ (PDF) . Teoret. Výpočet. Sci . 25 (2): 95–169. doi : 10,1016/0304-3975 (83) 90059-2 . Archivováno z originálu (PDF) dne 2014-04-21 . Citováno 2013-06-28 .
• Michael J. Maher (červenec 1988). „Kompletní axiomatizace algeber konečných, racionálních a nekonečných stromů“. Proč. IEEE 3. ročník Symp. o logice v informatice, Edinburgh . s. 348–357.
• Joxan Jaffar; Peter J. Stuckey (1986). „Sémantika programování logiky nekonečného stromu“ . Teoretická počítačová věda . 46 : 141–158. doi : 10,1016/0304-3975 (86) 90027-7 .

Algoritmus sjednocení, Prolog II:

• A. Colmerauer (1982). KL Clark; S.-A. Tarnlund (eds.). Prolog a nekonečné stromy . Akademický tisk.
• Alain Colmerauer (1984). „Rovnice a nerovnice na konečných a nekonečných stromech“. V ICOT (ed.). Proč. Int. Konf. na počítačových systémech páté generace . s. 85–99.

Aplikace:

• Francis Giannesini; Jacques Cohen (1984). „Generování analyzátoru a manipulace s gramatikou pomocí Prologových nekonečných stromů“ . Journal of Logic Programming . 1 (3): 253–265. doi : 10,1016/0743-1066 (84) 90013-X .

E-sjednocení

E-sjednocení je problém najít řešení pro daný soubor rovnic , s přihlédnutím k nějaké Ekvacionální pozadí znalostí E . Ten je uveden jako soubor univerzálních rovností . Pro některé konkrétní sady E byly navrženy algoritmy pro řešení rovnic (aka E-unifikační algoritmy ); u ostatních bylo prokázáno, že žádné takové algoritmy nemohou existovat.

Pokud například a a b jsou odlišné konstanty, rovnice nemá řešení s ohledem na čistě syntaktické sjednocení , kde o operátorovi není nic známo . Pokud je však známo, že je komutativní , pak substituce { x ↦ b , y ↦ a } řeší výše uvedenou rovnici, protože ${\ Displaystyle x*a \ doteq y*b}$${\ displaystyle *}$${\ displaystyle *}$

	${\ displaystyle x*a}$	{ x ↦ b , y ↦ a }
=	${\ displaystyle b*a}$		o substituční aplikací
=	${\ displaystyle a*b}$		komutativitou ${\ displaystyle *}$
=	${\ displaystyle y*b}$	{ x ↦ b , y ↦ a }	(konverzací) substituční aplikace

Základní znalosti E by mohly uvádět komutativitu univerzální rovnosti „ pro všechny u , v “. ${\ displaystyle *}$${\ Displaystyle u*v = v*u}$

Jednotlivé sady znalostí E

Použité konvence pojmenování

∀ u , v , w :	${\ Displaystyle u*(v*w)}$	=	${\ Displaystyle (u*v)*w}$	A	Asociativita ${\ displaystyle *}$
∀ u , v :	${\ displaystyle u*v}$	=	${\ displaystyle v*u}$	C	Komutativita ${\ displaystyle *}$
∀ u , v , w :	${\ displaystyle u*(v+w)}$	=	${\ Displaystyle u*v+u*w}$	D l	Levá distribučnost přes${\ displaystyle *}$${\ displaystyle +}$
∀ u , v , w :	${\ displaystyle (v+w)*u}$	=	${\ Displaystyle v*u+w*u}$	D r	Správná distribučnost přes${\ displaystyle *}$${\ displaystyle +}$
∀ u :	${\ displaystyle u*u}$	=	u	Já	Idempotence z ${\ displaystyle *}$
∀ u :	${\ displaystyle n*u}$	=	u	N l	Levý neutrální prvek n vzhledem k${\ displaystyle *}$
∀ u :	${\ displaystyle u*n}$	=	u	N r	Pravý neutrální prvek n vzhledem k${\ displaystyle *}$

Říká se, že sjednocení je pro teorii rozhodnutelné , pokud pro něj byl navržen unifikační algoritmus, který končí pro jakýkoli vstupní problém. Říká se, že sjednocení je pro teorii polorozhodnutelné , pokud pro něj byl navržen unifikační algoritmus, který končí pro jakýkoli řešitelný vstupní problém, ale může pokračovat v hledání řešení neřešitelného vstupního problému navždy.

Sjednocení je možné rozhodnout pro následující teorie:

• A
• A , C
• A , C , já
• A , C , N _l
• A , já
• A , N _l , N _r (monoid)
• C
• Booleovské prsteny
• Abelianské skupiny , i když je podpis rozšířen libovolnými dalšími symboly (ale ne axiomy)
• Modální algebry K4

Sjednocení je částečně rozhodnutelné pro následující teorie:

• A , D _l , D _r
• A , C , D _l
• Komutativní prsteny

Jednostranná paramodulace

Pokud je konvergentní termín přepisování systém R k dispozici pro E je jednostranný paramodulace algoritmus může být použit pro výčet všech řešení daných rovnic.

Počínaje G jako problémem sjednocení, který má být vyřešen, a S jako substitucí identity, pravidla se aplikují nedeterministicky, dokud se prázdná množina nezobrazí jako skutečné G , v takovém případě je skutečné S sjednocující substitucí. V závislosti na pořadí se aplikují pravidla paramodulace, na volbě skutečného rovnice z G , a na volbě R ' s pravidly mutovat , různé výpočty cesty jsou možné. Pouze některé vedou k řešení, zatímco jiné končí na G ≠ {}, kde již žádné další pravidlo neplatí (např. G = { f (...) ≐ g (...)}).

Například se používá systém přepisování termínů R definující připojený operátor seznamů sestavených z nevýhody a nuly ; kde cons ( x , y ) je zapsáno v infixovém zápisu jako x . y pro stručnost; např. aplikace ( a . b . nulová , c . d . nulová ) → a . aplikace ( b . nula , c . d . nula ) → a . b . aplikace ( nula , c . d . nula ) → a . b . c . d . nil ukazuje zřetězení seznamů a . b . nula a c . d . nil , využívající přepisovací pravidlo 2,2 a 1. Ekvacionální teorie E , což odpovídá R je uzávěr shoda z R , a to jak zobrazeno jako binární vztahů na podmínkách. Například, aplikace ( . B . Nulová , c . D . Nula ) ≡ . b . c . d . nil ≡ app ( a . b . c . d . nil , nil ). Algoritmus paramodulace výčet řešení rovnic v souvislosti s touto E při krmena příkladu R .

Úspěšný příklad cesty výpočtu pro problém sjednocení { app ( x , app ( y , x )) ≐ a . a . nil } je uveden níže. Aby se předešlo střetům názvů proměnných, jsou pravidla přepisování konzistentně přejmenována před jejich použitím mutací pravidel ; v ₂ , v ₃ , ... jsou pro tento účel počítačově generované názvy proměnných. V každém řádku je zvolená rovnice z G zvýrazněna červeně. Při každém použití pravidla mutace je v závorkách uvedeno zvolené pravidlo přepisu ( 1 nebo 2 ). Z posledního řádku sjednocující substituce S = { y ↦ nil , x ↦ a . nil } lze získat. Ve skutečnosti app ( x , app ( y , x )) { y ↦ nulové , x ↦ a . nula } = app ( a . nula , app ( nil , a . nil )) ≡ app ( a . nil , a . nil ) ≡ a . aplikace ( nula , a . nula ) ≡ a . a . nil řeší daný problém. Druhá úspěšná cesta výpočtu, kterou lze získat výběrem „mutovat (1), mutovat (2), mutovat (2), mutovat (1)“, vede k substituci S = { y ↦ a . a . nula , x ↦ nula }; zde se nezobrazuje. Žádná jiná cesta nevede k úspěchu.

Zúžení

Trojúhelníkový diagram kroku zúžení s ↝ t v poloze p v termu s , se sjednocující substitucí σ (spodní řada), pomocí přepisovacího pravidla l → r (horní řada)

Jestliže R je konvergentní systém přepisování termínů pro E , alternativa přístupu k předchozí části spočívá v postupném uplatňování „ zužujících se kroků “; toto nakonec vyjmenuje všechna řešení dané rovnice. Krok zúžení (viz obrázek) spočívá v

• výběrem neměnného podčastu aktuálního výrazu,
• syntakticky jej sjednotit levou stranou pravidla z R a
• nahrazení pravé strany instance pravidla na instancovaný výraz.

Formálně, pokud l → r je přejmenovaná kopie přepisovacího pravidla z R , která nemá žádné společné proměnné s výrazem s , a subterm s | _p není variabilní a je unifikovatelné s l přes MGU σ , potom je možno zúžen na termín t = sσ [ rσ ] _p , tedy k termínu sσ s subterm v p nahrazeny podle rσ . Situace, kterou lze s zúžit na t, se běžně označuje jako s ↝ t . Intuitivně sekvence zúžení kroky t ₁ ↝ t ₂ ↝ ... ↝ t _n si lze představit jako sekvence přepsání kroků t ₁ → t ₂ → ... → t _n , avšak s počáteční dobu t ₁ bytost dále a dále instancován, podle potřeby, aby každé z použitých pravidel bylo použitelné.

Výše uvedený příklad výpočtu paramodulace odpovídá následující zužující se sekvenci („↓“ zde označuje instanci):

Poslední termín, v ₂ . v ₂ . nula může být syntakticky sjednocena s původním pravým termínem a . a . nula .

V zúžení lemma zajišťuje, že vždy, když instance termín y může být přepsána na termínovaný t o konvergentní termín přepisování systému, pak to a t může být zúžen a přepsané na termínovaný s ' a t ' , v daném pořadí, tak, že t ' je příkladem s ' .

Formálně: kdykoli sσ →∗ t platí pro nějakou substituci σ, pak existují termíny s ′ , t ′ takové, že s ↝∗ s ' a t →∗ t ' a s ' τ = t ' pro nějakou substituci τ.

Sjednocení vyššího řádu

Mnoho aplikací vyžaduje, aby jeden zvážil sjednocení zadaných lambda termínů místo termínů prvního řádu. Takové sjednocení se často nazývá sjednocení vyššího řádu . Dobře studovaná větev sjednocení vyššího řádu je problém sjednocení jednoduše napsaných lambda termínů modulovajících rovnost určenou αβη převody. Takové problémy s unifikací nemají většinu obecných unifikátorů. Zatímco unifikace vyššího řádu je nerozhodnutelná , Gérard Huet poskytl semi-rozhodnutelný (pre-) unifikační algoritmus, který umožňuje systematické hledání prostoru unifikátorů (zobecnění unifikačního algoritmu Martelli-Montanari s pravidly pro termíny obsahující proměnné vyššího řádu) zdá se, že v praxi funguje dostatečně dobře. Huet a Gilles Dowek napsali články zaměřené na toto téma.

Dale Miller popsal to, čemu se nyní říká sjednocení vzorů vyššího řádu . Tato podmnožina sjednocení vyššího řádu je rozhodnutelná a řešitelné problémy sjednocení mají většinu obecných sjednocovačů. Mnoho počítačových systémů, které obsahují sjednocení vyššího řádu, jako jsou logické programovací jazyky vyššího řádu λProlog a Twelf , často implementují pouze fragment vzoru a nikoli úplné sjednocení vyššího řádu.

Ve výpočetní lingvistice je jednou z nejvlivnějších teorií elipsy to, že elipsy jsou reprezentovány volnými proměnnými, jejichž hodnoty jsou poté určeny pomocí Sjednocení vyššího řádu (HOU). Například sémantická reprezentace „Jon má rád Mary a Peter také“ je jako ( j , m ) ∧ R ( p ) a hodnota R (sémantická reprezentace elipsy) je určena rovnicí jako ( j , m ) = R ( j ) . Proces řešení takovýchto rovnic se nazývá Sjednocení vyššího řádu.

Například problém sjednocení { f ( a , b , a ) ≐ d ( b , a , c )}, kde jedinou proměnnou je f , má řešení { f ↦ λ x .λ y .λ z . d ( y , x , c )}, { f ↦ λ x .λ y .λ z . d ( y , z , c )}, { f ↦ λ x .λ y .λ z . d ( y , a , c )}, { f ↦ λ x .λ y .λ z . d ( b , x , c )}, { f ↦ λ x .λ y .λ z . d ( b , z , c )} a { f ↦ λ x .λ y .λ z . d ( b , a , c )}.

Wayne Snyder zobecnil jak unifikaci vyššího řádu, tak E-unifikaci, tj. Algoritmus pro sjednocení lambda termínů modulo rovníkové teorie.

Viz také

• Přepisování
• Přípustné pravidlo
• Explicitní substituce v lambda kalkulu
• Řešení matematické rovnice
• Dis-unifikace : řešení nerovností mezi symbolickým výrazem
• Anti-unifikace : výpočet nejméně obecné generalizace (lgg) dvou termínů, duální pro výpočet nejobecnější instance (mgu)
• Zarovnání ontologie (použijte unifikaci se sémantickou ekvivalencí )

Poznámky

Reference

Další čtení

• Franz Baader a Wayne Snyder (2001). „Teorie sjednocení“ archivována 2015-06-08 na Wayback Machine . In John Alan Robinson and Andrei Voronkov , editors, Handbook of Automated Reasoning, volume I, pages 447–533. Elsevier Science Publishers.
• Gilles Dowek (2001). „Sjednocení a párování vyššího řádu“ . V Příručce automatizovaného uvažování .
• Franz Baader a Tobias Nipkow (1998). Přepisování termínů a vše ostatní . Cambridge University Press.
• Franz Baader a Jörg H. Siekmann  [ de ] (1993). „Teorie sjednocení“. In Handbook of Logic in Artificial Intelligence and Logic Programming .
• Jean-Pierre Jouannaud a Claude Kirchner (1991). „Řešení rovnic v abstraktních algebrách: Průzkum sjednocení založený na pravidlech“. Ve výpočetní logice: Eseje na počest Alana Robinsona .
• Nachum Dershowitz a Jean-Pierre Jouannaud , Rewrite Systems , in: Jan van Leeuwen (ed.), Handbook of Theoretical Computer Science , svazek B Formální modely a sémantika , Elsevier, 1990, s. 243–320
• Jörg H. Siekmann (1990). „Teorie sjednocení“. In Claude Kirchner (editor) Sjednocení . Akademický tisk.
• Kevin Knight (březen 1989). „Sjednocení: Multidisciplinární průzkum“ (PDF) . Výpočetní průzkumy ACM . 21 (1): 93–124. CiteSeerX  10.1.1.64.8967 . doi : 10,1145/62029,62030 . S2CID  14619034 .
• Gérard Huet a Derek C. Oppen (1980). „Rovnice a pravidla pro přepis: průzkum“ . Technická zpráva. Stanfordská Univerzita.
• Raulefs, Peter; Siekmann, Jörg; Szabó, P .; Unvericht, E. (1979). „Krátký průzkum o stavu techniky v problémech shody a sjednocení“. Bulletin ACM SIGSAM . 13 (2): 14–20. doi : 10,1145/1089208.1089210 . S2CID  17033087 .
• Claude Kirchner a Hélène Kirchner. Přepisování, řešení, dokazování . Připravuje se.