Finitely terminating rewriting system: Difference between revisions
No edit summary |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{rewriting system property}} | {{rewriting system property}} | ||
{{semibasic nongt def}} | |||
==Definition== | ==Definition== | ||
| Line 5: | Line 7: | ||
===Symbol-free definition=== | ===Symbol-free definition=== | ||
A [[rewriting system]] is said to be '''finitely terminating''' if every chain of reductions in the rewriting system terminates in finitely many steps. | A [[rewriting system]] is said to be '''finitely terminating''' or '''Noetherian''' if every chain of reductions in the rewriting system terminates in finitely many steps. | ||
Note that though this property is originally defined for a rewriting system of a monoid, it also makes sense for a [[rewriting system for a group]]. | Note that though this property is originally defined for a rewriting system of a monoid, it also makes sense for a [[rewriting system for a group]]. | ||
| Line 16: | Line 18: | ||
* [[Monadic rewriting system]] | * [[Monadic rewriting system]] | ||
* [[Length-reducing rewriting system]] | * [[Length-reducing rewriting system]] | ||
* [[Linear-time terminating rewriting system]] | * [[Linear-time terminating rewriting system]] | ||
Latest revision as of 22:17, 31 January 2012
Template:Rewriting system property
This article is about a standard (though not very rudimentary) definition in an area related to, but not strictly part of, group theory
Definition
Symbol-free definition
A rewriting system is said to be finitely terminating or Noetherian if every chain of reductions in the rewriting system terminates in finitely many steps.
Note that though this property is originally defined for a rewriting system of a monoid, it also makes sense for a rewriting system for a group.