church-rosser theorem

Computing Dictionary

Church-Rosser Theorem definition

theory
A property of a reduction system that states that if an expression can be reduced by zero or more reduction steps to either expression M or expression N then there exists some other expression to which both M and N can be reduced. This implies that there is a unique normal form for any expression since M and N cannot be different normal forms because the theorem says they can be reduced to some other expression and normal forms are irreducible by definition. It does not imply that a normal form is reachable, only that if reduction terminates it will reach a unique normal form.
(1995-01-25)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: church-register
Next Definition: church-school
More from Thesaurus.com
Synonyms and Antonyms for church-rosser theorem
More from Reference.com
Search for articles containing church-rosser theorem
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature