Flat Petri Nets (Invited Talk)
| Autor: | Jérôme Leroux |
|---|---|
| Přispěvatelé: | Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-17-CE40-0028,BRAVAS,IDEAL-BASED ALGORITHMS FOR VASSES AND WELL-STRUCTURED SYSTEMS(2017) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Sequence
Flat Systems Theoretical computer science Reachability problem Computer science Existential quantification 020207 software engineering 0102 computer and information sciences 02 engineering and technology Petri net 16. Peace & justice Formal methods 01 natural sciences Formal Methods 010201 computation theory & mathematics Reachability [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT] TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Computer Science::Logic in Computer Science 0202 electrical engineering electronic engineering information engineering Petri Nets Representation (mathematics) Presburger Arithmetic Presburger arithmetic Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Application and Theory of Petri Nets and Concurrency Application and Theory of Petri Nets and Concurrency-42nd International Conference, {PETRI} {NETS} 2021 Application and Theory of Petri Nets and Concurrency-42nd International Conference, 2021, Jun 2021, Virtual Event, France. ⟨10.1007/978-3-030-76983-3_2⟩ Application and Theory of Petri Nets and Concurrency ISBN: 9783030769826 Petri Nets |
| DOI: | 10.1007/978-3-030-76983-3_2⟩ |
| Popis: | International audience; Vector addition systems with states (VASS for short), or equivalently Petri nets are one of the most popular formal methods for the representation and the analysis of parallel processes. The central algorithmic problem is reachability: whether from a given initial configuration there exists a sequence of valid execution steps that reaches a given final configuration. This paper provides an overview of results about the reachability problem for VASS related to Presburger arithmetic, by presenting 1) a simple algorithm for deciding the reachability problem based on invariants definable in Presburger arithmetic, 2) the class of flat VASS for computing reachability sets in Presburger arithmetic, and 3) complexity results about the reachability problem for flat VASS. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|