Translations from LTL to Büchi automata

Translations from LTL to Büchi automata

Learning scenarios

Some tools:

• LTL2BA www.lsv.fr/~gastin/ltl2ba by Paul Gastin & Denis Oddoux

(simple,

does not always give a pruned automaton)

• Rabinizer 4 https://www7.in.tum.de/~kretinsk/rabinizer4.html by Jan Kretinsky, Tobias Meggendorfer, Salomon Sickert (et al.)

(more efficient,

supports several types of automata: Büchi, Generalised Büchi, Rabin, parity, deterministic, non-deterministic, …

uses acceptance conditions on transitions rather than on states)

Simple (inefficient) translation from LTL

LTL vocabulary Propositional letters:            Σ = {p, q, r, …}

Boolean connectives:        ∨, ∧, ¬, →, Modal operators:        F, G, U, X

Syntax φ :     p | (for all p ∈ Σ) φ ∨ φ   |   φ ∧ φ   |   ¬φ   |   φ → φ   |   φ φ F φ | G φ | φ U φ | X φ

Goal: translate φ to an automaton Aφ s.t. L(Aφ) = { w ∈ ℘(Σ)^ω | w ⊨ φ }

Simple (inefficient) translation from LTL

Goal: translate φ to an automaton Aφ s.t. L(Aφ) = { w ∈ ℘(Σ)^ω | w ⊨ φ }

State of Aφ  any set P ⊆ cl(φ) such that

• α ∈ P iff ¬α ∉ P

• α ∧ β ∈ P iff α, β ∈ P, etc…

• F α ∈ P iff α ∈ P or X F α ∈ P

• G α ∈ P iff α ∈ P and X G α ∈ P

• α Uβ ∈ P iff β ∈ P or {α, X (α U β )} ⊆ P (P initial if φ ∈ P)

(= tableau atom)

Expanded closure of φ   cl(φ) = smallest set of formulas such that

• φ ∈ cl(φ)

• if α ∈ cl(φ) and β subformula of α, then β ∈ cl(φ)

• if α ∈ cl(φ), then ¬α ∈ cl(φ) (¬¬ β becomes β)

• if α ∈ cl(φ) ∩ { F…, G…, …U…}, then X α ∈ cl(φ)

Simple (inefficient) translation from LTL

Transition of Aφ  P —S—> P’ when

• p ∈ P p ∈ S for all p ∈ Σ ∩ cl(φ)

• X α ∈ P α ∈ P’ for all X α ∈ cl(φ) (= tableau edge)

Goal: translate φ to an automaton Aφ s.t. L(Aφ) = { w ∈ ℘(Σ)^ω | w ⊨ φ }

State of Aφ  any set P ⊆ cl(φ) such that

• α ∈ P iff ¬α ∉ P

• α ∧ β ∈ P iff α, β ∈ P, etc…

• F α ∈ P iff α ∈ P or X F α ∈ P

• G α ∈ P iff α ∈ P and X G α ∈ P

• α U β ∈ P iff β ∈ P or {α, X (α U β )} ⊆ P (P initial if φ ∈ P)

(= tableau atom)

Simple (inefficient) translation from LTL

Acceptance of Aφ:  For every α ∈ { F β, γ U β } ∩ cl(φ)

there is a state Pα that is α-fulfilling (i.e. α ∈ Pα → β ∈ Pα) and that is visited infinitely often

(= tableau acceptance)

Transition of Aφ  P —S—> P’ when

• p ∈ P p ∈ S for all p ∈ Σ ∩ cl(φ)

• X α ∈ P α ∈ P’ for all X α ∈ cl(φ) (= tableau edge)

Goal: translate φ to an automaton Aφ s.t. L(Aφ) = { w ∈ ℘(Σ)^ω | w ⊨ φ } State of Aφ  any set P ⊆ cl(φ) such that

• α ∈ P iff ¬α ∉ P

• α ∧ β ∈ P iff α, β ∈ P, etc…

• F α ∈ P iff α ∈ P or X F α ∈ P

• G α ∈ P iff α ∈ P and X G α ∈ P

• α U β ∈ P iff β ∈ P or {α, X (α U β )} ⊆ P (P initial if φ ∈ P)

(= tableau atom)

Simple (inefficient) translation from LTL

Generalised Büchi enforcing In(ρ) ∩ F ≠ ∅ for all F ∈ F

F = { F^α | α ∈ … } where Fα = { α-fulfilling states } Muller condition enforcing In(ρ) = F for some F ∈ F

F = { F ⊆ States | ∀ α ∈ … ∃ P^α ∈ F s.t. Pα α-fulfilling } Acceptance of Aφ:  For every α ∈ { F β, γ U β } ∩ cl(φ)

there is a state Pα that is α-fulfilling (i.e. α ∈ Pα → β ∈ Pα) and that is visited infinitely often

(= tableau acceptance)

Goal: translate φ to an automaton Aφ s.t. L(Aφ) = { w ∈ ℘(Σ)^ω | w ⊨ φ }

Büchi enforcing In(ρ) ∩ F ≠ ∅

similar to closure under intersection (on the tablet…)