# Thinning Theorem

## Constructing datatype-generic fully polynomial-time approximation schemes using generalised thinning

Shin-Cheng Mu, Yu-Han Lyu, and Akimasa Morihata. Constructing datatype-generic fully polynomial-time approximation schemes using generalised thinning. In the 6th ACM SIGPLAN workshop on Generic programming (WGP 2010), pages 97-108, Sep. 2010. [PDF]

## The Pruning Theorem: Thinning Based on a Loose Notion of Monotonicity

Any preorder R induces a lax preorder ∋ . R. If a relation S is monotonic on R∘, it is monotonic on lax preorder ∋ . R. Furthermore, prune (∋ . R) = thin R. Therefore, pruning is a generalisation of thinning. We need the notion of lax preorders because, for some problems, the generating relation S is monotonic on a lax preorder, but not a preorder.

## Proving the Thinning Theorem by Fold Fusion

Prove the thinning theorem by fold fusion. Horrifyingly, I could not do it anymore! Have my skills become rusty due to lack of practice in the past few years?

## Maximum Segment Sum and Density with Bounded Lengths

It may be surprising that variations of the maximum segment sum (MSS) problem, a textbook example for the squiggolists, are still active topics for algorithm designers. These literate Haskell scripts presents a program solving two recently studied variations: computing the maximum sum of segments not longer than an upper-bound, and the maximum density (average) of segments not shorter than a lower-bound. 2007/06/26 Update: fixed binary search.
2007/11/04 Update: linear time algorithm for MSDL.

## Countdown: a case study in origami programming

R. S. Bird and S-C. Mu, Countdown: a case study in origami programming. In Journal of Functional Programming Vol. 15(5), pp. 679-702, 2005.
[GZipped Postscript]

## A Calculational Approach to Program Inversion

S-C. Mu, A Calculational Approach to Program Inversion. D.Phil Thesis. Oxford University Computing Laboratory. March 2003
[GZipped Postscript][PDF]

## Algebraic methods for optimisation problems

R. S. Bird, J. Gibbons and S-C. Mu, Algebraic methods for optimisation problems. In Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, LNCS 2297, pp. 281-307, January 2002.
[PDF]

## Algebraic Methods for Optimisation Problems (Transfering dissertation)

S-C. Mu, Algebraic Methods for Optimisation Problems. Transfering dissertation.

## Optimisation problems in logic programming: an algebraic approach

S. Seres and S-C. Mu, Optimisation problems in logic programming: an algebraic approach. In Proceedings of LPSE’00, July 2000.
[GZipped Postscript]