Generalised Palindromes and the structural complexity of binary strings

Keith Gibson

There is a school of thought that entropy should be viewed as an anthropomorphic concept, or, more picturesquely put, that chaos is in the eye of the beholder. This philosophy has influenced a definition of structural complexity for binary strings intended in the first instance to meet the needs of cognitive psychologists who want to measure the complexity of patterns. Taking change to be the most primitive ingredient of complexity in the eye of a beholder we propose a measure of complexity of a binary string S based on the amount of change incorporated in S. Though not directly related to physical entropy, it is true, for example, that if dots are distributed randomly in a square the resulting pattern will have high complexity, whereas if they are all squashed up in one corner of the square the pattern will have very low complexity. Moreover our measure of complexity correlates very well with other measures given in the literature of cognitive psychology, which is all the more remarkable given that the concept on which we base our measure is different from and much simpler than that of other measures.

Our definition of structural complexity has thrown up a number of combinatorial problems that we hope will be of interest to mathematicians - we need solutions! In particular it has led us to consider what we call generalised palindromes. Define a binary map [] on binary strings S of length L as follows, and call S a generalised palindrome if [S] = 0. If L = 2 then [S] = 0 iff the two characters of S are different. If L >= 3, let Xk, Yk, be the substrings of S formed from the first and last k characters of S, k = 2 to L-1. Then [S] = 0 iff [Xk] = [Yk], k = 2 to T = L-1. An intriguing conjecture is that for L >= 9 it is sufficient to take T = (L-2) - (L-2)/4, integer division.

Generalised palindromes do generalise the concept of palindromicity. Call a binary string S of length L palindromic if the reverse of S is either S or the complement of S, sensible because structural complexity should clearly be invariant under complementation and reversal. Then for L > 2 any palindromic string is a generalised palindrome, but the converse is NOT true for L >= 9. Indeed we do not know how many generalised palindromes there are.