Browsing by Subject "Stochastic grammars"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Information theory of random trees induced by stochastic grammars.
    (2012-05) Oh, Sang-youn
    Previous research has been done on the information theory of binary random rooted tree models in which every nonleaf vertex in a tree has exactly two children. Let α be a positive integer parameter > 2. The main contribution of this thesis is to extend the information theory results for binary random tree models to α-random tree models, which are random tree models in which up to α children per each nonleaf vertex are allowed. An α-random random tree model consists of a sequence {Tn : n = 2, 3, · · · }, in which each Tn is an α-random tree having n leaves, and there is a context-free grammar describing how each Tn is randomly generated. In particular, balanced α-random tree models are examined, meaning that the context-free grammars which are employed satisfy a type of balance condition. We obtain three types of results for α-random tree models, described as follows. First, given a general α-random tree model {Tn}, the entropy H(Tn) of each tree Tn is expressed as a recursive formula relating H(Tn) to the entropies of its subtrees. This recursion can be explicitly solved for some random tree models, and we show how this can be done for the binary random search tree model. Our second set of results, which are our main results, concern the balanced α-random tree model {Tn}. Defining the entropy rate of Tn as the ratio H(Tn)/n, we examine the asymptotic behavior of the entropy rate as n grows without bound. This asymptotic behavior is described via a continuous non-constant periodic function P#11; → [0,∞), having period one, satisfying the property that H(Tn)/n = P#11;(log#11; n) for every n. The graph of P#11; is seen as a fractal and its fractal properties along with its fractal dimension are investigated. We develop a direct and indirect way of describing P#11;. The direct way expresses the graph of P#11; as the attractor of an iterated function system which is explicitly given. The indirect way obtains P#11; via a change of variable on a hierarchical entropy function discovered by J. Kieffer. Our third and final set of results concern the development of compression methods for some α-random tree models {Tn}. In the case in which each random tree Tn is not equiprobable over the ensemble of trees in which it takes it values, we develop a encoding method via which Tn is uniquely represented by a variable-length binary codeword, so that the expected codeword length is roughly equal to the entropy H(Tn). In the case of the balanced α-random tree model, each Tn is equiprobable, which allows us to develop encoding methods via which each Tn is uniquely represented by a fixed-length binary codeword of minimal length ⌈H(Tn)⌉. One of the encoding methods discussed employs an one-to-one mapping of the ensemble of Tn into one of the hierarchical type classes discovered by J. Kieffer, allowing Kieffer’s method for encoding hierarchical type classes to be adapted to an encoding method for balanced α-random trees.