Labelled Transition System

A Labelled Transition System (LTS) models the observable behaviour of the possible states of a system. They are particularly popular in the fields of concurrency theory, logic, and programming languages.

Main definitions

• LTS is a structure for labelled transition systems, consisting of a labelled transition relation tr between states. We follow the style and conventions in [San].

• lts.mtr extends the transition relation of any LTS to a multi-step transition relation, formalising the inference system and admissible rules for such relations in [Mon23].

• Definitions for all the common classes of LTSs: image-finite, finitely branching, finite-state, finite, and deterministic.

Main statements

• A series of results on lts.mtr that allow for obtaining and composing multi-step transitions in different ways.

• LTS.deterministic_imageFinite: every deterministic LTS is also image-finite.

• LTS.finiteState_imageFinite: every finite-state LTS is also image-finite.

• LTS.finiteState_finitelyBranching: every finite-state LTS is also finitely-branching, if the type of labels is finite.

References

• [F. Montesi, Introduction to Choreographies] [Mon23]
• [D. Sangiorgi, Introduction to Bisimulation and Coinduction] [San]

structure LTS (State : Type u) (Label : Type v) : Type (max u v)

A Labelled Transition System (LTS) consists of a type of states (State), a type of transition labels (Label), and a labelled transition relation (tr).

• tr : State → Label → State → Prop

  The transition relation.

def LTS.toRel {State : Type u_1} {Label : Type u_2} (lts : LTS State Label) (μ : Label) : Rel State State

Given an lts and a transition label μ, returns the relation that relates all states s1 and s2 such that lts.tr s1 μ s2.

This can be useful, for example, to see a reduction relation as an LTS.

Equations

• lts.toRel μ s1 s2 = lts.tr s1 μ s2

def Rel.toLTS {Label : Type u_1} {State : Type u_2} [DecidableEq Label] (r : Rel State State) (μ : Label) : LTS State Label

Any homogeneous relation can be seen as an LTS where all transitions have the same label.

Equations

• r.toLTS μ = { tr := fun (s1 : State) (μ' : Label) (s2 : State) => if μ' = μ then r s1 s2 else False }

Multi-step transitions

inductive LTS.mtr {State : Type u} {Label : Type v} (lts : LTS State Label) : State → List Label → State → Prop

Definition of a multi-step transition.

(Implementation note: compared to [Mon23], we choose stepL instead of stepR as fundamental rule. This makes working with lists of labels more convenient, because we follow the same construction. It is also similar to what is done in the SimpleGraph library in mathlib.)

• refl {State : Type u} {Label : Type v} {lts : LTS State Label} {s : State} : lts.mtr s [] s
• stepL {State : Type u} {Label : Type v} {lts : LTS State Label} {s1 : State} {μ : Label} {s2 : State} {μs : List Label} {s3 : State} : lts.tr s1 μ s2 → lts.mtr s2 μs s3 → lts.mtr s1 (μ :: μs) s3

theorem LTS.mtr.single {State : Type u} {Label : Type v} (lts : LTS State Label) {s1 : State} {μ : Label} {s2 : State} : lts.tr s1 μ s2 → lts.mtr s1 [μ] s2

Any transition is also a multi-step transition.

theorem LTS.mtr.stepR {State : Type u} {Label : Type v} (lts : LTS State Label) {s1 : State} {μs : List Label} {s2 : State} {μ : Label} {s3 : State} : lts.mtr s1 μs s2 → lts.tr s2 μ s3 → lts.mtr s1 (μs ++ [μ]) s3

Any multi-step transition can be extended by adding a transition.

theorem LTS.mtr.comp {State : Type u} {Label : Type v} (lts : LTS State Label) {s1 : State} {μs1 : List Label} {s2 : State} {μs2 : List Label} {s3 : State} : lts.mtr s1 μs1 s2 → lts.mtr s2 μs2 s3 → lts.mtr s1 (μs1 ++ μs2) s3

Multi-step transitions can be composed.

theorem LTS.mtr.single_invert {State : Type u} {Label : Type v} (lts : LTS State Label) (s1 : State) (μ : Label) (s2 : State) : lts.mtr s1 [μ] s2 → lts.tr s1 μ s2

Any 1-sized multi-step transition implies a transition with the same states and label.

theorem LTS.mtr.nil_eq {State : Type u} {Label : Type v} (lts : LTS State Label) {s1 s2 : State} (h : lts.mtr s1 [] s2) : s1 = s2

In any zero-steps multi-step transition, the origin and the derivative are the same.

def LTS.CanReach {State : Type u} {Label : Type v} (lts : LTS State Label) (s1 s2 : State) : Prop

A state s1 can reach a state s2 if there exists a multi-step transition from s1 to s2.

Equations

• lts.CanReach s1 s2 = ∃ (μs : List Label), lts.mtr s1 μs s2

theorem LTS.CanReach.refl {State : Type u} {Label : Type v} (lts : LTS State Label) (s : State) : lts.CanReach s s

Any state can reach itself.

def LTS.generatedBy {State : Type u} {Label : Type v} (lts : LTS State Label) (s : State) : LTS { s' : State // lts.CanReach s s' } Label

The LTS generated by a state s is the LTS given by all the states reachable from s.

Equations

• One or more equations did not get rendered due to their size.

Definitions about termination

def LTS.MayTerminate {State : Type u_1} {Label : Type u_2} (lts : LTS State Label) {Terminated : State → Prop} (s : State) : Prop

A state 'may terminate' if it can reach a terminated state. The definition of Terminated is a parameter.

Equations

• lts.MayTerminate s = ∃ (s' : State), Terminated s' ∧ lts.CanReach s s'

def LTS.Stuck {State : Type u_1} {Label : Type u_2} (lts : LTS State Label) {Terminated : State → Prop} (s : State) : Prop

A state 'is stuck' if it is not terminated and cannot go forward. The definition of Terminated is a parameter.

Equations

• lts.Stuck s = (¬Terminated s ∧ ¬∃ (μ : Label) (s' : State), lts.tr s μ s')

Definitions for the unions of LTSs

Note: there is a nontrivial balance between ergonomics and generality here. These definitions might change in the future.

def LTS.unionSubtype {State : Type u} {Label : Type v} {S1 : State → Prop} {L1 : Label → Prop} {S2 : State → Prop} {L2 : Label → Prop} [DecidablePred S1] [DecidablePred L1] [DecidablePred S2] [DecidablePred L2] (lts1 : LTS (Subtype S1) (Subtype L1)) (lts2 : LTS (Subtype S2) (Subtype L2)) : LTS State Label

The union of two LTSs that have common supertypes for states and labels.

Equations

• One or more equations did not get rendered due to their size.

def Sum.isLeftP {α : Type u_1} {β : Type u_2} (x : α ⊕ β) : Prop

TODO: move this to Sum?

Equations

• x.isLeftP = (x.isLeft = true)

def Sum.isRightP {α : Type u_1} {β : Type u_2} (x : α ⊕ β) : Prop

TODO: move this to Sum?

Equations

• x.isRightP = (x.isRight = true)

def LTS.inl {State : Type u} {Label : Type v} {State' : Type u_1} (lts : LTS State Label) : LTS (Subtype Sum.isLeftP) (Subtype (Function.const Label True))

Lifting of an LTS State Label to LTS (State ⊕ State') Label.

Equations

• One or more equations did not get rendered due to their size.

def LTS.inr {State : Type u} {Label : Type v} {State' : Type u_1} (lts : LTS State Label) : LTS (Subtype Sum.isRightP) (Subtype (Function.const Label True))

Lifting of an LTS State Label to LTS (State' ⊕ State) Label.

Equations

• One or more equations did not get rendered due to their size.

def LTS.unionSum {Label : Type v} {State1 : Type u_1} {State2 : Type u_2} (lts1 : LTS State1 Label) (lts2 : LTS State2 Label) : LTS (State1 ⊕ State2) Label

Union of two LTSs with the same Label type. The result combines the original respective state types State1 and State2 into (State1 ⊕ State2).

Equations

• lts1.unionSum lts2 = lts1.inl.unionSubtype lts2.inr

Classes of LTSs

def LTS.Deterministic {State : Type u} {Label : Type v} (lts : LTS State Label) : Prop

An lts is deterministic if a state cannot reach different states with the same transition label.

Equations

• lts.Deterministic = ∀ (s1 : State) (μ : Label) (s2 s3 : State), lts.tr s1 μ s2 → lts.tr s1 μ s3 → s2 = s3

def LTS.Image {State : Type u} {Label : Type v} (lts : LTS State Label) (s : State) (μ : Label) : Set State

The μ-image of a state s is the set of all μ-derivatives of s.

Equations

• lts.Image s μ = {s' : State | lts.tr s μ s'}

def LTS.ImageFinite {State : Type u} {Label : Type v} (lts : LTS State Label) : Prop

An lts is image-finite if all images of its states are finite.

Equations

• lts.ImageFinite = ∀ (s : State) (μ : Label), Finite ↑(lts.Image s μ)

theorem LTS.deterministic_not_lto {State : Type u} {Label : Type v} (lts : LTS State Label) (hDet : lts.Deterministic) (s : State) (μ : Label) (s' s'' : State) : s' ≠ s'' → lts.tr s μ s' → ¬lts.tr s μ s''

In a deterministic LTS, if a state has a μ-derivative, then it can have no other μ-derivative.

theorem LTS.deterministic_image_char {State : Type u} {Label : Type v} (lts : LTS State Label) (hDet : lts.Deterministic) (s : State) (μ : Label) : (∃ (s' : State), lts.Image s μ = {s'}) ∨ lts.Image s μ = ∅

In a deterministic LTS, any image is either a singleton or the empty set.

theorem LTS.deterministic_imageFinite {State : Type u} {Label : Type v} (lts : LTS State Label) : lts.Deterministic → lts.ImageFinite

Every deterministic LTS is also image-finite.

def LTS.HasOutLabel {State : Type u} {Label : Type v} (lts : LTS State Label) (s : State) (μ : Label) : Prop

A state has an outgoing label μ if it has a μ-derivative.

Equations

• lts.HasOutLabel s μ = ∃ (s' : State), lts.tr s μ s'

def LTS.OutgoingLabels {State : Type u} {Label : Type v} (lts : LTS State Label) (s : State) : Set Label

The set of outgoing labels of a state.

Equations

• lts.OutgoingLabels s = {μ : Label | lts.HasOutLabel s μ}

def LTS.FinitelyBranching {State : Type u} {Label : Type v} (lts : LTS State Label) : Prop

An LTS is finitely branching if it is image-finite and all states have finite sets of outgoing labels.

Equations

• lts.FinitelyBranching = (lts.ImageFinite ∧ ∀ (s : State), Finite ↑(lts.OutgoingLabels s))

def LTS.FiniteState {State : Type u} {Label : Type v} : LTS State Label → Prop

An LTS is finite-state if it has a finite State type.

Equations

• x✝.FiniteState = Finite State

theorem LTS.finiteState_imageFinite {State : Type u} {Label : Type v} (lts : LTS State Label) (hFinite : lts.FiniteState) : lts.ImageFinite

Every finite-state LTS is also image-finite.

theorem LTS.finiteState_finitelyBranching {State : Type u} {Label : Type v} (lts : LTS State Label) (hFiniteLabel : _root_.Finite Label) (hFiniteState : lts.FiniteState) : lts.FinitelyBranching

Every LTS with finite types for states and labels is also finitely branching.

def LTS.Acyclic {State : Type u} {Label : Type v} (lts : LTS State Label) : Prop

An LTS is acyclic if there are no infinite multi-step transitions.

Equations

• lts.Acyclic = ∃ (n : ℕ), ∀ (s1 : State) (μs : List Label) (s2 : State), lts.mtr s1 μs s2 → μs.length < n

def LTS.Finite {State : Type u} {Label : Type v} (lts : LTS State Label) : Prop

An LTS is finite if it is finite-state and acyclic.

Equations

• lts.Finite = (lts.FiniteState ∧ lts.Acyclic)

Weak transitions (single- and multi-step)

class HasTau (Label : Type v) : Type v

A type of transition labels that includes a special 'internal' transition τ.

• τ : Label

inductive LTS.str {Label : Type u_1} {State : Type u_2} [HasTau Label] (lts : LTS State Label) : State → Label → State → Prop

Saturated transition relation.

• refl {Label : Type u_1} {State : Type u_2} [HasTau Label] {lts : LTS State Label} {s : State} : lts.str s HasTau.τ s
• tr {Label : Type u_1} {State : Type u_2} [HasTau Label] {lts : LTS State Label} {s1 s2 : State} {μ : Label} {s3 s4 : State} : lts.str s1 HasTau.τ s2 → lts.tr s2 μ s3 → lts.str s3 HasTau.τ s4 → lts.str s1 μ s4

def LTS.saturate {Label : Type u_1} {State : Type u_2} [HasTau Label] (lts : LTS State Label) : LTS State Label

The LTS obtained by saturating the transition relation in lts.

Equations

• lts.saturate = { tr := lts.str }

theorem LTS.str.single {Label : Type u_1} {State : Type u_2} {s : State} {μ : Label} {s' : State} [HasTau Label] (lts : LTS State Label) : lts.tr s μ s' → lts.str s μ s'

Any transition is also a saturated transition.

inductive LTS.strN {Label : Type u_1} {State : Type u_2} [HasTau Label] (lts : LTS State Label) : ℕ → State → Label → State → Prop

As LTS.str, but counts the number of τ-transitions. This is convenient as induction metric.

• refl {Label : Type u_1} {State : Type u_2} [HasTau Label] {lts : LTS State Label} {s : State} : lts.strN 0 s HasTau.τ s
• tr {Label : Type u_1} {State : Type u_2} [HasTau Label] {lts : LTS State Label} {n : ℕ} {s1 s2 : State} {μ : Label} {s3 : State} {m : ℕ} {s4 : State} : lts.strN n s1 HasTau.τ s2 → lts.tr s2 μ s3 → lts.strN m s3 HasTau.τ s4 → lts.strN (n + m + 1) s1 μ s4

theorem LTS.str_strN {Label : Type u_1} {State : Type u_2} {s1 : State} {μ : Label} {s2 : State} [HasTau Label] (lts : LTS State Label) : lts.str s1 μ s2 ↔ ∃ (n : ℕ), lts.strN n s1 μ s2

LTS.str and LTS.strN are equivalent.

@[irreducible]

theorem LTS.strN.trans_τ {Label : Type u_1} {State : Type u_2} {n : ℕ} {s1 s2 : State} {m : ℕ} {s3 : State} [HasTau Label] (lts : LTS State Label) (h1 : lts.strN n s1 HasTau.τ s2) (h2 : lts.strN m s2 HasTau.τ s3) : lts.strN (n + m) s1 HasTau.τ s3

Saturated transitions labelled by τ can be composed (weighted version).

theorem LTS.str.trans_τ {Label : Type u_1} {State : Type u_2} {s1 s2 s3 : State} [HasTau Label] (lts : LTS State Label) (h1 : lts.str s1 HasTau.τ s2) (h2 : lts.str s2 HasTau.τ s3) : lts.str s1 HasTau.τ s3

Saturated transitions labelled by τ can be composed.

theorem LTS.strN.append {Label : Type u_1} {State : Type u_2} {n1 : ℕ} {s1 : State} {μ : Label} {s2 : State} {n2 : ℕ} {s3 : State} [HasTau Label] (lts : LTS State Label) (h1 : lts.strN n1 s1 μ s2) (h2 : lts.strN n2 s2 HasTau.τ s3) : lts.strN (n1 + n2) s1 μ s3

Saturated transitions can be appended with τ-transitions (weighted version).

theorem LTS.strN.comp {Label : Type u_1} {State : Type u_2} {n1 : ℕ} {s1 s2 : State} {n2 : ℕ} {μ : Label} {s3 : State} {n3 : ℕ} {s4 : State} [HasTau Label] (lts : LTS State Label) (h1 : lts.strN n1 s1 HasTau.τ s2) (h2 : lts.strN n2 s2 μ s3) (h3 : lts.strN n3 s3 HasTau.τ s4) : lts.strN (n1 + n2 + n3) s1 μ s4

Saturated transitions can be composed (weighted version).

theorem LTS.str.comp {Label : Type u_1} {State : Type u_2} {s1 s2 : State} {μ : Label} {s3 s4 : State} [HasTau Label] (lts : LTS State Label) (h1 : lts.str s1 HasTau.τ s2) (h2 : lts.str s2 μ s3) (h3 : lts.str s3 HasTau.τ s4) : lts.str s1 μ s4

Saturated transitions can be composed.

Divergence

def LTS.DivergentExecution {Label : Type u_1} {State : Type u_2} [HasTau Label] (lts : LTS State Label) (stream : Stream' State) : Prop

A divergent execution is a stream of states where each state is the anti-τ-derivative of the next.

Equations

• lts.DivergentExecution stream = ∀ (n : ℕ), lts.tr (stream n) HasTau.τ (stream n.succ)

def LTS.Divergent {Label : Type u_1} {State : Type u_2} [HasTau Label] (lts : LTS State Label) (s : State) : Prop

A state is divergent if there is a divergent execution from it.

Equations

• lts.Divergent s = ∃ (stream : Stream' State), stream 0 = s ∧ lts.DivergentExecution stream

theorem LTS.divergent_drop {Label : Type u_1} {State : Type u_2} [HasTau Label] (lts : LTS State Label) (stream : Stream' State) (h : lts.DivergentExecution stream) (n : ℕ) : lts.DivergentExecution (Stream'.drop n stream)

If a stream is a divergent execution, then any 'suffix' is also a divergent execution.

def LTS.DivergenceFree {Label : Type u_1} {State : Type u_2} [HasTau Label] (lts : LTS State Label) : Prop

An LTS is divergence-free if it has no divergent state.

Equations

• lts.DivergenceFree = ¬∃ (s : State), lts.Divergent s