Cslib.LTS
structureimported Lean
A Labelled Transition System (LTS) for a type of states (State) and a type of transition labels (Label) consists of a labelled transition relation (Tr).
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in universe u v in @[ext] structure Cslib.LTS (State : Type u) (Label : Type v)
- Defined in
- CSLib, `Cslib.LTS`
- 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← Cslib.LTS (Cslib/Foundations/Semantics/LTS/Basic.lean:64): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 102
- Cslib.LTS.deterministic_not_ltoIn a deterministic LTS, if a state has a
μ-derivative, then it can have no otherμ-derivative. - Cslib.Automata.NA.addHistThe construction of adding a history state. Note that
start'can depend on the initial value of the original state andtr'can depend… - Cslib.LTS.Morphism.idThe identity LTS morphism.
- Cslib.LTS.MTr.splitA multistep transition over a concatenation can be split into two multistep transitions.
- Cslib.LTS.setImageMultistepThe
μs-image of a set of statesS, whereμsis a list of labels, is the union of allμs-images of the states inS. - Cslib.LTS.Example.successorLTS_transGen_ltCslib.LTS.Example.successorLTS_transGen_lt
- Cslib.LTS.MTrDefinition of a multistep transition. (Implementation note: compared to [Montesi2023], we choose stepL instead of stepR as fundamental…
- Cslib.LTS.Execution
ExecutionextendsMTrby providing the intermediate states of a multistep transition. - Cslib.Automata.NA.BuchiNondeterministic Buchi automaton.
- Cslib.LTS.Execution.cons_invertDeconstruction of executions with
List.cons. - 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.totalize.nonsink_tr_iffIn
totalize, the transitions between non-sink states correspond exactly to the transitions in the original LTS. - Cslib.LTS.MTr.toRelationReturns the relation that relates all states
s1ands2via a fixed list of transition labelsμs. - Cslib.LTS.Example.countdownLTSThe countdown LTS takes a natural number to its predecessor.
- Cslib.LTS.Execution.to_mTrConverts an execution into a multistep transition.
- Cslib.LTS.finiteState_imageFiniteEvery finite-state LTS is also image-finite.
- 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.TrInvSingle-step invariant.
- Cslib.LTS.TerminatingAn LTS is terminating if its underlying unlabelled transition relation is terminating, equivalently if it admits no infinite execution.
- Cslib.Automata.NA.totalize
NA.totalizemakes the original NA total by replacing its LTS withLTS.totalizeand its starting states with their lifted non-sink… - Cslib.LTS.generatedByThe LTS generated by a state
sis the LTS given by all the states reachable froms. - Cslib.LTS.reflTransGen_unlabelledTr_iffThe reflexive-transitive closure of the underlying unlabelled transition relation is exactly reachability in the LTS.
- Cslib.LTS.MayTerminateA state 'may terminate' if it can reach a terminated state. The definition of
Terminatedis a parameter. - Cslib.LTS.Example.countdownLTS_mTrCslib.LTS.Example.countdownLTS_mTr
- Cslib.LTS.mtrInv_of_trInvAny single-step invariant is also a multistep invariant.
- Cslib.LTS.mapLabel_trCslib.LTS.mapLabel_tr
- Cslib.LTS.StuckA state 'is stuck' if it is not terminated and cannot go forward. The definition of
Terminatedis a parameter. - Cslib.LTS.setImageThe
μ-image of a set of statesSis the union of allμ-images of the states inS. - Cslib.LTS.Execution.isChainThe states visited by an execution form a chain in the underlying unlabelled relation.
- Cslib.LTS.Acyclic.toBoundedOn a finite state space, acyclic LTSs are bounded.
- Cslib.LTS.Total.chooseFLTSThe FLTS chosen by
chooseFLTSalways provides legal transitions. - Cslib.LTS.MTr.singleAny transition is also a multistep transition.
- Cslib.LTS.instTotalOptionTotalizeThe LTS constructed by
totalizeis indeed total. - Cslib.LTS.Example.selfLoopLTS_not_acyclicThe self-loop LTS is not acyclic.
- 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.Morphism.compComposition of LTS morphisms. We use Kleisli composition to define this.
- 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.Execution.nonEmpty_statesEvery execution has at least one intermediate state.
- Cslib.FLTS.toLTS_tr
FLTS.toLTScorrectly characterises transitions. - Cslib.LTS.unionThe union of two LTSs defined on the same types.
- Cslib.LTS.CanReachA state
s1can reach a states2if there exists a multistep transition froms1tos2. - Cslib.LTS.unionSubtypeThe union of two LTSs that have common supertypes for states and labels.
- Cslib.instCategoryLTSCatFinally, we prove that these form a category.
- 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.outgoingLabelsThe set of outgoing labels of a state.
- Cslib.LTS.Example.countdownLTS_terminatingCslib.LTS.Example.countdownLTS_terminating
- Cslib.LTS.deterministic_tr_image_singletonCslib.LTS.deterministic_tr_image_singleton
- Cslib.FLTS.toLTS
FLTSis a special case ofLTS. - Cslib.LTS.DeterministicAn lts is deterministic if a state cannot reach different states with the same transition label.
- Cslib.LTS.TotalAn LTS is total iff every state has a
μ-derivative for every labelμ. - Cslib.LTSCatThe definition of labelled transition system (with the type of states and the type of labels as part of the structure).
- Cslib.LTS.FinitelyBranching.of_finiteEvery LTS with finite types for states and labels is also finitely branching.
- Cslib.Automata.NA.MullerNondeterministic Muller automaton.
- Cslib.LTS.mapLabelConstructs an LTS by mapping its labels into those of an existing LTS.
- Cslib.LTS.Relation.toLTSAny homogeneous relation can be seen as an LTS where all transitions have the same label.
- Cslib.LTS.Tr.toRelationReturns the relation that relates all states
s1ands2via a fixed transition labelμ. - Cslib.LTS.AcyclicAn LTS is acyclic if its underlying unlabelled transition relation contains no nonempty cycle.
- Cslib.LTS.MTr.toReflTransGenA multistep transition induces a reflexive-transitive path in the underlying unlabelled transition relation.
- Cslib.FLTS.instCoeLTSCslib.FLTS.instCoeLTS
- Cslib.Computability.Turing.SingleTape.SingleTapeNTMA (single-tape) Nondeterministic Turing Machine (NTM) is a nondeterministic automaton equipped with a set of accepting halting states.
- 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.ImageFiniteAn lts is image-finite if all images of its states are finite.
- Cslib.LTS.totalize
totalizeconstructs a total LTS from any given LTS by adding a sink state. - Cslib.LTS.toFLTS_mem_trCharacterisation of transitions in
LTS.toFLTSwrt transitions in the originalLTS. - Cslib.LTS.Execution.stepLEquivalent of
MTr.stepLfor executions. - Cslib.LTS.imageThe
μ-image of a statesis the set of allμ-derivatives ofs. - Cslib.LTS.FinitelyBranchingAn LTS is finitely branching if it is image-finite and all states have finite sets of outgoing labels.
- Cslib.LTS.chooseFLTSChoose an FLTS that is a "sub-LTS" of a total LTS.
- Cslib.LTS.BoundedAn LTS is bounded if there is a global bound on the length of all of its finite executions.
- Cslib.LTS.imageMultistepThe
μs-image of a states, whereμsis a list of labels, is the set of allμs-derivatives ofs. - Cslib.LTS.mem_setImageCharacterisation of
setImagewrtTr. - Cslib.LTS.inrLifting of an
LTS State LabeltoLTS (State' ⊕ State) Label. - Cslib.LTS.toFLTSConverts an
LTSinto anFLTSusing the subset construction. - 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.Execution.splitAn execution can be split at any intermediate state into two executions.
- 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.Example.selfLoopLTSThe self-loop LTS has a transition from its unique state to itself.
- Cslib.Automata.NAA nondeterministic automaton extends a
LTSwith a set of initial states. - Cslib.LTS.Example.successorLTSThe successor LTS takes each natural number to its successor.
- Cslib.LTS.mem_setImageMultistepCharacterisation of
setImageMultistepwithMTr. - Cslib.Automata.NA.iSumThe sum of an indexed family of nondeterministic automata.
- Cslib.LTS.Execution.reflEvery state has an execution of zero steps terminating in itself.
- Cslib.LTS.BoundedUpToAn LTS is bounded up to
nif every finite execution has length strictly less thann. - Cslib.LTS.UnlabelledTrThe unlabelled transition relation underlying an LTS.
- Cslib.LTS.Deterministic.eq_of_trCslib.LTS.Deterministic.eq_of_tr
- Cslib.LTS.CanReach.reflAny state can reach itself.
- Cslib.LTS.unionSumUnion of two LTSs with the same
Labeltype. The result combines the original respective state typesState1andState2into… - Cslib.LTS.inlLifting of an
LTS State LabeltoLTS (State ⊕ State') Label. - Cslib.LTS.withIdleWe first define what is denoted Tran* in [WinskelNielsen1995]: the extension of a transition relation with idle transitions.
- Cslib.LTS.MTrInvMultistep invariant.
- Cslib.Automata.NA.iProdThe product of an indexed family of nondeterministic automata.
- Cslib.LTS.totalize.no_sink_to_nonsinkIn
totalize, there is no finite execution from the sink state to any non-sink state. - Cslib.LTS.MorphismA morphism between two labelled transition systems consists of (1) a function on states, (2) a partial function on labels, and a proof…
- Cslib.LTS.HasOutLabelA state has an outgoing label
μif it has aμ-derivative. - Cslib.Automata.NA.FinAccA nondeterministic automaton that accepts finite strings (lists of symbols).
- Cslib.StatefulProcesses.Process.ltsSymbolic LTS of processes.
- Cslib.LTS.deterministic_not_ltoIn a deterministic LTS, if a state has a
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in universe u v in /-- A Labelled Transition System (LTS) for a type of states (`State`) and a type of transition labels (`Label`) consists of a labelled transition relation (`Tr`). -/ @[ext] structure Cslib.LTS (State : Type u) (Label : Type v) where /-- The transition relation. -/ Tr : State → Label → State → Prop