An introduction to FIFO nets - monogeneous nets: a subclass of FIFO nets (Q1059399): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(85)90014-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2067782667 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3967058 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3704895 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3959437 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3670573 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Communicating sequential processes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coloured Petri nets and the invariant-method / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel program schemata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Homomorphisms between models of parallel computation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3859263 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5590814 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on colored Petri nets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Deterministic buffer synchronization of sequential processes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4168054 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3670605 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automates a file / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Petri nets and regular languages / rank | |||
Normal rank |
Latest revision as of 17:58, 14 June 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