### Abstract

Labeled transition systems are ubiquitous in computer science. They are used e.g. for automata and for program graphs in program analysis. We formalize labeled transition systems with and without epsilon transitions. The main difference between formalizations of labeled transition systems is in their choice of how to represent the transition system. In the present formalization the set of nodes is a type, and a labeled transition system is represented as a locale fixing a set of transitions where each transition is a triple of respectively a start node, a label and an end node. Wimmer [Wim20] provides an overview of formalizations of graphs and transition systems.

[Wim20] Simon Wimmer. Archive of graph formalizations. 2020. https://github.com/wimmers/archive-of-graph-formalizations.

### License

BSD License

### Topics

- Computer science/Automata and formal languages
- Computer science

### Related publications

- Schlichtkrull, A., Konggaard Schou, M., Srba, J., & Traytel, D. (2022). Differential Testing of Pushdown Reachability with a Formally Verified Oracle. TU Wien. https://doi.org/10.34727/2022/ISBN.978-3-85448-053-2_44

### Session Labeled_Transition_Systems

- LTS

### Depends on

- Deriving class instances for datatypes

### Used by

- Pushdown Systems

### Auto-related entries

- Transition Systems and Automata
- Promela Formalization

## Cite

×

Labeled_Transition_Systems-AFP

    @article{Labeled_Transition_Systems-AFP,
      author  = {Anders Schlichtkrull and Morten Konggaard Schou and Jiří Srba and Dmitriy Traytel},
      title   = {Labeled Transition Systems},
      journal = {Archive of Formal Proofs},
      month   = {October},
      year    = {2023},
      note    = {\url{https://isa-afp.org/entries/Labeled_Transition_Systems.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest