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

We investigate the problem of succinctly representing an arbitrarypermutation, \pi, on {0,...,n-1} so that \pi^k(i) can be computed quickly forany i and any (positive or negative) integer power k. A representation taking(1+\epsilon) n lg n + O(1) bits suffices to compute arbitrary powers inconstant time, for any positive constant \epsilon <= 1. A representation takingthe optimal \ceil{\lg n!} + o(n) bits can be used to compute arbitrary powersin O(lg n / lg lg n) time.  We then consider the more general problem of succinctly representing anarbitrary function, f: [n] \rightarrow [n] so that f^k(i) can be computedquickly for any i and any integer power k. We give a representation that takes(1+\epsilon) n lg n + O(1) bits, for any positive constant \epsilon <= 1, andcomputes arbitrary positive powers in constant time. It can also be used tocompute f^k(i), for any negative integer k, in optimal O(1+|f^k(i)|) time.  We place emphasis on the redundancy, or the space beyond theinformation-theoretic lower bound that the data structure uses in order tosupport operations efficiently. A number of lower bounds have recently beenshown on the redundancy of data structures. These lower bounds confirm thespace-time optimality of some of our solutions. Furthermore, the redundancy ofone of our structures "surpasses" a recent lower bound by Golynski [Golynski,SODA 2009], thus demonstrating the limitations of this lower bound.

Succinct Representations of Permutations and Functions