Motiverad av ett konkret problem och med målet att förstå sambandet mellan komplexiteten i strömmande algoritmer och beräknings komplexitet formella språk, undersöker vi problemet Dyck (s) att kontrollera matchande parenteser, med olika typer av parenteser. Vi presenterar en en-pass randomiserad streaming algoritm för Dyck(2) med utrymme O ( ε n log n ) bitar, tid per bokstav polylog(n), och ensidigt fel. Vi bevisar att denna en-pass algoritm är optimal, upp till en log n faktor, även när dubbelsidigt fel är tillåtet, och antar att en liknande gräns håller för varje konstant antal passerar över inmatningen. Förvånansvärt nog krymper rymdbehovet drastiskt om vi har tillgång till ingångsströmmen i omvänd riktning. Vi presenterar en två-pass randomiserad streaming algoritm för Dyck(2) med utrymme O((log n) 2 ), tid polylog(n) och ensidig fel, där det andra passet är i omvänd riktning. Båda algoritmerna kan utvidgas till Dyck(s) eftersom detta problem är reducible till Dyck(2) för en lämplig uppfattning om minskning i streaming modellen. Med undantag för en extra O( ε logs ) multiplicativ overhead i det utrymme som krävs i one-pass algoritmen, resurskraven är i samma ordning. För den nedre gränsen, uppvisar vi hårda instanser Uppstigning(m) av Dyck(2) med längd (mn). Vi inbäddade dessa i vad vi kallar ett "en-pass" kommunikationsproblem med 2m-spelare, där m = Õ(n). För att fastställa hårdheten i Ascension(m) bevisar vi ett direkt resultat genom att följa "informationskostnaden" metoden, men med några *
När det finns en utrymmesbegränsning, Magniez, Mathieu och Nayak Ref beaktade streaming komplexiteten av att känna igen DYCK(s) som visar en lägre gräns och en matchande övre gräns inom en log n faktor.
Recognizing well-parenthesized expressions in the streaming model
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}