Consistency and Completeness of Rewriting in the Calculus of Constructions
| Autor: | Daria Walukiewicz-Chrząszcz, Jacek Chrząszcz |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Symbolic Computation Computer Science - Logic in Computer Science General Computer Science Computer science Rho calculus Symbolic Computation (cs.SC) Theoretical Computer Science Consistency (database systems) Calculus Pattern matching Mathematics Proof assistant F.4.1 F.4.2 Logic in Computer Science (cs.LO) Undecidable problem Decidability Critical pair Type theory TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Completeness (logic) Confluence Rewriting |
| Zdroj: | Automated Reasoning ISBN: 9783540371878 IJCAR |
| ISSN: | 1860-5974 |
| DOI: | 10.2168/lmcs-4(3:8)2008 |
| Popis: | Adding rewriting to a proof assistant based on the Curry-Howard isomorphism, 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 property. 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, containing rules which depart from standard pattern matching. 20 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|