Injetividade não necessária para algoritmos de unificação?

Question

Ao aprender sobre um algoritmo geral de unificação, aprendemos a regra decompor , quais os estados unificam

$$ g \ cope \ {f (a_0, ... a_k)= f (b_0, ..., b_k) \} \ rightarrow g \ cope \ {a_0= b_0, ... a_k= b_k}. $$

A questão de "E se $ F $ não é injectivo?" se destacou para mim. Diga $ F $ não é injetivo, e nós atravessamos esse ramo de computação onde $ f (a_0, ... A_K)= F (B_0, ..., B_K) \ Rightarrow \ {a_0= b_0, ..., a_k= b_k \} $ e levar a falha. É possível que haja outra maneira de atribuir $ a_0, ..., A_K $ para $ b_0, ... B_K $ de tal forma que é unificável?

Eu estava pensando talvez de um exemplo para demonstrar o que quero dizer. Isso pode não ser um bom exemplo, mas dizer que consideramos $ f (x, y)= x + y $ , e queremos unificar $ f (h (a), g (b))= f (g (c), h (d)) $ então nós falharíamos atribuindo $ \ {h (a)= g (c), g (b)= h (d) \} $ por decompor, mas ter sucesso na unificação se, em vez disso, primeiro trocar os argumentos da $ F $ (válido desde a $ f (a, b)= f (b, a) $ ), que produzirá < span class="contêiner matemático"> $ \ {\ mapsto d, b \ mapsto c \} $ .

Eu estava lendo um pouco sobre isso em este papel Na página 6, onde eles discutem a ideia de rigor em termos de decomposição, mas eu não entendo muito, e mais geralmente como podemos realizar este passo de unificação de decompor em uma classe geral $ f $ sem o backtracking de alguma forma.

Answer 1

Aqui $ F $ não é uma função matemática. Pelo contrário, é um símbolo de função . Não pense em $ f (a, b) $ como resultado de avaliar a função em parâmetros $ a, b $ . Em vez disso, pense nisso como um termo em uma expressão simbólica - é um objeto sintático que não se destina a ser interpretado da maneira que você está interpretando.

Se você gosta, você pode pensar nisso como se cada símbolo de função em uma expressão simbólica seja uma função injetiva; Mas isso não é realmente preciso, isso é apenas uma maneira grosseira de pensar em expressões simbólicas.

Você não pode definir $ f (x)= x + y $ . $ F $ é um símbolo de função seminterpretado. Você não tem permissão para definir uma função específica. Em vez disso, $ F $ é um stand-in para uma função que ainda não está definida. Uma maneira de pensar sobre isso é que quaisquer conclusões que você extraem da unificação, são conclusões que devem manter todas as funções $ F $ (não apenas um único). < / p >.