NASALib is a continuing collaborative effort that has spanned over 3 decades, to aid in research related to theorem proving sponsored by NASA (https://shemesh.larc.nasa.gov/fm/pvs/). It consists of a collection of formal development (i.e., libraries) written in the Prototype Verification System (PVS), contributed by SRI, NASA, NIA, and the PVS community, and maintained by the Formal Methods Team at LaRC.
The current version of NASALib is 7.1.2 (2023/09/01) and requires PVS 7.1.
Currently, NASALib consists of 62 top-level libraries, containing about 38K proven formulas in total.
| Library | Description |
|---|---|
| ACCoRD | Framework for the analysis of air traffic conflict detection and resolution algorithms |
| affine_arith | Formalization of affine arithmetic and strategy for evaluating polynomial functions with variables on interval domains |
| algebra | Groups, monoids, rings, etc |
| analysis | Real analysis, limits, continuity, derivatives, integrals |
| ASP | Denotational semantics of Answer Set Programming |
| aviation | Support definitions and properties for aviation-related formalizations |
| Bernstein | Formalization of multivariate Bernstein polynomials |
| CCG | Formalization of diverse termination criteria |
| complex | Complex numbers |
| complex_alt | Alternative formalization of complex numbers |
| complex_integration | Complex integration |
| co_structures | Sequences of countable length defined as co-algebraic datatypes |
| digraphs | Directed graphs: circuits, maximal subtrees, paths, DAGs |
| dL | Differential Dynamic Logic |
| exact_real_arith | Exact real arithmetic including trig functions |
| examples | Examples of application of the functionality provided by NASALib |
| extended_nnreal | Extended non-negative reals |
| fast_approx | Approximations of standard numerical functions |
| fault_tolerance | Fault tolerance protocols |
| float | Floating point arithmetic |
| graphs | Graph theory |
| interval_arith | Interval arithmetic and numerical approximations. Includes automated strategies numerical for computing numerical approximations and interval for checking satisfiability and validity of simply quantified real-valued formulas. This development includes a formalization of Allen interval temporal logic |
| ints | Integer division, gcd, mod, prime factorization, min, max |
| lebesgue | Lebesgue integral with connection to Riemann Integral |
| linear_algebra | Linear algebra |
| line_segments | 2-dimensional line segments |
| lnexp | Logarithm, exponential and hyperbolic functions. & Foundational definitions of logarithm, exponential and hyperbolic functions |
| LTL | Linear Temporal Logic |
| matrices | Executable specification of MxN matrices. This library includes computation of inverse and basic matrix operations such as addition and multiplication |
| measure_integration | Sigma algebras, measures, Fubini-Tonelli Lemmas |
| MetiTarski | Integration of MetiTarski, an automated theorem prover for real-valued functions |
| metric_space | Domains with a distance metric, continuity and uniform continuity |
| mv_analysis | Multivariate real analysis: norms, limits, continuity, derivatives, optimization, etc. |
| mult_poly | Multivariate polynomials and semi-algebriac sets. |
| nominal | Nominal equational reasoning |
| numbers | Elementary number theory |
| ODEs | Ordinary Differential Equations |
| orders | Abstract orders, lattices, fix points |
| polygons | 2-dimensional polygons |
| polygon_merge | Merge of 2-dimensional polygons without generating holes |
| power | Generalized Power function (without ln/exp) |
| probability | Probability theory |
| PVS0 | Formalization of fundamental computability concepts |
| pvsio_utils | Additions to PVSio, a PVS standard library for animation of PVS specifications |
| reals | Summations, sup, inf, sqrt over the reals, absolute value, etc |
| Riemann | Riemann integral |
| scott | Scott topology |
| series | Power series, comparison test, ratio test, Taylor's theorem |
| sets_aux | Power sets, orders, cardinality over infinite sets. Includes functional and relational facts based on Axiom of Choice and refinement relations based on equivalence relations |
| shapes | 2D-Shapes: triangle, parallelogram, rectangle, circular segment |
| sigma_set | Summations over countably infinite sets |
| sorting | Sorting algorithms |
| structures | Bounded arrays, finite sequences, bags, and several other structures |
| Sturm | Formalization of Sturm's theorem for univariate polynomials. Includes strategies sturm and mono-poly for automatically proving univariate polynomial relations over a real interval |
| Tarski | Formalization of Tarski's theorem for univariate polynomials. Includes strategy tarski for automatically proving systems of univariate polynomial relations on the real line |
| topology | Continuity, homeomorphisms, connected and compact spaces, Borel sets/functions |
| trig | Trigonometry: definitions, identities, approximations |
| TRS | Term rewrite systems and Robinson unification algorithm |
| TU_games | Cooperative TU-games |
| vect_analysis | Limits, continuity, and derivatives of vector functions |
| vectors | 2-D, 3-D, 4-D, and n-dimensional vectors |
| while | Semantics for the programming language While |
NASALib also provides a collection of scripts that automates several tasks.
proveit (*) - Runs PVS in batch modeprovethem (*) - Runs proveit on several librariespvsio (*) - Command-line utility to run the PVSio ground evaluator.prove-all - Runs proveit on each library
in NASALib by wrapping provethem in order to provide a specific kind of run.cleanbin-all - Clean .pvscontext and binary files from PVS libraries.find-all - Searches strings matching a given regular expressions in PVS libraries.dependencygraph - Generates a library dependency graph for libraries in the current directory.dependency-all - Generates the dependency graphs for the PVS libraries in the current folder.Click here for more details on these scripts.
(*) Already included in the PVS 7.1 distribution.
NASALib (v7.0.1) is fully compatible with VSCode-PVS, a modern graphical interface to PVS based on Visual Studio Code. The latest version of NASALib can be installed from VSCode-PVS.
For PVS advanced users, the development version is available from GitHub.
To clone the development version, type the following command inside directory where PVS 7.0 is installed. Henceforth, that directory will be referred to as
$ git clone http://github.com/nasa/pvslib nasalib The command above will put a copy of the library in the directory
The library groups is now deprecated. The group library was integrated into algebra . A symbolic link is still provided for backward compatibility, but its use is discouraged. Every mention to groups should be replaced by algebra.
The library trig_fnd is now deprecated. It's still provided for backward compatibility, but it should be replaced by trig. The new library trig, which used to be axiomatic, is now foundational. However, in contrast to trig_fnd, trigonometric definitions are based on infinite series, rather than integrals. This change considerably reduces the type-checking of theories involving trigonometric functions. The change from trig_fnd to trig should not have a major impact in your formal developments since names of definitions and lemmas are the same. However, theory importing may be slightly different.
The PVS developments TCASII, WellClear, and DAIDALUS are now available as part of the GitHub WellClear distribution. The PVS development PRECiSA is now available as part of the GitHub PRECiSA distribution. The PVS development PolyCARP is now available as part of the GitHub PolyCARP distribution.
The following instructions assume that NASALib is located in the directory
PVS_LIBRARY_PATHIf it does not exists, creates such variable and with the path of this directory as only content. It is usually very useful to have your shell systems creating this variable at startup. To this end, and depending upon your shell, you may want to add one of the following lines in your startup script. For C shell (csh or tcsh), you may add this line in ~/.cshrc:
setenv PVS_LIBRARY_PATH "/nasalib" For Borne shell (bash or sh), add this line in either ~/.bashrc or ~/.profile:
export PVS_LIBRARY_PATH="/nasalib" If you had a previous installation of NASALib, either remove the file ~/.pvs.lisp or, if you have a special configuration in that file, remove the following line
(load "/nasalib/pvs-patches.lisp" ) Finally, go to the directory
The install-scripts command will update and install NASALib scripts as needed.
$ ./install-scriptsOlder versions of NASALib are available from http://shemesh.larc.nasa.gov/fm/ftp/larc/PVS-library.
NASALib has grown over the years thanks to the contribution of several people, among them:
If we have incorrectly attributed a PVS development or you have contributed to NASALib and your name is not included here, please let us know.
If you want to contribute please read this guide.
NASALib is a collection of formal specifications most of
which have been in the public domain for several years. The Formal
Methods Team at NASA LaRC still
maintains these developments. For the developments originally made by
the Formal Methods Team, these
developments are considered fundamental research that do not
constitute software. Contributions made by others may have particular
licenses, which are listed in the file top.pvs in each
respective directory. In case of doubt, please contact the developers
of each contribution, which are also listed in that file.
PVS patches, which are included in the directory pvs-patches, are part of the
PVS source code and they are covered by the PVS open source license.
Some proof strategies require third party research tools, e.g., MetiTarski and Z3. For convenience, they are included in this repository with permission from their authors. Licenses for these tools are also included as appropriate.
Enjoy it.
The Formal Methods Team at LaRC
César Muñoz Mariano Moscato
