Vi presenterar utrymme lägre gränser för online mönster matchning under ett antal olika avstånd åtgärder. Med tanke på ett mönster av längd m och en text som anländer ett tecken i taget, det online mönster matchande problemet är att rapportera avståndet mellan mönstret och ett skjutfönster av texten så snart det nya tecknet anländer. Vi kräver att rätt svar ges på varje position med konstant sannolikhet. Vi ger en (m) bit utrymme lägre gränser för L1, L2, Lņ, Hamming, redigera och byta avstånd samt för alla algoritmer som beräknar korskorrelering/konvolution. Vi visar sedan en dikotomi mellan avståndsfunktioner som har wildcard-liknande egenskaper och de som inte gör det. I det tidigare fallet som inkluderar, som exempel, mönster som matchar med teckenklasser, ger vi en (m) bit utrymme lägre gränser. För andra avståndsfunktioner visar vi att det finns utrymmesgränser för  och O(log 2 m) bitar. Slutligen diskuterar vi rymdens lägre gränser för icke-binära ingångar och visar hur de i vissa fall kan förbättras.
REF visar också flera nedre gränser för online mönster matchning problem.
Space Lower Bounds for Online Pattern Matching
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}