Dados os conjuntos e , uma relação difuncional entre eles é definida como uma relação que satisfaz a seguinte propriedade:
Se e e , então .
Relações difuncionais são uma generalização do conceito de relações de equivalência parcial que permitem definir uma noção de igualdade a partir de diferentes conjuntos. Como resultado, eles também são conhecidos como quase-PERs (QPERs) e também são conhecidos como relações em zig-zag, devido à seguinte imagem:
Estou escrevendo um artigo que os utiliza, mas tive problemas para localizar boas referências para uso em semântica.
- Martin Hoffman os utiliza na correção de transformações de programas baseados em efeitos .
- Eu já vi menções (mas nenhuma boa referência) alegando que Tennant e Takeyama também propuseram seu uso.
Eles são uma idéia tão bonita que tenho dificuldade em acreditar que meu uso particular deles seja original. Eu realmente aprecio quaisquer outras referências.
reference-request
pl.programming-languages
denotational-semantics
logical-relations
Neel Krishnaswami
fonte
fonte
Respostas:
Makoto Takeyama e eu enviamos o seguinte para [email protected] em 5 de janeiro de 1996:
fonte
Não conheço o campo da semântica, mas o conceito que você menciona é crucial na complexidade da contagem.
fonte