Presentation | 2004-11-04 On Dead of Program Nets Kousuke YAMADA, Shingo YAMAGUCHI, Qi-Wei GE, Minoru TANAKA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | This paper discusses dead for program nets. We first give the definition of dead for program nets. A program net is said to be partially dead if the net consists of nodes which never become firable in any possible firing sequence. We define dead problem as a problem to deciding whether a given program net is partially dead or not. We classify program nets into 4 classes: general, acyclic, SWITCH-less, and acvclic SWITCH-less nets. Then we discuss methods of solving dead problem for each class. The results are as follows: (1) Acyclic SWITCH-less nets are not partially dead. (2)For SWITCH-less nets, the dead problem can be solved in polynomial time. (3) For acyclic nets and general nets, the dead problem seems not to be included in NP class. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | dataflow program / program net / dead / decision algorithm / computation complexity |
Paper # | CAS2004-53,CST2004-32 |
Date of Issue |
Conference Information | |
Committee | CAS |
---|---|
Conference Date | 2004/10/28(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Circuits and Systems (CAS) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | On Dead of Program Nets |
Sub Title (in English) | |
Keyword(1) | dataflow program |
Keyword(2) | program net |
Keyword(3) | dead |
Keyword(4) | decision algorithm |
Keyword(5) | computation complexity |
1st Author's Name | Kousuke YAMADA |
1st Author's Affiliation | Graduate School of Science and Engineering, Yamaguchi University() |
2nd Author's Name | Shingo YAMAGUCHI |
2nd Author's Affiliation | Faculty of Engineering, Yamaguchi University |
3rd Author's Name | Qi-Wei GE |
3rd Author's Affiliation | Faculty of Education, Yamaguchi University |
4th Author's Name | Minoru TANAKA |
4th Author's Affiliation | Faculty of Engineering, Yamaguchi University |
Date | 2004-11-04 |
Paper # | CAS2004-53,CST2004-32 |
Volume (vol) | vol.104 |
Number (no) | 402 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |