Church–Rosser property
E143338
The Church–Rosser property is a confluence property of rewriting systems stating that if an expression can be reduced in different ways, all reduction paths can be further reduced to a common equivalent form.
All labels observed (3)
| Label | Occurrences |
|---|---|
| Church–Rosser property canonical | 1 |
| Church–Rosser theorem | 1 |
| Newman’s lemma | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T1255161 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Church–Rosser property Context triple: [lambda calculus, hasConcept, Church–Rosser property]
-
A.
Knuth–Bendix completion algorithm
The Knuth–Bendix completion algorithm is a procedure in term rewriting and automated theorem proving that transforms a set of equations into a confluent rewriting system, enabling decision of word problems in algebraic structures.
-
B.
Church–Turing thesis
The Church–Turing thesis is a foundational principle in computability theory stating that any function that can be effectively computed by an algorithm can be computed by a Turing machine (or equivalently by other formal models of computation).
-
C.
Entscheidungsproblem
The Entscheidungsproblem is a foundational decision problem in mathematical logic that asks whether there exists a general algorithm to determine the truth or falsity of any given first-order logical statement.
-
D.
Hilbert’s program
Hilbert’s program was an influential early-20th-century initiative in the foundations of mathematics that sought to formalize all of mathematics and prove its consistency using finitistic methods.
-
E.
lambda calculus
Lambda calculus is a formal system in mathematical logic and computer science that uses function abstraction and application to investigate computation and serves as a foundational model for programming languages.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Church–Rosser property Target entity description: The Church–Rosser property is a confluence property of rewriting systems stating that if an expression can be reduced in different ways, all reduction paths can be further reduced to a common equivalent form.
-
A.
Knuth–Bendix completion algorithm
The Knuth–Bendix completion algorithm is a procedure in term rewriting and automated theorem proving that transforms a set of equations into a confluent rewriting system, enabling decision of word problems in algebraic structures.
-
B.
Church–Turing thesis
The Church–Turing thesis is a foundational principle in computability theory stating that any function that can be effectively computed by an algorithm can be computed by a Turing machine (or equivalently by other formal models of computation).
-
C.
Entscheidungsproblem
The Entscheidungsproblem is a foundational decision problem in mathematical logic that asks whether there exists a general algorithm to determine the truth or falsity of any given first-order logical statement.
-
D.
Hilbert’s program
Hilbert’s program was an influential early-20th-century initiative in the foundations of mathematics that sought to formalize all of mathematics and prove its consistency using finitistic methods.
-
E.
lambda calculus
Lambda calculus is a formal system in mathematical logic and computer science that uses function abstraction and application to investigate computation and serves as a foundational model for programming languages.
- F. None of above. chosen
Statements (45)
| Predicate | Object |
|---|---|
| instanceOf |
confluence property
ⓘ
mathematical property ⓘ property of rewriting systems ⓘ |
| alsoKnownAs |
Church–Rosser property
ⓘ
surface form:
Church–Rosser theorem
diamond property ⓘ |
| appliesTo |
abstract reduction systems
ⓘ
equational theories ⓘ lambda terms ⓘ rewriting systems ⓘ |
| concerns | joinability of reduction sequences ⓘ |
| contrastsWith | local confluence without termination ⓘ |
| coreIdea | different reduction paths from the same term can be joined ⓘ |
| describes | confluence of a rewriting relation ⓘ |
| ensures | if a term has a normal form then that normal form is unique up to equivalence ⓘ |
| equivalentTo | every pair of convertible terms is joinable ⓘ |
| expressedAs | for all x,y,z: if x →* y and x →* z then there exists w with y →* w and z →* w ⓘ |
| field |
lambda calculus
ⓘ
mathematical logic ⓘ term rewriting systems ⓘ theoretical computer science ⓘ |
| formalizes | if two terms are convertible then they have a common reduct ⓘ |
| guarantees | determinacy of results of computation modulo equivalence ⓘ |
| hasConsequence | confluent systems have unique normal forms if they are normalizing ⓘ |
| historicalContext | introduced in the study of the lambda calculus in the 1930s ⓘ |
| implies | uniqueness of normal forms up to equivalence ⓘ |
| involves | equivalence relation generated by a reduction relation ⓘ |
| isPropertyOf |
beta-reduction in the untyped lambda calculus
ⓘ
many terminating term rewriting systems ⓘ |
| mathematicalDomain |
category theory
ⓘ
universal algebra ⓘ |
| namedAfter |
Alonzo Church
ⓘ
J. Barkley Rosser ⓘ |
| namedInHonorOf |
Alonzo Church
ⓘ
surface form:
Alonzo Church and J. Barkley Rosser
|
| relatedTo |
Church–Rosser property
self-linksurface differs
ⓘ
surface form:
Newman’s lemma
beta-reduction ⓘ confluence ⓘ lambda calculus reduction ⓘ local confluence ⓘ normal form ⓘ |
| requires | a binary reduction relation on terms ⓘ |
| typeOf | global confluence property ⓘ |
| usedIn |
automated theorem proving
ⓘ
equational reasoning ⓘ programming language semantics ⓘ proof theory ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Church–Rosser property Description of subject: The Church–Rosser property is a confluence property of rewriting systems stating that if an expression can be reduced in different ways, all reduction paths can be further reduced to a common equivalent form.
Referenced by (3)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Church–Rosser theorem
this entity surface form:
Newman’s lemma