Abstract
We introduce a new model of parallel computation, namely the FIFO nets. First, we introduce some basic definitions. A restriction of this model has the power of the Turing machine. Monogeneous Fifo nets are then introduced. The coverability tree is a procedure to decide whether a monogeneous net is bounded or not. At last, regularity is decidable for monogeneous nets.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
V-Bibliography
: G.W. BRAMS "Réseaux de Petri: théorie et pratique" (tome 1) Masson — Paris (1982).
: A. FINKEL "Monogeneous FIFO Petri nets" — 3rd European Workshop on applications and theory of Petri net — Varenna — Italy (September 1982)
: A. FINKEL — "Deux Classes de Réseaux à files: Les Réseaux Monogènes et les Réseaux Préfixes" — Thèse de 3ème cycle — Paris VII (Octobre 1982).
: H.J. GENRICH & K. LAUTENBACH "The analysis of distributed systems by means of predicate/transition nets". Semantics of Concurrent Computation (G. KAHN ed.) L.N.C.S. 70 pp 123–146 — Springer Verlag — (1979).
: K. JENSEN "Coloured Petri nets and the invariant method". T.C.S. Vol. 14, no 3, pp. 317–336 (June 1981).
: R.M. KARP & R.E. MILLER "Parallel program schemata" J. Comput. System Sci. 3 (4), pp. 167–195 (1969).
: T. KASAI & R. E. MILLER "Homomorphisms between models of parallel computation". Research Report IBM — RC 7796 (33742) (1979).
: R. MARTIN & G. MEMMI "Spécification et validation de système temps réel à l'aide de réseaux de Petri à files", Revue Technique THOMSONCSF, Vol. 13, no 3, pp. 635–653 (September 1981).
: G. MEMMI — Thèse d'Etat — Paris VI — to appear.
: M. MINSKY "Computation: finite and infinite machines" Prentice-Hall, Englewood Cliffs N.J. (1967).
: B. VAUQUELIN & P. FRANCHI-ZANNETTACCI "Automates à files" TCS 11 pp. 221–225 (1980).
: R. VALK & G. VIDAL-NAQUET "Petri nets and regular languages" J.C.S.S. Vol. 23, no 3, pp. 299–325 (december 1981).
: G. VIDAL-NAQUET "Rationalité et déterminisme dans les réseaux de Petri", Thèse d'Etat — Paris VI — (1981).
: "Méthodologie d'analyse et de programmation des systèmes" Rapport final du marché d'études DAII no 79-35-059 (1981).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1982 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Finkel, A., Memmi, G. (1982). FIFO nets: A new model of parallel computation. In: Cremers, A.B., Kriegel, HP. (eds) Theoretical Computer Science. Lecture Notes in Computer Science, vol 145. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0036474
Download citation
DOI: https://doi.org/10.1007/BFb0036474
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-11973-9
Online ISBN: 978-3-540-39421-1
eBook Packages: Springer Book Archive