Carleton University
Technical Report TR-256
November 1994
String Recognition on Anonymous Rings
Abstract
We consider the problem of recognizing whether a given binary string of length n is equal (up to rotation) to the input of an anonymous oriented ring of n processors. Previous algorithms for this problem have been “global” and do not take into account “local” patterns occurring in the string. Such patterns may be repetitive or discriminating, and can be used to provide ecient algorithms for recognizing strings. In this paper we give new upper and lower bounds on the bit complexity of string recognition. For the case of periodic strings, near optimal bounds are given which depend on the period of the string. For the case of a randomly chosen string, an optimal algorithm for the problem is given. In particular, we show that almost all strings can be recog- nized by communicating (n log n) bits. It is interesting to note that Kolmogorov complexity theory is used in the proof of our upper bound, rather than its traditional application to the proof of lower bounds.