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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper, a compressed membership problem for finite automata, bothdeterministic and non-deterministic, with compressed transition labels isstudied. The compression is represented by straight-line programs (SLPs), i.e.context-free grammars generating exactly one string. A novel technique ofdealing with SLPs is introduced: the SLPs are recompressed, so that substringsof the input text are encoded in SLPs labelling the transitions of the NFA(DFA) in the same way, as in the SLP representing the input text. To this end,the SLPs are locally decompressed and then recompressed in a uniform way.Furthermore, such recompression induces only small changes in the automaton, inparticular, the size of the automaton remains polynomial.  Using this technique it is shown that the compressed membership for NFA withcompressed labels is in NP, thus confirming the conjecture of Plandowski andRytter and extending the partial result of Lohrey and Mathissen; as it isalready known, that this problem is NP-hard, we settle its exact computationalcomplexity. Moreover, the same technique applied to the compressed membershipfor DFA with compressed labels yields that this problem is in P; for thisproblem, only trivial upper-bound PSPACE was known.

Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)