Citizendia
Your Ad Here

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. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Logic is the study of the principles of valid demonstration and Inference. Deterministic automaton are a concept of Automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for What is considered are rewrite systems (also rewriting systems, or term rewriting systems, though the latter term may imply a more specific system) which, in their most basic form, consist of a set of terms, plus relations on how to transform these terms.

Term rewriting can be non-deterministic. One rule to rewrite a term could be applied in many different ways to that term, or more than one rule could be applicable. Rewriting systems then do not provide an algorithm for changing one term to another, but a set of possible rule applications. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation When combined with an appropriate algorithm, however, rewrite systems can be viewed as computer programs, and several declarative programming languages are based on term rewriting. Computer programs (also software programs, or just programs) are instructions for a Computer.

Contents

Examples

Arithmetic

Consider the rules of regular arithmetic. We can think of these rules as forming a rewriting system, with rules including:

\mathrm{plus}(a, b) \rightarrow a + b
\mathrm{times}(a, b) \rightarrow a \times b

where a+b denotes the sum of a and b, and a × b denotes the product of a and b.

Suppose we are given the expression

times(plus(11,9),plus(2,4))

We can rewrite this expression in two ways, simplifying either the first bracket or the second. Simplifying the first bracket, we have

times(20,plus(2,4)) = times(20,6) = 120

Simplifying the second gives

times(plus(11,9),6) = times(20,6) = 120.

Basic algebra

Rewrite systems provide a convenient method of automating theorem proving. Automated theorem proving ( ATP) or automated deduction, currently the most well-developed subfield of Automated reasoning (AR is the If we begin with a set of equational hypotheses, then these may be used to formulate a set of rewrite rules. An example from school algebra goes under the heading collect like terms in an equation. Algebra is a branch of Mathematics concerning the study of structure, relation, and Quantity. There will usually be several ways to proceed, in collecting up and simplifying an equation

P(x) = Q(x)

in which P and Q are polynomials. In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations After some application of the conventional rules of algebra we may end with an equation

R(x) = 0.

This is something like a normal form, though we may well have different signs (at least) for R found by different routes. In considering Rewriting systems a normal form is an element of the system which cannot be rewritten any further If we insist that R is monic there is actually a normal form (as is usually tacitly assumed) in which R(x) is written in terms of decreasing powers of x. In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations

Logic

In logic, the procedure for determining the conjunctive normal form (CNF) of a formula can be conveniently written as a rewriting system. Logic is the study of the principles of valid demonstration and Inference. In Boolean logic, a Formula is in conjunctive normal form (CNF or cnf if it is a conjunction of clauses, where a clause is a disjunction The rules of such a system would be:

\neg\neg A \to A (double negative elimination)
\neg(A \land B) \to \neg A \lor \neg B (De Morgan's laws)
\neg(A \lor B) \to \neg A \land\neg B
(A \land B) \lor C \to (A \lor C) \land (B \lor C) (Distributivity)
A \lor (B \land C) \to (A \lor B) \land (A \lor C),

where the arrow (\to) indicates that the left side of the rule can be rewritten to the right side (so it does not denote logical implication). In Propositional logic, the inference rules double negative elimination (also called double negation elimination, double negative introduction, double In Logic, De Morgan's laws or De Morgan's theorem are rules in Formal logic relating pairs of dual Logical operators in a systematic manner expressed In Mathematics, and in particular in Abstract algebra, distributivity is a property of Binary operations that generalises the distributive law The material conditional, also known as the material implication or truth functional conditional, expresses a property of certain Conditionals in Logic

Abstract rewriting systems

We can think of rewriting systems in an abstract manner also. We need to specify our set of terms and the rules that can be applied to transform them.

Suppose the set of terms T = {a, b, c} and the rules are a → b, b → a, a → c, and b → c hold. From these rules, observe that these rules can be applied to both a and b in any fashion to get the term c. Such a property is clearly an important one. Note also, that c is, in a sense, a "simplest" term in the system, since nothing can be applied to c to transform it any further.

Philosophy

Rewriting systems can be seen as programs that infer end-effects from a list of cause-effect relationships. In this way, rewriting systems can be considered to be automated Causality provers. Causality (but not causation) denotes a necessary relationship between one event (called cause and another event (called effect) which is the direct consequence

Properties of rewriting systems

Observe that in both of the above rewriting systems, it is possible to get terms rewritten to a "simplest" term, where this term cannot be modified any further from the rules in the rewriting system. Terms which cannot be written any further are called normal forms. In considering Rewriting systems a normal form is an element of the system which cannot be rewritten any further The potential existence or uniqueness of normal forms can be used to classify and describe certain rewriting systems. There are rewriting systems which do not have normal forms: a very simple one is the rewriting system on two terms a and b with a → b, b → a.

The property exhibited above where terms can be rewritten regardless of the choice of rewriting rule to obtain the same normal form is known as confluence. Confluence is a property of term rewriting systems, describing that terms in this system can be rewritten in more than one way to yield the same result The property of confluence is linked with the property of having unique normal forms.

See also

References

Dictionary

rewriting

-noun

  1. (logic, computer science) a wide range of potentially non-deterministic methods of replacing subterms of a formula with other terms

-verb

  1. Present participle of rewrite.
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic