Dead Problem of Program Nets

Shingo YAMAGUCHI; Kousuke YAMADA; Qi-Wei GE; Minoru TANAKA

doi:10.1093/ietfec/e89-a.4.887

Dead Problem of Program Nets

Shingo YAMAGUCHI, Kousuke YAMADA, Qi-Wei GE, Minoru TANAKA

Full Text Views

0

Cite this

Summary :

In this paper, we discuss a new property, named dead, of (dataflow) program nets. We say that a node of a program net is dead iff the node cannot fire once in any possible firing sequence, and furthermore the program net is partially dead. We tackle a problem of deciding whether a given program net is partially dead, named dead problem. Program nets can be classified into four subclasses: general, acyclic, SWITCH-less, and acyclic SWITCH-less nets. For each subclass, we give a method of solving dead problem and its computation complexity. Our results show that (i) acyclic SWITCH-less nets are not partially dead; (ii) for SWITCH-less nets, dead problem can be solved in polynomial time; (iii) for acyclic nets and general nets, dead problem is intractable.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.4 pp.887-894

Publication Date: 2006/04/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.4.887

Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)

Category

Cite this

Copy

Shingo YAMAGUCHI, Kousuke YAMADA, Qi-Wei GE, Minoru TANAKA, "Dead Problem of Program Nets" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 4, pp. 887-894, April 2006, doi: 10.1093/ietfec/e89-a.4.887.
Abstract: In this paper, we discuss a new property, named dead, of (dataflow) program nets. We say that a node of a program net is dead iff the node cannot fire once in any possible firing sequence, and furthermore the program net is partially dead. We tackle a problem of deciding whether a given program net is partially dead, named dead problem. Program nets can be classified into four subclasses: general, acyclic, SWITCH-less, and acyclic SWITCH-less nets. For each subclass, we give a method of solving dead problem and its computation complexity. Our results show that (i) acyclic SWITCH-less nets are not partially dead; (ii) for SWITCH-less nets, dead problem can be solved in polynomial time; (iii) for acyclic nets and general nets, dead problem is intractable.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.4.887/_p

Copy

@ARTICLE{e89-a_4_887,
author={Shingo YAMAGUCHI, Kousuke YAMADA, Qi-Wei GE, Minoru TANAKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Dead Problem of Program Nets},
year={2006},
volume={E89-A},
number={4},
pages={887-894},
abstract={In this paper, we discuss a new property, named dead, of (dataflow) program nets. We say that a node of a program net is dead iff the node cannot fire once in any possible firing sequence, and furthermore the program net is partially dead. We tackle a problem of deciding whether a given program net is partially dead, named dead problem. Program nets can be classified into four subclasses: general, acyclic, SWITCH-less, and acyclic SWITCH-less nets. For each subclass, we give a method of solving dead problem and its computation complexity. Our results show that (i) acyclic SWITCH-less nets are not partially dead; (ii) for SWITCH-less nets, dead problem can be solved in polynomial time; (iii) for acyclic nets and general nets, dead problem is intractable.},
keywords={},
doi={10.1093/ietfec/e89-a.4.887},
ISSN={1745-1337},
month={April},}

Copy

TY - JOUR
TI - Dead Problem of Program Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 887
EP - 894
AU - Shingo YAMAGUCHI
AU - Kousuke YAMADA
AU - Qi-Wei GE
AU - Minoru TANAKA
PY - 2006
DO - 10.1093/ietfec/e89-a.4.887
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2006
AB - In this paper, we discuss a new property, named dead, of (dataflow) program nets. We say that a node of a program net is dead iff the node cannot fire once in any possible firing sequence, and furthermore the program net is partially dead. We tackle a problem of deciding whether a given program net is partially dead, named dead problem. Program nets can be classified into four subclasses: general, acyclic, SWITCH-less, and acyclic SWITCH-less nets. For each subclass, we give a method of solving dead problem and its computation complexity. Our results show that (i) acyclic SWITCH-less nets are not partially dead; (ii) for SWITCH-less nets, dead problem can be solved in polynomial time; (iii) for acyclic nets and general nets, dead problem is intractable.
ER -