Cslib.LTS.MTr
inductiveimported Lean
Definition of a multistep transition. (Implementation note: compared to [Montesi2023], 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.)
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Cslib in universe u v in variable {State : Type u} {Label : Type v} (lts : LTS State Label) in @[grind, mk_iff] inductive Cslib.LTS.MTr (lts : LTS State Label) : State → List Label → State → Prop
- Defined in
- CSLib, `Cslib.LTS.MTr`
- Lean proof
- By Fabrizio Montesi, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2025 Fabrizio Montesi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Cslib.LTS.MTr← Cslib.LTS.MTr (Cslib/Foundations/Semantics/LTS/Basic.lean:91): adapted
What was changed in
Cslib.LTS.MTr--- Cslib/Foundations/Semantics/LTS/Basic.lean:91 (Cslib.LTS.MTr) +++ as compiled here @@ -1,10 +1,8 @@ -/-- -Definition of a multistep transition. - -(Implementation note: compared to [Montesi2023], 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.) --/ -@[scoped grind, mk_iff] -inductive MTr (lts : LTS State Label) : State → List Label → State → Prop where +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open Cslib in +universe u v in +variable {State : Type u} {Label : Type v} (lts : LTS State Label) in +@[grind, mk_iff] +inductive Cslib.LTS.MTr (lts : LTS State Label) : State → List Label → State → Prop where | refl {s : State} : lts.MTr s [] s - Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 1
- Cslib.LTSA Labelled Transition System (LTS) for a type of states (
State) and a type of transition labels (Label) consists of a labelled…
- Cslib.LTSA Labelled Transition System (LTS) for a type of states (
- Used by 30
- Cslib.LTS.MTr.splitA multistep transition over a concatenation can be split into two multistep transitions.
- Cslib.LTS.MTr.single_invertAny 1-sized multistep transition implies a transition with the same states and label.
- Cslib.LTS.transGen_unlabelledTr_iffThe transitive closure of the underlying unlabelled transition relation is exactly the nonempty multistep transitions of the LTS.
- Cslib.LTS.MTr.toRelationReturns the relation that relates all states
s1ands2via a fixed list of transition labelsμs. - Cslib.LTS.Execution.to_mTrConverts an execution into a multistep transition.
- Cslib.LTS.MTr.stepRAny multistep transition can be extended by adding a transition.
- Cslib.LTS.Acyclic.toBoundedUpToOn a finite state space, an acyclic LTS has execution length strictly less than the number of states.
- Cslib.LTS.MTr.nil_iffCslib.LTS.MTr.nil_iff
- Cslib.LTS.reflTransGen_unlabelledTr_iffThe reflexive-transitive closure of the underlying unlabelled transition relation is exactly reachability in the LTS.
- Cslib.LTS.Example.countdownLTS_mTrCslib.LTS.Example.countdownLTS_mTr
- Cslib.LTS.mtrInv_of_trInvAny single-step invariant is also a multistep invariant.
- Cslib.LTS.MTr.singleAny transition is also a multistep transition.
- Cslib.LTS.MTr.toTransGenA nonempty multistep transition induces a nonempty path in the underlying unlabelled transition relation.
- Cslib.LTS.MTr.compMultistep transitions can be composed.
- Cslib.LTS.totalize.nonsink_mtr_iffIn
totalize, the multistep transitions between non-sink states correspond exactly to the multistep transitions in the original LTS. - Cslib.LTS.CanReachA state
s1can reach a states2if there exists a multistep transition froms1tos2. - Cslib.LTS.MTr.append_iffMultistep-transitions over
μs ++ μs'are exactly multistep transitions overμsandμs'with a common end & start state (respectively). - Cslib.LTS.MTr.toReflTransGenA multistep transition induces a reflexive-transitive path in the underlying unlabelled transition relation.
- Cslib.Automata.NA.FinAcc.instAcceptorAn
NA.FinAccaccepts a string if there is a multistep transition from a start state to an accept state. This is the standard string… - Cslib.LTS.Deterministic.eq_of_mTrIn a deterministic lts, multistep transitions with a given start state and trace reach a unique end state.
- Cslib.LTS.imageMultistepThe
μs-image of a states, whereμsis a list of labels, is the set of allμs-derivatives ofs. - Cslib.LTS.MTr.nil_eqIn any zero-steps multistep transition, the origin and the derivative are the same.
- Cslib.LTS.Execution.of_mTrA multistep transition implies the existence of an execution.
- Cslib.LTS.MTr.cons_iffA multistep transition along
μ :: μsis a transition labelled byμplus a multistep transition labelled byμs. - Cslib.LTS.MTr.singleton_iffA 1-sized multistep transition is exactly a single transition with the given label.
- Cslib.LTS.mem_setImageMultistepCharacterisation of
setImageMultistepwithMTr. - Cslib.LTS.BoundedUpToAn LTS is bounded up to
nif every finite execution has length strictly less thann. - Cslib.LTS.CanReach.reflAny state can reach itself.
- Cslib.LTS.MTrInvMultistep invariant.
- Cslib.LTS.totalize.no_sink_to_nonsinkIn
totalize, there is no finite execution from the sink state to any non-sink state.
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Cslib in universe u v in variable {State : Type u} {Label : Type v} (lts : LTS State Label) in /-- Definition of a multistep transition. (Implementation note: compared to [Montesi2023], 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.) -/ @[grind, mk_iff] inductive Cslib.LTS.MTr (lts : LTS State Label) : State → List Label → State → Prop where | refl {s : State} : lts.MTr s [] s | stepL {s1 : State} {μ : Label} {s2 : State} {μs : List Label} {s3 : State} : lts.Tr s1 μ s2 → lts.MTr s2 μs s3 → lts.MTr s1 (μ :: μs) s3