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.

Confluent interpolation

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 functions

The 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 systems

A 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:

y_1 \xleftarrow{*} x \xrightarrow{*} y_2 \implies y_1 \downarrow y_2

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 posts

Leave a Reply

Your email address will not be published. Required fields are marked *