Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information-theoretically optimal number of bits along with supporting queries on them efficiently. Towards this goal, we first design a succinct data structure for representing any deterministic finite automaton @math having @math states over a @math -letter alphabet @math using @math bits of space, which can determine, given an input string @math over @math , whether @math accepts @math in @math time, using constant words of working space. When the input deterministic finite automaton is acyclic, not only we can improve the above space-bound significantly to @math bits, we also obtain optimal query time for string acceptance checking. More specifically, using our succinct representation, we can check if a given input string @math can be accepted by the acyclic deterministic finite automaton using time proportional to the length of @math , hence, the optimal query time. We also exhibit a succinct data structure for representing a non-deterministic finite automaton @math having @math states over a @math -letter alphabet @math using @math bits of space, such that given an input string @math , we can decide whether @math accepts @math efficiently in @math time. Finally, we also provide time and space-efficient algorithms for performing several standard operations such as union, intersection, and complement on the languages accepted by deterministic finite automata.
The field of succinct data structures originally started with the work of Jacobson @cite_11 , and by now it is a relatively mature field in terms of breadth of problems considered. To illustrate this further, there already exists a large body of work on representing various combinatorial objects succinctly. A partial list of such combinatorial objects would be trees @cite_19 @cite_18 , various special graph classes like planar graphs @cite_6 , chordal graphs @cite_23 , partial @math -trees @cite_7 , interval graphs @cite_20 along with arbitrary general graphs @cite_0 , permutations @cite_21 , functions @cite_21 , bitvectors @cite_15 among many others. We refer the reader to the recent book by Navarro @cite_16 for a comprehensive treatment of this field. The study of succinct data structures is motivated by both theoretical curiosity and also by the practical needs as these combinatorial structures do arise quite often in various applications.
@cite_18 @cite_7 @cite_21 @cite_6 @cite_0 @cite_19 @cite_23 @cite_15 @cite_16 @cite_20 @cite_11
2147935317 1988115395 1987699222 2024465063 1993294649 2093788424 2907584067 1974033543 2517241835 2964624700 127947978
We propose new succinct representations of ordinal trees and match various space time lower bounds. It is known that any n-node static tree can be represented in 2n p o(n) bits so that a number of operations on the tree can be supported in constant time under the word-RAM model. However, the data structures are complicated and difficult to dynamize. We propose a simple and flexible data structure, called the range min-max tree, that reduces the large number of relevant tree operations considered in the literature to a few primitives that are carried out in constant time on polylog-sized trees. The result is extended to trees of arbitrary size, retaining constant time and reaching 2n p O(n polylog(n)) bits of space. This space is optimal for a core subset of the operations supported and significantly lower than in any previous proposal. For the dynamic case, where insertion deletion (indels) of nodes is allowed, the existing data structures support a very limited set of operations. Our data structure builds on the range min-max tree to achieve 2n p O(n log n) bits of space and O(log n) time for all operations supported in the static scenario, plus indels. We also propose an improved data structure using 2n p O(nlog log n log n) bits and improving the time to the optimal O(log n log log n) for most operations. We extend our support to forests, where whole subtrees can be attached to or detached from others, in time O(log1pe n) for any e > 0. Such operations had not been considered before. Our techniques are of independent interest. An immediate derivation yields an improved solution to range minimum maximum queries where consecutive elements differ by ± 1, achieving n p O(n polylog(n)) bits of space. A second one stores an array of numbers supporting operations sum and search and limited updates, in optimal time O(log n log log n). A third one allows representing dynamic bitmaps and sequences over alphabets of size σ, supporting rank select and indels, within zero-order entropy bounds and time O(log n log σ (log log n)2) for all operations. This time is the optimal O(log n log log n) on bitmaps and polylog-sized alphabets. This improves upon the best existing bounds for entropy-bounded storage of dynamic sequences, compressed full-text self-indexes, and compressed-space construction of the Burrows-Wheeler transform. Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is Ω(logn) bits. We investigate the problem of succinctly representing an arbitrary permutation, @p, on 0,...,n-1 so that @p^k(i) can be computed quickly for any i and any (positive or negative) integer power k. A representation taking (1+@e)nlgn+O(1) bits suffices to compute arbitrary powers in constant time, for any positive constant @e@?1. A representation taking the optimal @?lgn!@?+o(n) bits can be used to compute arbitrary powers in O(lgn lglgn) time. We then consider the more general problem of succinctly representing an arbitrary function, f:[n]->[n] so that f^k(i) can be computed quickly for any i and any integer power k. We give a representation that takes (1+@e)nlgn+O(1) bits, for any positive constant @e@?1, and computes arbitrary positive powers in constant time. It can also be used to compute 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 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. This paper addresses the problem of representing the connectivity information of geometric objects, using as little memory as possible. As opposed to raw compression issues, the focus here is on designing data structures that preserve the possibility of answering incidence queries in constant time. We propose, in particular, the first optimal representations for 3-connected planar graphs and triangulations, which are the most standard classes of graphs underlying meshes with spherical topology. Optimal means that these representations asymptotically match the respective entropy of the two classes, namely 2 bits per edge for 3-connected planar graphs, and 1.62 bits per triangle, or equivalently 3.24 bits per vertex for triangulations. These representations support adjacency queries between vertices and faces in constant time. We consider the problem of encoding graphs with n vertices and m edges compactly supporting adjacency, neighborhood and degree queries in constant time in the @Q(logn)-bit word RAM model. The adjacency query asks whether there is an edge between two vertices, the neighborhood query reports the neighbors of a given vertex in constant time per neighbor, and the degree query reports the number of incident edges to a given vertex. We study the problem in the context of succinctness, where the goal is to achieve the optimal space requirement as a function of n and m, to within lower order terms. We prove a lower bound in the cell probe model indicating it is impossible to achieve the information-theory lower bound up to lower order terms unless the graph is either too sparse (namely, m=o(n^@d) for any constant @d>0) or too dense (namely m=@w(n^2^-^@d) for any constant @d>0). Furthermore, we present a succinct encoding of graphs supporting aforementioned queries in constant time. The space requirement of the encoding is within a multiplicative 1+@e factor of the information-theory lower bound for any arbitrarily small constant @e>0. This is the best achievable space bound according to our lower bound where it applies. The space requirement of the representation achieves the information-theory lower bound tightly within lower order terms where the graph is very sparse (m=o(n^@d) for any constant @d>0), or very dense (m>n^2 lg^1^-^@dn for an arbitrarily small constant @d>0). We consider the implementation of abstract data types for the static objects: binary tree, rooted ordered tree, and a balanced sequence of parentheses. Our representations use an amount of space within a lower order term of the information theoretic minimum and support, in constant time, a richer set of navigational operations than has previously been considered in similar work. In the case of binary trees, for instance, we can move from a node to its left or right child or to the parent in constant time while retaining knowledge of the size of the subtree at which we are positioned. The approach is applied to produce a succinct representation of planar graphs in which one can test adjacency in constant time. We consider the indexable dictionary problem, which consists of storing a set S ⊆ 0,…,m − 1 for some integer m while supporting the operations of rank(x), which returns the number of elements in S that are less than x if x ∈ S, and −1 otherwise; and select(i), which returns the ith smallest element in S. We give a data structure that supports both operations in O(1) time on the RAM model and requires B(n, m) p o(n) p O(lg lg m) bits to store a set of size n, where B(n, m) e ⌊lg (m n)⌋ is the minimum number of bits required to store any n-element subset from a universe of size m. Previous dictionaries taking this space only supported (yes no) membership queries in O(1) time. In the cell probe model we can remove the O(lg lg m) additive term in the space bound, answering a question raised by Fich and Miltersen [1995] and Pagh [2001]. We present extensions and applications of our indexable dictionary data structure, including: —an information-theoretically optimal representation of a k-ary cardinal tree that supports standard operations in constant time; —a representation of a multiset of size n from 0,…,m − 1 in B(n, m p n) p o(n) bits that supports (appropriate generalizations of) rank and select operations in constant time; and p O(lg lg m) —a representation of a sequence of n nonnegative integers summing up to m in B(n, m p n) p o(n) bits that supports prefix sum queries in constant time. Compact data structures help represent data in reduced space while allowing it to be queried, navigated, and operated in compressed form. They are essential tools for efficiently handling massive amounts of data by exploiting the memory hierarchy. They also reduce the resources needed in distributed deployments and make better use of the limited memory in low-end devices. The field has developed rapidly, reaching a level of maturity that allows practitioners and researchers in application areas to benefit from the use of compact data structures. This first comprehensive book on the topic focuses on the structures that are most relevant for practical use. Readers will learn how the structures work, how to choose the right ones for their application scenario, and how to implement them. Researchers and students in the area will find in the book a definitive guide to the state of the art in compact data structures. Data compression is when you take a big chunk of data and crunch it down to fit into a smaller space. That data is put on ice; you have to un-crunch the compressed data to get at it. Data optimization, on the other hand, is when you take a chunk of data plus a collection of operations you can perform on that data, and crunch it into a smaller space while retaining the ability to perform the operations efficiently. This thesis investigates the problem of data optimization for some fundamental static data types, concentrating on linked data structures such as trees. I chose to restrict my attention to static data structures because they are easier to optimize since the optimization can be performed off-line. Data optimization comes in two different flavors: concrete and abstract. Concrete optimization finds minimal representations within a given implementation of a data structure; abstract optimization seeks implementations with guaranteed economy of space and time. I consider the problem of concrete optimization of various pointer-based implementations of trees and graphs. The only legitimate use of a pointer is as a reference, so we are free to map the pieces of a linked structure into memory as we choose. The problem is to find a mapping that maximizes overlap of the pieces, and hence minimizes the space they occupy. I solve the problem of finding a minimal representation for general unordered trees where pointers to children are stored in a block of consecutive locations. The algorithm presented is based on weighted matching. I also present an analysis showing that the average number of cons-cells required to store a binary tree of n nodes as a minimal binary DAG is asymptotic to @math lg @math . Methods for representing trees of n nodes in @math ( @math ) bits that allow efficient tree-traversal are presented. I develop tools for abstract optimization based on a succinct representation for ordered sets that supports ranking and selection. These tools are put to use in a building an @math ( @math )-bit data structure that represents n-node planar graphs, allowing efficient traversal and adjacency-testing.