Three kinds of confluence
We say someone is fluent in a language if their words flow easily. The word fluent comes from the Latin fluere which means to flow. We say things are confluent if they flow together, such as the confluence of two streams.
This post will give three examples of the use of confluent in math and computer science:
- confluent interpolation,
- confluent functions, and
- confluent reduction systems.
Interpolation fills in the gaps between locations where a function's values are known. If you're given the values of a function f(x) at n+1 distinct points, there is a unique polynomial of degree n that takes on those values at those points.
Notice the above paragraph stipulated distinct points. If two of your point are actually different labels for the same point, your interpolation problem is either inconsistent and over-determined, or it is consistent but under-determined.
Suppose you have two points x1 and x2 that start out as distinct but move together. Once they become equal, information is lost. But if you kept track of the slope of the line joining f(x1) and f(x2) as the points moved together, in the limit you have the derivative f '(x1). The derivative restores information that otherwise would have been lost.
Confluent interpolation specifies the values of the function f(x) at distinct points. At doubled points, it specifies a consistent function value and the value of the derivative.
Incidentally, just as the Vandermonde matrix arises in ordinary interpolation, the confluent Vandermonde matrix arises in confluent interpolation.
Confluent functionsThe previous post showed that the error function erf(x) is closely related to a special function known as a confluent hypergeometric function."
The hypergeometric differential equation has regular singular points at 0, 1, and . If we take a limit that pushes the singularity at 1 off to , we get Kummer's differential equation, the equation satisfied by confluent hypergeometric functions.
Confluent reduction systemsA reduction system is said to be confluent if whenever a term x can be reduced in a finite number of steps to two different terms y1 and y2, there is a common term that both y1 and y2 can be reduced to. In symbols:
The Church-Rosser theorem says that lambda calculus is confluent. If two ways of applying reduction rules to the same lambda expression terminate, they terminate in the same expression. Not all term rewriting systems are confluent, but lambda calculus is.
Related postsThe post Three kinds of confluence first appeared on John D. Cook.