Church–Rosser theorem
In lambda calculus, the Church–Rosser theorem states that, when applying reduction rules to terms, the ordering in which the reductions are chosen does not make a difference to the eventual result. More precisely, if there are two distinct reductions or sequences of reductions that can be applied to the same term, then there exists a term that is reachable from both results, by applying (possibly empty) sequences of additional reductions. The theorem was proved in 1936 by Alonzo Church and J. Barkley Rosser, after whom it is named.
known for
Wikipage redirect
Abstract rewriting systemAlonzo ChurchChurch-RosserChurch-Rosser theoremConfluence (abstract rewriting)Deductive lambda calculusJ. Barkley RosserLambda calculusList of functional programming topicsList of mathematical logic topicsList of theoremsLogical frameworkNatarajan ShankarReduction strategy (lambda calculus)RewritingSahlqvist formula
Link from a Wikipage to another Wikipage
known for
primaryTopic
Church–Rosser theorem
In lambda calculus, the Church–Rosser theorem states that, when applying reduction rules to terms, the ordering in which the reductions are chosen does not make a difference to the eventual result. More precisely, if there are two distinct reductions or sequences of reductions that can be applied to the same term, then there exists a term that is reachable from both results, by applying (possibly empty) sequences of additional reductions. The theorem was proved in 1936 by Alonzo Church and J. Barkley Rosser, after whom it is named.
has abstract
Das Church-Rosser-Theorem (bew ...... bstrakte Reduktionssysteme zu.
@de
En informatique théorique et e ...... Church et John Barkley Rosser.
@fr
In lambda calculus, the Church ...... of a given normalizable term.
@en
O Teorema de Church-Rosser é u ...... temas de reescrita de termos.)
@pt
Теорема Чёрча — Россера — одна ...... , в честь которых она названа.
@ru
チャーチ・ロッサーの定理(チャーチ・ロッサーのていり、英: ...... 可能な式があることを述べる定理である。詳しくは合流性を参照。
@ja
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,021,906,453
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
comment
Das Church-Rosser-Theorem (bew ...... bstrakte Reduktionssysteme zu.
@de
En informatique théorique et e ...... Church et John Barkley Rosser.
@fr
In lambda calculus, the Church ...... osser, after whom it is named.
@en
O Teorema de Church-Rosser é u ...... temas de reescrita de termos.)
@pt
Теорема Чёрча — Россера — одна ...... , в честь которых она названа.
@ru
チャーチ・ロッサーの定理(チャーチ・ロッサーのていり、英: ...... 可能な式があることを述べる定理である。詳しくは合流性を参照。
@ja
label
Church–Rosser theorem
@en
Propriété de Church-Rosser
@fr
Satz von Church-Rosser
@de
Teorema de Church-Rosser
@pt
Теорема Чёрча — Россера
@ru
チャーチ・ロッサーの定理
@ja
처치-로서 정리
@ko