| THE SPECTRALITY DECISION PROBLEM |
| |
| 作者姓名： | E.V.Dubrova J.C.Muzio |
| |
| 作者单位： | University of Victoria Canada，University of Victoria，Canada |
| |
| 摘 要： | An effcient algorithm for deciding whether a given integer vector is thespectrum of some Boolean function is presented.The algorithm performs astep-by-step spectral decomposition of the input vector and checks at eachstep a set of necessary conditions for spectrality for the resulting vectors.The algorithm concludes that the input vector cannot lead to a valid Booleanfunction as soon as a vector not satisfying the conditions is found,which,as proved in the paper,for almost all cases happens after the first step ofthe decomposition.
|
The spectrality decision problem |
| |
| E.V.Dubrova,J.C.Muzio.THE SPECTRALITY DECISION PROBLEM[J].Analysis in Theory and Applications,1998,14(3):73-84. |
| |
| Authors: | E V Dubrova J C Muzio |
| |
| Institution: | 1. VLSI Design and Test Group Department of Computer Science, University of Victoria, P.O. Box 3055, V8W 3P6, Victoria, B.C., Canada
|
| |
| Abstract: | An efficient algorithm for deciding whether a given integer vector is the spectrum of some Boolean function is presented. The algorithm performs a step-by-step spectral decomposition of the input vector and checks at each step a set of necessary conditions for spectrality for the resulting vectors. The algorithm concludes that the input vector cannot lead to a valid Boolean function as soon as a vector not satisfying the conditions is found, which, as proved in the paper, for almost all cases happens after the first step of the decomposition. |
| |
| Keywords: | |
| 本文献已被 CNKI SpringerLink 等数据库收录！ |
