2 ms·
That depends on what you mean by "exactly the same approach". Can the same algorithm construct both proofs? Can it construct both proofs with the same computati
by pron 11y ago
That depends on what you mean by "exactly the same approach". Can the same algorithm construct both proofs? Can it construct both proofs with the same computational complexity? If not, then you're not using the same approach.
Using dependent types is more of a particular notation than a solution to verification. How you prove your type inference/checking is the hard part. Examples of approaches include SAT/SMT solvers, symbolic model checking, manual deduction, explicit model checking, abstract interpretation (which is really abstraction + explicit model checking; H-M inference algorithms can be described in terms of this approach), weakest preconditions, etc. You can use all of these approaches to infer/check dependent types, just as you can use them to verify program logic stated using means other than dependent types.
- lmm 11y ago> That depends on what you mean by "exactly the same approach". Can the same algorithm construct both proofs? Can it construct both proofs with the same computational complexity? Yes, because once you're representing the values with dependent types, metric recursion and structural recursion are physically the same thing.