For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Partial Order Semantics for FIFO-Nets
Cinzia BERNARDESCHI Nicoletta De FRANCESCO Gigliola VAGLINI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/08/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata,Languages and Theory of Computing
true concurrency, FIFO-nets, partial order semantics,
Full Text: PDF>>
In this work, we give a true concurrency semantics for FIFO-nets, that are Petri nets in which places behave as queues, tokens take values in a finite alphabet and the firing of a transition depends on sequences on the alphabet. We introduce fn-processes to represent the concurrent behavior of a FIFO-net N during a sequence of transition firings. Fn-processes are modeled by a mapping from a simple FIFO-net without queue sharing and cycles, named FIFO-occurrence net, to N. Moreover, the relation among the firings expressed by the FIFO-occurrence net has been enriched by an ordering relation among the elements of the FIFO-occurrence net representing values entered into a same queue of N. We give a way to build fn-processes step by step in correspondance with a sequence of transition firings and the fn-processes operationally built are all those abstractly defined. The FIFO-occurrence nets of fn-processes have some interesting properties; for example, such nets are always discrete and, consequently, there is at least a transition sequence corresponding to each fn-process.