An introduction to FIFO nets- monogeneous nets: A subclass of FIFO nets

G. Memmi; A. Finkel

doi:10.1016/0304-3975(85)90014-3

An introduction to FIFO nets- monogeneous nets: A subclass of FIFO nets

G. Memmi
, A. Finkel

INRIA Saclay, Laboratoire de Recherche en Informatique (LRI), Université Paris Sud

Research output: Contribution to journal › Article › peer-review

28 Citations (Scopus)

Abstract

We introduce a new model of parallel computation, the FIFO nets. We show how it can simulate Petri nets and coloured Petri nets and prove that a restriction of it (alphabetical FIFO nets) has the power of Turing machines. Furthermore, we define monogeneous FIFO nets and use the coverability graph for proving that it is decidable whether or not a monogeneous net is bounded and whether or not its language is regular.

Original language	English
Pages (from-to)	191-214
Number of pages	24
Journal	Theoretical Computer Science
Volume	35
Issue number	C
DOIs	https://doi.org/10.1016/0304-3975(85)90014-3
Publication status	Published - 1 Jan 1985

Keywords

FIFO nets
boundedness
coverability graph
deterministic languages of Petri nets
monogeneous net
parallel computation model
program machines
regular languages

Access to Document

10.1016/0304-3975(85)90014-3

Cite this

@article{e6c58aa475664adeb97364f35bd55a41,

title = "An introduction to FIFO nets- monogeneous nets: A subclass of FIFO nets",

abstract = "We introduce a new model of parallel computation, the FIFO nets. We show how it can simulate Petri nets and coloured Petri nets and prove that a restriction of it (alphabetical FIFO nets) has the power of Turing machines. Furthermore, we define monogeneous FIFO nets and use the coverability graph for proving that it is decidable whether or not a monogeneous net is bounded and whether or not its language is regular.",

keywords = "FIFO nets, boundedness, coverability graph, deterministic languages of Petri nets, monogeneous net, parallel computation model, program machines, regular languages",

author = "G. Memmi and A. Finkel",

year = "1985",

month = jan,

day = "1",

doi = "10.1016/0304-3975(85)90014-3",

language = "English",

volume = "35",

pages = "191--214",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - An introduction to FIFO nets- monogeneous nets

T2 - A subclass of FIFO nets

AU - Memmi, G.

AU - Finkel, A.

PY - 1985/1/1

Y1 - 1985/1/1

N2 - We introduce a new model of parallel computation, the FIFO nets. We show how it can simulate Petri nets and coloured Petri nets and prove that a restriction of it (alphabetical FIFO nets) has the power of Turing machines. Furthermore, we define monogeneous FIFO nets and use the coverability graph for proving that it is decidable whether or not a monogeneous net is bounded and whether or not its language is regular.

AB - We introduce a new model of parallel computation, the FIFO nets. We show how it can simulate Petri nets and coloured Petri nets and prove that a restriction of it (alphabetical FIFO nets) has the power of Turing machines. Furthermore, we define monogeneous FIFO nets and use the coverability graph for proving that it is decidable whether or not a monogeneous net is bounded and whether or not its language is regular.

KW - FIFO nets

KW - boundedness

KW - coverability graph

KW - deterministic languages of Petri nets

KW - monogeneous net

KW - parallel computation model

KW - program machines

KW - regular languages

U2 - 10.1016/0304-3975(85)90014-3

DO - 10.1016/0304-3975(85)90014-3

M3 - Article

AN - SCOPUS:0022018122

SN - 0304-3975

VL - 35

SP - 191

EP - 214

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -

An introduction to FIFO nets- monogeneous nets: A subclass of FIFO nets

Abstract

Keywords

Access to Document

Fingerprint

Cite this