Subclasses of Formalized Data Flow Diagrams: Monogeneous, Linear & Topologically Free Choice RDFD's

Thumbnail Image
Date
1996-12-01
Authors
Symanzik, Jürgen
Baker, Albert
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract

Formalized Data Flow Diagrams (FDFD's) and, especially, Reduced Data Flow Diagrams (RDFD's) are Turing equivalent (Symanzik and Baker, 1996). Therefore, no decidability problem can be solved for FDFD's in general. However, it is possible to define subclasses of FDFD's for which decidability problems can be answered. In this paper we will define certain subclasses of FDFD's, which we call Monogeneous RDFD's, Linear RDFD's, and Topologically Free Choice RDFD's. We will show that two of these three subclasses of FDFD's can be simulated via isomorphism by the correspondingly named subclasses of FIFO Petri Nets. It is known that isomorphisms between computation systems guarantee the same answers to corresponding decidability problems (e. g., reachability, deadlock, liveness) in the two systems (Kasai and Miller, 1982). This means that problems where it is known that they can (not) be solved for a subclass of FIFO Petri Nets it follows immediately that the same problems can (not) be solved for the correspondingly named subclass of FDFD's.

Comments

© Copyright 1996 by Jürgen Symanzik and Albert L. Baker. All rights reserved.

Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright
Collections