Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Church–Rosser_theorem> ?p ?o }
Showing triples 1 to 50 of
50
with 100 triples per page.
- Church–Rosser_theorem abstract "In mathematics and theoretical computer science, the Church–Rosser theorem states that, when applying reduction rules to terms in the lambda calculus, 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.The theorem is symbolized by the diagram at right: if term a can be reduced to both b and c, then there must be a further term d (possibly equal to either b or c) to which both b and c can be reduced.Viewing the lambda calculus as an abstract rewriting system, the Church–Rosser theorem states that the reduction rules of the lambda calculus are confluent. As a consequence of the theorem, a term in the lambda calculus has at most one normal form, justifying reference to "the normal form" of a given term. The Church–Rosser theorem also holds for many variants of the lambda calculus, such as the simply-typed lambda calculus, many calculi with advanced type systems, and Gordon Plotkin's beta-value calculus. Plotkin also used a Church–Rosser theorem to prove that the evaluation of functional programs (for both lazy evaluation and eager evaluation) is a function from programs to values (a subset of the lambda terms).In older research papers, a rewriting system is said to be Church–Rosser, or to have the Church–Rosser property, when it is confluent.".
- Church–Rosser_theorem thumbnail Confluence.svg?width=300.
- Church–Rosser_theorem wikiPageID "150035".
- Church–Rosser_theorem wikiPageLength "2436".
- Church–Rosser_theorem wikiPageOutDegree "23".
- Church–Rosser_theorem wikiPageRevisionID "574581424".
- Church–Rosser_theorem wikiPageWikiLink Abstract_rewriting_system.
- Church–Rosser_theorem wikiPageWikiLink Alonzo_Church.
- Church–Rosser_theorem wikiPageWikiLink Beta_normal_form.
- Church–Rosser_theorem wikiPageWikiLink Category:Lambda_calculus.
- Church–Rosser_theorem wikiPageWikiLink Category:Rewriting_systems.
- Church–Rosser_theorem wikiPageWikiLink Category:Theorems_in_the_foundations_of_mathematics.
- Church–Rosser_theorem wikiPageWikiLink Confluence_(abstract_rewriting).
- Church–Rosser_theorem wikiPageWikiLink Eager_evaluation.
- Church–Rosser_theorem wikiPageWikiLink Gordon_Plotkin.
- Church–Rosser_theorem wikiPageWikiLink J._Barkley_Rosser.
- Church–Rosser_theorem wikiPageWikiLink Lambda_calculus.
- Church–Rosser_theorem wikiPageWikiLink Lazy_evaluation.
- Church–Rosser_theorem wikiPageWikiLink Mathematics.
- Church–Rosser_theorem wikiPageWikiLink Simply_typed_lambda_calculus.
- Church–Rosser_theorem wikiPageWikiLink Subset.
- Church–Rosser_theorem wikiPageWikiLink Term_(logic).
- Church–Rosser_theorem wikiPageWikiLink Theoretical_computer_science.
- Church–Rosser_theorem wikiPageWikiLink Transactions_of_the_American_Mathematical_Society.
- Church–Rosser_theorem wikiPageWikiLink Type_system.
- Church–Rosser_theorem wikiPageWikiLink File:Confluence.svg.
- Church–Rosser_theorem wikiPageWikiLinkText "Church–Rosser theorem".
- Church–Rosser_theorem wikiPageWikiLinkText "Church-Rosser property".
- Church–Rosser_theorem wikiPageWikiLinkText "Church–Rosser theorem".
- Church–Rosser_theorem wikiPageWikiLinkText "Church–Rosser".
- Church–Rosser_theorem hasPhotoCollection Church–Rosser_theorem.
- Church–Rosser_theorem wikiPageUsesTemplate Template:Citation.
- Church–Rosser_theorem wikiPageUsesTemplate Template:Comp-sci-stub.
- Church–Rosser_theorem subject Category:Lambda_calculus.
- Church–Rosser_theorem subject Category:Rewriting_systems.
- Church–Rosser_theorem subject Category:Theorems_in_the_foundations_of_mathematics.
- Church–Rosser_theorem comment "In mathematics and theoretical computer science, the Church–Rosser theorem states that, when applying reduction rules to terms in the lambda calculus, 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.".
- Church–Rosser_theorem label "Church–Rosser theorem".
- Church–Rosser_theorem sameAs Satz_von_Church-Rosser.
- Church–Rosser_theorem sameAs Propriété_de_Church-Rosser.
- Church–Rosser_theorem sameAs Church-Rosserov_teorem.
- Church–Rosser_theorem sameAs チャーチ・ロッサーの定理.
- Church–Rosser_theorem sameAs 처치-로서_정리.
- Church–Rosser_theorem sameAs Teorema_de_Church-Rosser.
- Church–Rosser_theorem sameAs m.0139k0.
- Church–Rosser_theorem sameAs Q1308502.
- Church–Rosser_theorem sameAs Q1308502.
- Church–Rosser_theorem wasDerivedFrom Church–Rosser_theorem?oldid=574581424.
- Church–Rosser_theorem depiction Confluence.svg.
- Church–Rosser_theorem isPrimaryTopicOf Church–Rosser_theorem.