Accession Number:



Proving Invariants of I/O Automata with TAME

Descriptive Note:

Journal article

Corporate Author:


Report Date:


Pagination or Media Count:



This paper describes a specialized interface to PVS called TAME Timed Automata Modeling Environment which provides automated support for proving properties of IO automata. A major goal of TAME is to allow a software developer to use PVS to specify and prove properties of an IO automaton efficiently and without first becoming a PVS expert. To accomplish this goal, TAME provides a template that the user completes to specify an IO automaton and a set of proof steps natural for humans to use for proving properties of automata. Each proof step is implemented by a PVS strategy and possibly some auxiliary theories that support that strategy. We have used the results of two recent formal methods studies as a basis for two case studies to evaluate TAME. In the first formal methods study, Romijn used IO automata to specify and verify memory and remote procedure call components of a concurrent system. In the second formal methods study, Devillers et al. specified a tree identify protocol TIP, part of the IEEE 1394 bus protocol, and provided hand proofs of TIP properties. Devillers also used PVS to specify TIP and to check proofs of TIP properties. In our first case study, the third author, a new TAME user with no previous PVS experience, used TAME to create PVS specifications of the IO automata formulated by Romijn and Devillers et al. and to check their hand proofs. In our second case study, the TAME approach to verification was compared with an alternate approach by Devillers which uses PVS directly.

Subject Categories:

  • Computer Programming and Software

Distribution Statement: