Journal of the ACM · 2007 · 73 citations · 31 references
ComputingComputer ScienceFormal MethodsLogicTheory Of ComputationFormal SemanticsModel TheoryProof ComplexityRecursion TheoryType CheckingType SystemsAbstractionContextual EquivalenceDomain TheoryExistential TypesLambda CalculusLogical RelationsRecursive TypesType Theory
We present a bisimulation method for proving the contextual equivalence of packages in λ-calculus with full existential and recursive types. Unlike traditional logical relations (either semantic or syntactic), our development is “elementary,” using only sets and relations and avoiding advanced machinery such as domain theory, admissibility, and TT-closure. Unlike other bisimulations, ours is complete even for existential types. The key idea is to consider sets of relations—instead of just relations—as bisimulations.
31
Notions of computation and monads
Eugenio Moggi · Information and Computation · 1991 · 1.7K citations
A calculus for cryptographic protocols
Martı́n Abadi, Andrew D. Gordon · 1997 · 1.2K citations · Full text
Mobile values, new names, and secure communication
Martı́n Abadi, Cédric Fournet · 2001 · 843 citations
Philip Wadler · 1989 · 776 citations