Please use this identifier to cite or link to this item:

`http://hdl.handle.net/2381/28330`

Title: | Succinct representations of permutations and functions |

Authors: | Munro, J. Ian Raman, Rajeev Raman, Venkatesh Rao, Satti Srinivasa |

First Published: | 22-Jun-2012 |

Publisher: | Elsevier |

Citation: | Theoretical Computer Science, 2012, 438, pp. 47-88 |

Abstract: | We investigate the problem of succinctly representing an arbitrary permutation, π, on {0, . . . , n−1} so that π[superscript k](i) can be computed quickly for any i and any (positive or negative) integer power k. A representation taking (1 + ϵ)n lg n + O(1) bits suffices to compute arbitrary powers in constant time, for any positive constant ϵ ≤ 1. A representation taking the optimal ⌈lg n!⌉ + o(n) bits can be used to compute arbitrary powers in O(lg n/ lg lg n) time. We then consider the more general problem of succinctly representing an arbitrary function, f : [n] → [n] so that f[superscript k](i) can be computed quickly for any i and any integer power k. We give a representation that takes (1 + ϵ)n lg n + O(1) bits, for any positive constant ϵ ≤ 1, and computes arbitrary positive powers in constant time. It can also be used to compute f[superscript k](i), for any negative integer k, in optimal O(1+ | f[superscript k](i) |) time. We place emphasis on the redundancy, or the space beyond the information-theoretic lower bound that the data structure uses in order to support operations efficiently. A number of lower bounds have recently been shown on the redundancy of data structures. These lower bounds confirm the space–time optimality of some of our solutions. Furthermore, the redundancy of one of our structures "surpasses" a recent lower bound by Golynski [Golynski, SODA 2009], thus demonstrating the limitations of this lower bound. |

DOI Link: | 10.1016/j.tcs.2012.03.005 |

ISSN: | 0304-3975 |

Links: | http://www.sciencedirect.com/science/article/pii/S0304397512002253 http://hdl.handle.net/2381/28330 |

Version: | Post-print |

Status: | Peer-reviewed |

Type: | Journal Article |

Rights: | Copyright © 2012 Elsevier B.V. Deposited with reference to the publisher’s open access archiving policy. |

Description: | NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical Computer Science, 2012, 438, pp. 47-88, DOI: 10.1016/j.tcs.2012.03.005. |

Appears in Collections: | Published Articles, Dept. of Computer Science |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

tcs-toplevel.pdf | Post-review (final submitted) | 376.75 kB | Adobe PDF | View/Open |

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.