No label defined (Q4028349)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 139989
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 139989 |
Statements
28 March 1993
0 references
term rewriting
0 references
equational axiomatic specifications
0 references
development of formally verified software
0 references
interactive generation of inductive proofs
0 references
narrowing
0 references
induction
0 references
0.7669498324394226
0 references
0.7659380435943604
0 references
0.7637253403663635
0 references
0.7627167105674744
0 references
[For the entire collection see Zbl 0747.00046.] The aim of the present work is to the development of formally verified software, in particular during the early phases of development. Equational axiomatic specifications are used for describing the functionality of the intended product. We consider two layers of specification: In an operational layer, a very abstract but executable specification is given, which is similar to a functional program. In a theorem layer, equational statements about the software are made, which are not restricted to operationality and which may formulate rather general requirements or design decisions. We describe a tool for formally proving that the theorem layer is a consequence of the operational layer. The tool under discussion admits the interactive generation of inductive proofs, where induction relies on a well-founded ordering on terms (for instance the subterm ordering). The proof method is more powerful than simple structural induction, since it works with various orderings (for instance variants of the recursive path ordering). In contrast to the so- called ``induction-less'' approaches, we try to keep the proof method rather ``natural'', i.e. very similar to the human method for performing a proof with paper and pencil. In order to gain a suitable amount of automatization, the search for the proof is organized systematically by reuse of an existing deduction algorithm. It turns out that an adequate inductive proof method can be realized by applying relatively few modifications to the so-called narrowing algorithm. Narrowing is an algorithm for solving equations within the framework of an equational specification using a method similar to Prolog's resolution technique. Our tool uses the system RAP as its basis, which contains a flexible implementation of narrowing. Using this basis, since spring 1989 a prototype system (called TIP) is available, which allows us to experiment with practical examples. TIP is constantly improved, the latest version (1993) is able to deal effectively also with conditional-equational axioms. The paper is structured as follows: After a short introduction of basic terminology, we discuss the notion of induction which is used in our approach. It is explained how parts of the machinery given by a narrowing implementation can be re-used for the purposes of induction proofs. A short example for the practical use of the system is given. The summary of some experiences concludes the paper.
0 references