A know extension of the Petri net model and a recently proposed extension of the LOTOS specification language are considered. Both formalisms are meant to allow one to specify time constrains in describing the behaviour of concurrent systems. In spite of their " superficial" differences, these two extended formalisms define the timing of synchronization events in essentially the same way; we prove, in the context of Petri nets, that such timing mechanism offers "weak" expressiveness, in the sense that, contrary to the Time Petri Nets model proposed by Merlin, such timed nets cannot simulate Turing machines.
The weakness of some timed models for concurrent systems
Bolognesi T;
1989
Abstract
A know extension of the Petri net model and a recently proposed extension of the LOTOS specification language are considered. Both formalisms are meant to allow one to specify time constrains in describing the behaviour of concurrent systems. In spite of their " superficial" differences, these two extended formalisms define the timing of synchronization events in essentially the same way; we prove, in the context of Petri nets, that such timing mechanism offers "weak" expressiveness, in the sense that, contrary to the Time Petri Nets model proposed by Merlin, such timed nets cannot simulate Turing machines.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_419289-doc_148134.pdf
accesso aperto
Descrizione: The weakness of some timed models for concurrent systems
Dimensione
1.44 MB
Formato
Adobe PDF
|
1.44 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.


