Entropies and combinatorics of random branching processes and context-free languages

Abstract

The entropies and combinatorics of trees that branch according to fixed but finite numbers of rules are studied. Context-free grammars are used to categorize the ways in which nodes branch to yield daughter nodes, thus providing an organized setting to examine the entropies for random branching processes whose realizations are trees and whose probabilities are determined by probabilities associated with the substitution rules of the grammar. Normalized entropy rates H are derived for the critical branching rate and supercritical branching rate processes. An equipartition theorem is proved for the supercritical processes. A strong departure from classical theorems for Markov sources occurs for supercritical branching processes as the typical sets have supergeometric growth rates. The combinatorics of the set of all trees that can be generated from the context-free substitution rules is also studied.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>