Generalised Palindromes and the structural complexity of binary strings
Keith Gibson
Birkbeck
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.