Dead Problem of Program Nets
| Autor: | Kousuke Yamada, Minoru Tanaka, Shingo Yamaguchi, Qi-Wei Ge |
|---|---|
| Rok vydání: | 2006 |
| Předmět: | |
| Zdroj: | IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. :887-894 |
| ISSN: | 1745-1337 0916-8508 |
| DOI: | 10.1093/ietfec/e89-a.4.887 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|