Technical Report CS0383

Title: On the Bit Complexity of Distributed Computations in a Undirectional Ring with a Leader
Authors: Y. Mansour and S. Zaks
Abstract: We study the bit complexity of pattern recognition in a distributed unidirectional ring with a leader. Each processor gets as input a letter from some alphabet, and these concatenated letters, starting at the leader, form the pattern of the ring. The leader initiates an algorithm that accepts or rejects this pattern. Thus each algorithm recognizes a language over a given alphabet. We prove the following ( n is the size of the ring): (1) A language is recognized by an algorithm that uses 0(n) bits if and only if it is regular (also compared is the bit complexity vs the number of rounds). (2) Every non-regular language requires at least Omega(nlogn) bits for its recognition (clearly, every language requires no more than O(n^2) bits for its recognition). (3) For every function g(n), Omega(nlogn)<=g(n)<=0(n2), there is a language that requires Theta(g(n) bits for its recognition.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1985
To the main CS technical reports page

Computer science department, Technion