Quasi-Monotonic Sequences: Theory, Algorithms and Applications
Andrzej Ehrenfeucht, Jeffrey Haemer, David H. Haussler · SIAM Journal on Algebraic and Discrete Methods · 1987
We present a simple algebraic theory which allows us to solve a variety of combinatorial problems, including the problem of finding convex hulls in two dimensions, the “Trip Around the Moon” problem, a version of the ballot problem, and the problem of enumerating and randomly generating ordered trees of a given size. Individual problems are solved by applying general algorithms and theorems developed within this algebraic theory.