On Recognizing a String on an Anonymous Ring

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 occurri...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2000-02, Vol.34 (1), p.3-12
Main Authors: Kranakis, E., Krizanc, D., Luccio, F. L.
Format: Article
Language:English
Subjects:
Algorithms
Complexity theory
Lower bounds
Optimization
Processors
Proving
Recognition
Strings
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. In this paper we give new upper and lower bounds on the bit complexity of string recognition. For periodic strings, near optimal bounds are given which depend on the period of the string. For Kolmogorov random strings an optimal algorithm is given. As a consequence, we show that almost all strings can be recognized by communicating Theta (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.
ISSN:1432-4350
1433-0490
DOI:10.1007/s002240010007