Name
Abstract | ||
|---|---|---|
Adding rewriting to a proof assistant based on the Curry-Howard isomor- phism, such as Coq, may greatly improve usability of the tool. Unfortunately adding an arbitrary set of rewrite rules may render the underlying formal system undecidable and inconsistent. While ways to ensure termination and confluence, and hence decidability of type-checking, have already been studied to some extent, logical consistency has got little attention so far. In this paper we show that consistency is a consequence of canonicity, which in turn follows from the assumption that all functions defined by rewrite rules are complete. We provide a sound and terminating, but necessarily incomplete algorithm to verify this prop- erty. The algorithm accepts all definitions that follow dependent pattern matching schemes presented by Coquand and studied by McBride in his PhD thesis. It also accepts many definitions by rewriting including rules which depart from standard pattern matching. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/11814771_50 | IJCAR'06 Proceedings of the Third international joint conference on Automated Reasoning |
Keywords | DocType | Volume |
higher-order rewrit- ing,logical consistency,standard pattern matching,dependent pattern,curry-howard isomorphism,calculus of constructions,arbitrary set,lambda calculus.,phd thesis,underlying formal system undecidable,type theory,higher-order logic,term rewriting,proof assistant,incomplete algorithm,higher order logic,pattern matching,lambda calculus,higher order | Journal | abs/0806.1749 |
Issue | ISSN | ISBN |
3 | 0302-9743 | 3-540-37187-7 |
Citations | PageRank | References |
3 | 0.47 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daria Walukiewicz-Chrząszcz | 1 | 26 | 3.35 |
| Jacek Chrzaszcz | 2 | 36 | 6.38 |
| Natarajan Shankar | 3 | 3050 | 309.55 |