|
|
|
|
normalizing reduction
|
(Definition)
|
|
Definition 1 Let  be a set and
 a reduction ( binary relation) on  . An element  is said to be in normal form with respect to
 if
 for all  , i.e., if there is no  such that
 . Equivalently,  is in normal form with respect to iff
 . To be irreducible is a common synonym for `to be in normal form'.
Denote by
the reflexive transitive closure of
. An element is said to be a normal form of if is in normal form and
.
A reduction on is said to be normalizing if every element has a normal form.
Examples.
- Let
be any set. Then no elements in are in normal form with respect to any reduction that is either reflexive. If is a symmetric relation, then is in normal form with respect to iff is not in the domain (or range) of .
- Let
and
. Then and are both in normal form. In addition, they are both normal forms of , while is a normal form only for . However, is not normalizing because neither nor have normal forms.
- Let
be the set of all positive integers greater than . Define the reduction on as follows: if there is an element such that . Then it is clear that every prime number is in normal form. Furthermore, every element in has normal forms, where is the number of prime divisors of . Clearly, for every . As a result, is normalizing.
|
"normalizing reduction" is owned by CWoo.
|
|
(view preamble)
Cross-references: prime divisors, prime number, clear, integers, positive, addition, range, domain, symmetric relation, Reflexive, reflexive transitive closure, iff, binary relation, reduction
There are 22 references to this entry.
This is version 7 of normalizing reduction, born on 2008-03-31, modified 2008-04-02.
Object id is 10460, canonical name is NormalizingReduction.
Accessed 408 times total.
Classification:
| AMS MSC: | 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|