Normal form (abstract rewriting)

In abstract rewriting, a normal form is an element of the system which cannot be rewritten any further. Stated formally, for some reduction relation ⋅ → ⋅ over X a term t in X is a normal form if there does not exist a term t′ in X such that t → t′.

Consider the basic term rewriting system with reduction rule ρ : g(x, y) → x. The term g(g(4, 2), g(3, 1)) has the following reduction sequence, according to the usual outermost strategy, that is, if the reduction rule is applied to each outermost occurrence of g:

$g(g(4,2), g(3,1)) \rightarrow_\rho g(4,2) \rightarrow_\rho 4.$

There is no rule that permits us to rewrite 4, so 4 is a normal form for this term rewriting system.

Related concepts refer to the possibility of rewriting an element into normal form. Weak normalization means that some element can be rewritten into a normal form. Strong normalization means that any reduction sequence starting from some element terminates. We say that the system is weakly normalizing (or strongly normalizing) if all elements are weakly normalizing (resp. strongly normalizing).

Newman's lemma states that if an abstract reduction system A is strongly normalizing and is weakly confluent, then A is in fact confluent. The result enables us to further generalize the critical pair lemma.

References

• Baader, Franz; Nipkow, Tobias (1998). Term Rewriting and All That. Cambridge University Press. 

P ≟ NP

This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Computability theory Formal languages Rewriting systems Theoretical computer science stubs Wikimedia Foundation. 2010. Игры ⚽ Нужен реферат? Normal flex acres Theoretical gravity Look at other dictionaries: Normal form (term rewriting) — In considering rewriting systems, a normal form is an element of the system which cannot be rewritten any further. Consider the basic term rewriting system with reduction rule ρ : g ( x , y ) → x . The term g ( g (4, 2), g (3, 1)) has the… …   Wikipedia Normal form — may refer to: Normal form (abstract rewriting) Normal form (databases) Normal form (game theory) Normal form (mathematics) In formal language theory: Beta normal form Chomsky normal form Greibach normal form Kuroda normal form Normal form… …   Wikipedia Abstract rewriting system — In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviation ARS) is a formalism that captures the quintessential notion and properties of… …   Wikipedia Abstract rewriting machine — The Abstract Rewriting Machine (ARM) is a virtual machine which implements term rewriting for minimal term rewriting systems. Minimal term rewriting systems are left linear term rewriting systems in which each rule takes on one of six forms:… …   Wikipedia Abstract Rewriting Machine — The Abstract Rewriting Machine (ARM) is a virtual machinewhich implements term rewriting for minimal term rewriting systems. Minimal term rewriting systems are left linear termrewriting systems in which each rule takes on one of six… …   Wikipedia Normalization property (abstract rewriting) — In mathematical logic and theoretical computer science, a rewrite system has the strong normalization property (in short: the normalization property) if every term is strongly normalizing; that is, if every sequence of rewrites eventually… …   Wikipedia Rewriting — In mathematics, computer science and logic, rewriting covers a wide range of potentially non deterministic methods of replacing subterms of a formula with other terms. What is considered are rewrite systems (also rewriting systems, or term… …   Wikipedia Canonical form — Generally, in mathematics, a canonical form (often called normal form or standard form) of an object is a standard way of presenting that object. Canonical form can also mean a differential form that is defined in a natural (canonical) way; see… …   Wikipedia Knuth-Bendix completion algorithm — The Knuth Bendix completion algorithm is an algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it has effectively solved the word problem for the specified algebra. An… …   Wikipedia Divergence (computer science) — In computer science, a computation is said to diverge if it does not terminate or terminates in an (unobservable) exceptional state. Otherwise it is said to converge. In domains where computations are expected to be infinite, such as process… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”