mwang@watmath.UUCP (mwang) (08/27/85)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY SEMINAR
- Wednesday, September 4, 1985.
Dr. S. Zaks of Technion will speak on ``On the Bit Com-
plexity of Distributed Computations in a Unidirectional
Ring with a Leader.''
TIME: 3:30 PM
ROOM: MC 6091A (Please Note)
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 for a ring of size n:
-
(1) A language is recognized by an algorithm that uses
O(n) bits if and only if it is regular (also com-
- -
pared is the bit complexity vs. the number of
rounds).
(2) Every non-regular language requires at least
()(nlogn) bits for its recognition (clearly, any
-- - -
language requires no more than O(n**2) bits for its
- ---
recognition).
(3) For every function g(n),
- -
()(nlogn) < g(n) < O(n**2), there is a language
-- - - - - - - - ---
that requires O(g(n)) bits for its recognition.
- - -
August 19, 1985