Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
On recognizing a string on an anonymous ring
Autore:
Kranakis, E; Krizanc, D; Luccio, EL;
Indirizzi:
Carleton Univ, Sch Comp Sci, Ottawa, ON K1S 5B6, Canada Carleton Univ Ottawa ON Canada K1S 5B6 mp Sci, Ottawa, ON K1S 5B6, Canada Wesleyan Univ, Dept Math, Middletown, CT 06459 USA Wesleyan Univ Middletown CT USA 06459 Dept Math, Middletown, CT 06459 USA Univ Trieste, Dipartimento Sci Matemat, I-34127 Trieste, Italy Univ Trieste Trieste Italy I-34127 o Sci Matemat, I-34127 Trieste, Italy
Titolo Testata:
THEORY OF COMPUTING SYSTEMS
fascicolo: 1, volume: 34, anno: 2001,
pagine: 3 - 12
SICI:
1432-4350(200101/02)34:1<3:ORASOA>2.0.ZU;2-7
Fonte:
ISI
Lingua:
ENG
Soggetto:
COMPUTATION; COMPLEXITY; NETWORKS;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
13
Recensione:
Indirizzi per estratti:
Indirizzo: Kranakis, E Carleton Univ, Sch Comp Sci, Ottawa, ON K1S 5B6, Canada Carleton Univ Ottawa ON Canada K1S 5B6 wa, ON K1S 5B6, Canada
Citazione:
E. Kranakis et al., "On recognizing a string on an anonymous ring", THEOR C SYS, 34(1), 2001, pp. 3-12

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 ringof 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 stringrecognition. 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 berecognized 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.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 18/01/20 alle ore 13:37:03