We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Synthesis and reengineering of persistent systems.
- Authors
Best, Eike; Devillers, Raymond
- Abstract
In formal verification, a structural object, such as a program or a Petri net, is given, and questions are asked about its behaviour. In system synthesis, conversely, a behavioural object, such as a transition system, is given, and questions are asked about the existence of a structural object realising this behaviour. In system reengineering, one wishes to transform a given system into another one, with similar behaviour and other properties not enjoyed by the original system. This paper addresses synthesis and reengineering problems in the specific framework of finite-state labelled transition systems, place/transition Petri nets, and behaviour isomorphisms. Since algorithms solving these problems are prohibitively time-consuming in general, it is interesting to know whether they can be improved in restricted circumstances, and whether direct correspondences can be found between classes of behavioural and classes of structural objects. This paper is concerned with persistent systems, which occur in hardware design and in various other applications. We shall derive exact conditions for a finite persistent transition system to be isomorphically implementable by a bounded Petri net exhibiting persistence in a structural way, and derive an efficient algorithm to find such a net if one exists. For the class of marked graph Petri nets, this leads to an exact characterisation of their state spaces.
- Subjects
REENGINEERING (Management); IDENTIFICATION; PETRI nets; PROBABILITY theory; ISOMORPHISM (Mathematics)
- Publication
Acta Informatica, 2015, Vol 52, Issue 1, p35
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-014-0209-7