English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Motivated by a concrete problem and with the goal of understanding the sensein which the complexity of streaming algorithms is related to the complexity offormal languages, we investigate the problem Dyck(s) of checking matchingparentheses, with $s$ different types of parenthesis.  We present a one-pass randomized streaming algorithm for Dyck(2) with space$\Order(\sqrt{n}\log n)$, time per letter $\polylog (n)$, and one-sided error.We prove that this one-pass algorithm is optimal, up to a $\polylog n$ factor,even when two-sided error is allowed. For the lower bound, we prove a directsum result on hard instances by following the "information cost" approach, butwith a few twists. Indeed, we play a subtle game between public and privatecoins. This mixture between public and private coins results from a balancingact between the direct sum result and a combinatorial lower bound for the basecase.  Surprisingly, the space requirement shrinks drastically if we have access tothe input stream in reverse. We present a two-pass randomized streamingalgorithm for Dyck(2) with space $\Order((\log n)^2)$, time $\polylog (n)$ andone-sided error, where the second pass is in the reverse direction. Bothalgorithms can be extended to Dyck(s) since this problem is reducible toDyck(2) for a suitable notion of reduction in the streaming model.

Recognizing well-parenthesized expressions in the streaming model