Rust Model Checker for Finite State Systems

This challenge asks you to implement a basic model checker in Rust. Model checking is a crucial technique in formal verification, used to automatically prove or disprove properties about a system's design. We'll focus on checking properties for finite state systems, which are commonly represented as state transition systems.

Problem Description

You need to build a Rust program that can model a finite state system and check if a given temporal logic property holds true for that system.

The finite state system will be defined by:

1. States: A finite set of unique states.
2. Initial States: A subset of states from which the system can start.
3. Transitions: A function or set of rules defining how the system can move from one state to another.
4. State Labels: Each state is associated with a set of atomic propositions that are true in that state.

The temporal logic property to be checked will be expressed in a simplified linear temporal logic (LTL).

Key Requirements:

• State Representation: You should be able to represent states, initial states, transitions, and state labels.
• Temporal Logic Syntax: Implement a parser or a way to represent the following temporal logic operators:
  • Atomic Propositions: Simple boolean variables (e.g., "p", "q").
  • Negation: !P (NOT P)
  • Conjunction: P & Q (P AND Q)
  • Disjunction: P | Q (P OR Q)
  • Always (Globally): G P (Globally P - P holds now and in all future states)
  • Eventually (Future): F P (Finally P - P will hold at some point in the future, including the current state)
  • Next: X P (Next P - P will hold in the next state)
  • Until: P U Q (P Until Q - P holds until Q becomes true, and Q must eventually become true)
• Model Checking Algorithm: Implement a model checking algorithm (e.g., Buchi automaton based or directly state-space exploration for LTL) to determine if the property holds in all reachable states from the initial states.
• Output: The program should output true if the property holds for the entire system and false otherwise.

Expected Behavior:

The model checker should systematically explore all reachable states from the initial states. For each reachable state, it should evaluate the truth of the temporal logic property. If the property is found to be false in any reachable state, the model checker should report false. If the property holds in all reachable states, it should report true.

Edge Cases to Consider:

• Systems with no initial states.
• Systems with cyclic transitions.
• Properties that are trivially true or false.
• Properties involving complex combinations of temporal operators.
• Infinite paths (though for finite state systems, all paths are ultimately cyclic, so we are concerned with properties holding along all such paths).

Examples

Example 1: Simple Latch

System Definition:

• States: s0, s1
• Initial States: s0
• Transitions:
  • s0 -> s1
  • s1 -> s0
• State Labels:
  • s0: {"p"}
  • s1: {"q"}

Temporal Logic Property: G (p | q) (Globally, in every state, either 'p' or 'q' is true)

Input:

System:
  States: [s0, s1]
  Initial: [s0]
  Transitions:
    s0 -> s1
    s1 -> s0
  Labels:
    s0: [p]
    s1: [q]

Property: G (p | q)

Output:

true

Explanation: From the initial state s0, 'p' is true, so p | q is true. The system transitions to s1, where 'q' is true, so p | q is also true. The system then cycles back to s0. Since p | q holds in both reachable states (s0 and s1), the property G (p | q) holds globally.

Example 2: Deadlock Scenario

System Definition:

• States: idle, busy, error
• Initial States: idle
• Transitions:
  • idle -> busy
  • busy -> idle
  • busy -> error
• State Labels:
  • idle: {}
  • busy: {"processing"}
  • error: {}

Temporal Logic Property: !F error (It is not eventually the case that the system enters the 'error' state)

Input:

System:
  States: [idle, busy, error]
  Initial: [idle]
  Transitions:
    idle -> busy
    busy -> idle
    busy -> error
  Labels:
    idle: []
    busy: [processing]
    error: []

Property: !F error

Output:

false

Explanation: The system starts in idle. It can transition to busy. From busy, it can transition to error. Since there is a path (idle -> busy -> error) that leads to the error state, the property F error (eventually error) is true. Therefore, !F error is false.

Example 3: Property with 'Until'

System Definition:

• States: a, b, c, d
• Initial States: a
• Transitions:
  • a -> b
  • b -> c
  • c -> d
  • d -> b (cycle)
• State Labels:
  • a: {}
  • b: {"x"}
  • c: {"y"}
  • d: {}

Temporal Logic Property: x U y (x holds until y becomes true)

Input:

System:
  States: [a, b, c, d]
  Initial: [a]
  Transitions:
    a -> b
    b -> c
    c -> d
    d -> b
  Labels:
    a: []
    b: [x]
    c: [y]
    d: []

Property: x U y

Output:

true

Explanation: The initial state a does not satisfy x. The system moves to b, where x is true. The system then moves to c, where y is true. At this point, y has become true, and x held true in the preceding states (b). Therefore, x U y holds. The subsequent states (d and the cycle back to b) do not invalidate the property because y has already become true.

Constraints

• The number of states in the system will be between 1 and 50.
• The number of atomic propositions will be at most 10.
• The length of the temporal logic formula will be at most 20 operators/propositions.
• The state labels are unique to each state.
• All transitions are deterministic (one outgoing transition from a given state leads to a specific state).
• The temporal logic formula will be well-formed.

Notes

• You will likely need to implement a way to parse the temporal logic formula into an internal representation (e.g., an Abstract Syntax Tree or AST).
• For model checking, consider algorithms like the basic explicit-state model checking approach, which involves exploring the state space using a worklist or queue.
• Handling the temporal operators, especially U (Until), requires careful implementation to ensure correctness. The P U Q property means P must hold in all states from the current state up to, but not including, the state where Q first holds, and Q must eventually hold.
• You might find it helpful to represent states as integers or strings and use a HashMap or similar data structure to manage state labels and transitions.
• The definition of G P is that P must hold in the current state and all subsequent states.
• The definition of F P is that P must hold in the current state or some future state.
• The definition of X P is that P must hold in the immediately next state.