Title :
The Link between r-contiguous Detectors and k-CNF Satisfiability
Author :
Stibor, Thomas ; Timmis, Jonathan ; Eckert, Claudia
Author_Institution :
Darmstadt Univ. of Technol., Darmstadt
Abstract :
In the context of generating detectors using the r-contiguous matching rule, questions have been raised at the efficiency of the process. We show that the problem of generating r-contiguous detectors can be transformed in a k-CNF satisfiability problem. This insight allows for the wider understanding of the problem of generating r-contiguous detectors. Moreover, we apply this result to consider questions relating to the complexity of generating detectors, and when detectors are generable.
Keywords :
computability; matching rule; r-contiguous detectors; satisfiability problem; Clustering algorithms; Computer networks; Computer science; Detectors; Immune system; Information processing; Proteins; Rough surfaces; Space technology; Surface roughness;
Conference_Titel :
Evolutionary Computation, 2006. CEC 2006. IEEE Congress on
Conference_Location :
Vancouver, BC
Print_ISBN :
0-7803-9487-9
DOI :
10.1109/CEC.2006.1688350