An introduction to FIFO nets - monogeneous nets: a subclass of FIFO nets (Q1059399): Difference between revisions

The paper introduces FIFO nets, a model for the specification and analysis of sequential processes communicating by FIFO channels. A FIFO net is a triplet \((R,M_ 0,A)\), where \(R=(F,T,\Gamma,V)\) is a finite valuated bipartite graph with F the set of FIFO queues, T the set of transitions, \(\Gamma\) the correspondence between F and T giving for each T the set of its successors and V a valuation function from (T\(\times F)\cup (F\times T)\) into \(A^*\), \(M_ 0\) is the initial marking and A is a finite alphabet. The firing of a transition t for each fifo f of input t removes V(t,f) which is the prefix of the marking M(f) and for each fifo f' of output t appends V(t,f) to M(f'). Petri nets and colored Petri nets can be effectively simulated by Petri nets. FIFO nets can be effectively simulated by a subclass of them, namely alphabetical FIFO nets. Alphabetical FIFO nets can be shown to have the power of Turing machines. Known results on Petri nets are extended to classes of FIFO nets. In particular the class of FIFO nets is considered in which each input edge of a fifo is valuated by a power of the same word. These nets, called monogeneous FIFO nets, contain Petri nets. A procedure for deciding boundedness of monogeneous FIFO nets is given. As the class of monogeneous FIFO nets labelled languages is proved to be equal to the class of Petri nets labelled languages questions which are decidable for Petri nets languages, like regularity, are decidable also for monogeneous FIFO nets languages.