Iniettività non richiesta per gli algoritmi di unificazione?

Question

Quando si impara su un algoritmo di unificazione generale, abbiamo imparato la regola decomporsi , che afferma Unifying

$$ G \ Cup \ {f (A_0, ... a_k)= f (B_0, ..., B_K) \} \ RightArraw G \ Cup \ {A_0= B_0, ... a_k= b_k \}. $$

La domanda di, "Cosa succede se $ f $ non è iniettivo?" mi sono fermato. Dì $ f $ non è iniettivo, e attraversiamo il ramo del calcolo in cui $ f (a_0, ... a_k)= f (B_0, ..., B_K) \ Right Docka \ {A_0= B_0, ..., A_K= B_K \} $ e portare a fallimento. È possibile che ci sia un altro modo per assegnare $ a_0, ..., a_k $ a $ B_0, ... B_K $ tale che è unificabile?

Stavo pensando forse di un esempio per dimostrare cosa intendo. Questo potrebbe non essere un buon esempio, ma dire che consideriamo $ f (x, y)= x + y $ , e vogliamo unificare $ f (h (a), g (b))= f (g (c), h (d)) $ Allora avremmo fallito assegnando $ \ {h (a)= g (c), g (b)= h (d) \} $ per decompolazione, ma ha successo nell'unificazione se invece cambiamo per la prima volta gli argomenti di $ f $ (valido da $ f (a, b)= f (b, a) $ ), che produrrà < Span Class="Math-Container"> $ \ {A \ mapsto d, b \ mapsto c \} $ .

Stavo leggendo un po 'a riguardo in Questa carta A pagina 6 dove discutono l'idea di rigore in termini di decomporsione, ma non lo capisco, e più in generale come possiamo eseguire questa fase di unificazione decomporsi su una classe generale $ f $ senza in qualche modo backtracking sull'insufficienza.

Answer 1

qui $ f $ non è una funzione matematica. Piuttosto, è un Simbolo della funzione . Non pensare a $ f (A, B) $ come risultato della valutazione della funzione a parametri $ A, B $ . Piuttosto, pensaci come un termine in un'espressione simbolica - è un oggetto sintattico che non è destinato a essere interpretato nel modo in cui lo stai interpretando.

Se ti piace, puoi pensarlo come se ogni simbolo di funzione in un'espressione simbolica sia una funzione iniettiva; Ma non è proprio accurato, è solo un modo crudo per pensare alle espressioni simboliche.

Non è possibile definire $ f (x)= x + y $ . $ f $ è un simbolo funzione non interpretato. Non ti è permesso definire una particolare funzione. Piuttosto, $ f $ è uno stand-in per una funzione che non è ancora definita. Un modo per pensarci è che eventuali conclusioni che disegni dall'unificazione, sono conclusioni che dovrebbero tenere per tutte le funzioni $ f $ (non solo uno single). < / P >.