The search functionality is under construction.

Author Search Result

[Author] Kousuke YAMADA(1hit)

1-1hit
  • Dead Problem of Program Nets

    Shingo YAMAGUCHI  Kousuke YAMADA  Qi-Wei GE  Minoru TANAKA  

     
    PAPER

      Vol:
    E89-A No:4
      Page(s):
    887-894

    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.