The Third Homomorphism Theorem
Jeremy Gibbons
Abstract
The Third Homomorphism Theorem is a folk theorem of the constructive algorithmics community. It states that a function on lists that can be computed both from left to right and from right to left is necessarily a list homomorphism - it can be computed according to any parenthesization of the list. We formalize and prove the theorem, and describe two practical applications: to fast parallel algorithms for language recognition problems and for downwards accumulations on trees.
Details
| Journal |
Journal of Functional Programming |
| Note |
Earlier version appeared in B. Jay‚C. editor‚ Computing: The Australian Theory Seminar‚ Sydney‚ December 1994‚ 62–6p.9 |
| Number |
4 |
| Pages |
657–665 |
| Volume |
6 |
| Year |
1996 |
Links
Related pages
|
People |
|
|
Activities |