LTLModelChecking

An implementation of a classical algorithm for verification of linear temporal logic. Assignment for CS3959, Model Checking, ACM Class.

Requirements

Antlr4

pip3 install antlr4-python3-runtime  

Run

python3 src/main.py

Implementation Details

Parser

Under src/parser is the grammar file LTL.g4 and the generated parser LTLParser.py. The parser is generated by Antlr4. We use the visitor pattern to traverse the LTL formula parse tree. While traversing, we build the corresponding syntax tree and perform some equivalence transformations to simplify the formula. Details can be found in src/parser/LTLEvalVisitor.py.

Construct GNBA

Under src/Automata is the implementation of all automata. We use the algorithm in Theorem 5.37 (page 278 of Principles of Model Checking) to construct the GNBA. Details can be found in src/Automata/GNBA.py.

Construct NBA

We use Theorem 4.56 (page 195 of Principles of Model Checking) to construct the NBA. Details can be found in src/Automata/NBA.py.

Construct cross product for NBA and original Transition System

We use Definition 4.62 (page 200 of Principles of Model Checking) to construct cross product for NBA and original Transition System. Details can be found in src/TS/TransitionSystem.py::initFromProduct.

Persistence checking

We use Algorithm 7 & 8 (page 210 of Principles of Model Checking) to perform persistence checking. Details can be found in src/TS/TransitionSystem.py::persistenceChecking.