Convergence (logic)
Encyclopedia
In mathematics
, computer science
and logic
, convergence refers to the idea that a series of transformations come to a conclusion in a finite amount of time (the transformations are terminating
), and that the conclusion reached is independent of the path taken to get to it (they are confluent
).
More formally, a set of term rewriting transformations are said to be convergent if they are confluent
and terminating
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, convergence refers to the idea that a series of transformations come to a conclusion in a finite amount of time (the transformations are terminating
Newman's lemma
In the theory of rewriting systems, Newman's lemma states that a terminating abstract rewriting system , that is, one in which there are no infinite reduction sequences, is confluent if it is locally confluent...
), and that the conclusion reached is independent of the path taken to get to it (they are confluent
Confluence (abstract rewriting)
In computer science, confluence is a property of rewriting systems, describing that terms in this system can be rewritten in more than one way, to yield the same result. This article describes the properties in the most abstract setting of an abstract rewriting system.- Motivating example :Consider...
).
More formally, a set of term rewriting transformations are said to be convergent if they are confluent
Confluence (abstract rewriting)
In computer science, confluence is a property of rewriting systems, describing that terms in this system can be rewritten in more than one way, to yield the same result. This article describes the properties in the most abstract setting of an abstract rewriting system.- Motivating example :Consider...
and terminating
Newman's lemma
In the theory of rewriting systems, Newman's lemma states that a terminating abstract rewriting system , that is, one in which there are no infinite reduction sequences, is confluent if it is locally confluent...
.