An introduction to FIFO nets - monogeneous nets: a subclass of FIFO nets (Q1059399): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:02, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An introduction to FIFO nets - monogeneous nets: a subclass of FIFO nets |
scientific article |
Statements
An introduction to FIFO nets - monogeneous nets: a subclass of FIFO nets (English)
0 references
1985
0 references
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.
0 references
parallel computation model
0 references
program machines
0 references
regular languages
0 references
deterministic languages
0 references
sequential processes communicating by FIFO channels
0 references
Petri nets
0 references
Turing machines
0 references