Journal article icon

Journal article

The Third Homomorphism Theorem

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.

Actions


Authors


More by this author
Institution:
University of Oxford
Department:
Mathematical, Physical and Life Sciences Division - Department of Computer Science
Journal:
Journal of Functional Programming
Volume:
6
Issue:
4
Pages:
657-665
Publication date:
1996
URN:
uuid:9d4f43b2-b06b-4441-acee-86a8972bc1b2
Local pid:
cs:2365

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP