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.
1989
Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" - ISTI
Concurrent systems
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/361570
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact