Phase Transition and the Computational Complexity of Generating rcontiguous Detectors
The problem of generating rcontiguous detectors in negative selection can be transformed in the problem of finding assignment sets for a Boolean formula in kCNF. Knowing this crucial fact enables us to explore the computational complexity and the feasibility of finding detectors with respect to the number of self bit strings $\mathcalS$, the bit string length l and matching length r. It turns out that finding detectors is hardest in the phase transition region, which is characterized by certain combinations of parameters $\mathcalS,l$ and r. This insight is derived by investigating the rcontiguous matching probability in a random search approach and by using the equivalent kCNF problem formulation.
Phase Transition and the Computational Complexity of Generating rcontiguous Detectors
Proceedings of the 6th International Conference on Artificial Immune Systems (ICARIS2007)
Authors:  Thomas Stibor 
Year/month:  2007/ 
Booktitle:  Proceedings of the 6th International Conference on Artificial Immune Systems (ICARIS2007) 
Series:  Lecture Notes in Computer Science 
Pages:  142155 
Address:  Santos/SP, Brazil 
Publisher:  SpringerVerlag 
Fulltext:  icaris2007tscrc.pdf 
Abstract 

The problem of generating rcontiguous detectors in negative selection can be transformed in the problem of finding assignment sets for a Boolean formula in kCNF. Knowing this crucial fact enables us to explore the computational complexity and the feasibility of finding detectors with respect to the number of self bit strings $\mathcalS$, the bit string length l and matching length r. It turns out that finding detectors is hardest in the phase transition region, which is characterized by certain combinations of parameters $\mathcalS,l$ and r. This insight is derived by investigating the rcontiguous matching probability in a random search approach and by using the equivalent kCNF problem formulation. 
Bibtex:
@inproceedings { proc:Stibor2007,author = { Thomas Stibor},
title = { Phase Transition and the Computational Complexity of Generating rcontiguous Detectors },
year = { 2007 },
booktitle = { Proceedings of the 6th International Conference on Artificial Immune Systems (ICARIS2007) },
series = { Lecture Notes in Computer Science },
address = { Santos/SP, Brazil },
pages = { 142155 },
publisher = { SpringerVerlag },
url = {https://www.sec.in.tum.de/i20/publications/phasetransitionandthecomputationalcomplexityofgeneratingrcontiguousdetectors/@@download/file/icaris2007tscrc.pdf}
}