A new technique for obtaining lower bounds on the worst-case time-complexity of optimization problems in the linear decision tree model of computation is presented. This technique is then used to obtain a tight $\Omega (n\log n)$ lower bound for a problem of finding a minimum cost triangulation of a convex polygon with weighted vertices. This problem is similar to the problem of finding an optimal order of computing a matrix chain product. If the lower bound technique could be extended to bounded degree algebraic decision trees, a tight $\Omega (n\log n)$ lower bound for this latter problem would be obtained.

There is a well-known class of algorithms for permuting symbols which has been formally characterized by a device called a pushdown permuter. Two theorems attempting to characterize the type of permutations that can be achieved by a pushdown permuter have appeared in the literature. Counter-examples to these theorems have also appeared in the literature. This paper presents a correct statement of this theorem.