Type Classes of Tree Models
Álvaro Martín, G. Seroussi, M.J. Weinberger · 2007
It is well known that a tree model does not always admit a finite-state machine (FSM) representation with the same (minimal) number of parameters. Therefore, known characterizations of type classes for FSMs do not apply, in general, to tree models. In this paper, the type class of a string with respect to a tree model is studied, and an exact formula is derived for the size of the class. The formula, which applies to arbitrary trees, generalizes Whittle's formula for FSMs. The derivation is more intricate than the FSM case, since some basic properties of FSM types do not hold in general for tree-model types. The derivation also yields an efficient enumeration of the tree-model type class, which has applications in universal data compression and universal simulation. A formula for the number of type classes with respect to a given tree is also derived. The formula is asymptotically tight up to multiplication by a constant and also generalizes a known result for FSMs.