In 1971, J.H. Conway [Con71] published a slim volume entitled "Regular Algebra and Finite Machines" which was to have great influence on my own work (eg. [Bac06]). I was particularly impressed by the chapter on factor theory and its subsequent application in the construction of biregulators. Although some elements of Conway's book are now well cited, this part of the book still appears to be much less well known. The goal of this talk is to explain why factor theory is important in the design of algorithms. We introduce Conway's factor matrix and then show how the (unique) reflexive-transitive-reduction of the factor matrix, dubbed the "factor graph" [Bac75], is the basis of the well-known Knuth-Morris-Pratt pattern-matching algorithm [KMP77, BL77]. This serves as an appetiser for a review of fixed-point theory and Galois connections, focusing particularly on the relevance of the theory in the design of algorithms. We then return to factor theory and how it forms the basis of practical applications in program analysis [SdML04]. We conclude with some speculation on how a greater focus on factorisation might help us to better understand the complexity of algorithms.
展开▼
