We present a CAT (constant amortized time) algorithm for generating those partitions of that are in the (), a generalization of the (). More precisely, for any fixed integer , we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice (): this lets us design an algorithm which generates all the ice piles of () in amortized time (1) and in space ().
We present a CAT (constant amortized time) algorithm for generating those partitions of that are in the (), a generalization of the (). More precisely, for any fixed integer , we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice (): this lets us design an algorithm which generates all the ice piles of () in amortized time (1) and in space ().
In this work we study some probabilistic models for the random generation of words over a given alphabet used in the literature in connection with pattern statistics. Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position only depends on a finite number of previous occurrences) and the stochastic models that can generate a word of given length from a regular language under uniform distribution. We present some results that show the differences...
Page 1