Confluent (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
A reduction system is called confluent (or globally confluent) if, for all 
, 
, and 
such that 
and 
, there exists a 
such that 
and 
. A reduction system is said to be locally confluent if, for all 
, 
,
such that 
and 
, there exists a 
such that 
and 
. Here, the notation 
indicates that 
is reduced to 
in one step, and 
indicates that 
is reduced to 
in zero or more steps.
A reduction system is confluent iff it has Church-Rosser property (Wolfram 2002, p. 1036). In finitely terminating reduction systems, global and local confluence are equivalent, for instance in the systems shown above. Reduction systems that are both finitely terminating and confluent are called convergent. In a convergent reduction system, unique normal forms exist for all expressions.
The problem of determining whether a given reduction system is confluent is recursively undecidable.
The property of being confluent is called confluence. Confluence is a necessary condition for causal invariance.
See also
Causal Invariance, Confluent Hypergeometric Differential Equation, Confluent Hypergeometric Function of the First Kind, Confluent Hypergeometric Function of the Second Kind, Critical Pair, Knuth-Bendix Completion Algorithm, Multiway System, Reduction Order
Portions of this entry contributed by Todd Rowland
Portions of this entry contributed by Alex Sakharov (author's link)
Explore with Wolfram|Alpha
References
Baader, F. and Nipkow, T. Term Rewriting and All That. Cambridge, England: Cambridge University Press, 1999.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 507 and 1036-1037, 2002.
Referenced on Wolfram|Alpha
Cite this as:
Rowland, Todd; Sakharov, Alex; and Weisstein, Eric W. "Confluent." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Confluent.html