Digital Library of Zielona Góra contains 9 272 digital objects
Object
Title: Generation of synchronizing state machines from a transition system: A region-based approach
Contributor:
Niemiec, Marcin - ed. ; Dziech, Andrzej - ed. ; Wassermann, Jakob - ed.
Subtitle:
Group publication title:
Abstract:
Transition systems (TSs) and Petri nets (PNs) are important models of computation ubiquitous in formal methods for modeling systems. A crucial problem is how to extract, from a given TS, a PN whose reachability graph is equivalent (with a suitable notion of equivalence) to the original TS. This paper addresses the decomposition of transition systems into synchronizing state machines (SMs), which are a class of Petri nets where each transition has one incoming and one outgoing arc. Furthermore, all reachable markings (non-negative vectors representing the number of tokens for each place) of an SM have only one marked place with only one token. ; This is a significant case of the general problem of extracting a PN from a TS. The decomposition is based on the theory of regions, and it is shown that a property of regions called excitation-closure is a sufficient condition to guarantee the equivalence between the original TS and a decomposition into SMs. An efficient algorithm is provided which solves the problem by reducing its critical steps to the maximal independent set problem (to compute a minimal set of irredundant SMs) or to satisfiability (to merge the SMs). We report experimental results that show a good trade-off between quality of results vs. computation time.
Publisher:
Zielona Góra: Uniwersytet Zielonogórski
Resource Identifier:
DOI:
Pages:
Source:
AMCS, volume 33, number 1 (2023) ; click here to follow the link
Language:
License CC BY 4.0:
Rights:
Biblioteka Uniwersytetu Zielonogórskiego
Object collections:
- Repository > Faculties > Faculty of Computer, Electrical and Control Engineering
- Repository > Types of work > Articles
- Repository > Scientific journals and UZ publishing series > International Journal of Applied Mathematics and Computer Science (AMCS) > International Journal of Applied Mathematics and Computer Science (AMCS) (2023)
Last modified:
Jul 25, 2025
In our library since:
Jul 25, 2025
Number of object content hits:
13
All available object's versions:
https://zbc.uz.zgora.pl/repozytorium/publication/101577
Show description in RDF format:
Show description in OAI-PMH format:
-
-
-
-
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 33, number 1 (2023)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 33, number 2 (2023)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 33, number 3 (2023)
-
International Journal of Applied Mathematics and Computer Science (AMCS), volume 33, number 4 (2023)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
| Edition name | Date |
|---|---|
| Generation of synchronizing state machines from a transition system: A region-based approach | Jul 25, 2025 |
Objects Similar
Wojnakowski, Marcin Wiśniewski, Remigiusz Bazydło, Grzegorz Popławski, Mateusz Kusy, Maciej - ed. Scherer, Rafał - ed. Krzyżak, Adam - ed.
Gosti, Wilsin Villa, Tiziano Saldanha, Alex Sangiovanni-Vincentelli, Alberto L. Korbicz, Józef (1951- ) - red.
Clempner, Julio Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
Clempner, Julio Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
Gu, Tianlong Bahri, Parisa A. Cai, Guoyong Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
Gu, Tianlong Dong, Rongsheng Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
Li, Ben Khlif-Bouassida, Manel Toguéyni, Armand Puig, Vicenç - ed. Sauter, Dominique - ed. Aubrun, Christophe - ed. Schulte, Horst - ed.
Patalas-Maliszewska, Justyna Wiśniewski, Remigiusz Zhou, MengChu Topczak, Marcin Wojnakowski, Marcin Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
