Формулаларды қайта жазу жүйелері

Replacing subterm in a formula with another term

In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduction systems). In their most basic form, they consist of a set of objects, plus relations on how to transform those objects. 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. When combined with an appropriate algorithm, however, rewrite systems can be viewed as computer programs, and several theorem provers and declarative programming languages are based on term rewriting.

In linguistics, phrase structure rules, also called rewrite rules, are used in some systems of generative grammar, as a means of generating the grammatically correct sentences of a language. Such a rule typically takes the form , where A is a syntactic category label, such as noun phrase or sentence, and X is a sequence of such labels or morphemes, expressing the fact that A can be replaced by X in generating the constituent structure of a sentence. For example, the rule means that a sentence can consist of a noun phrase (NP) followed by a verb phrase (VP); further rules will specify what sub constituents a noun phrase and a verb phrase can consist of, and so on.

From the above examples, it is clear that we can think of rewriting systems in an abstract manner. We need to specify a set of objects and the rules that can be applied to transform them. The most general (unidimensional) setting of this notion is called an abstract reduction system or abstract rewriting system (abbreviated ARS). An ARS is simply a set A of objects, together with a binary relation → on A called the reduction relation, rewrite relation or just reduction.

A term rewriting system (TRS) is a rewriting system whose objects are terms, which are expressions with nested sub expressions. For example, the system shown under above is a term rewriting system. The terms in this system are composed of binary operators and and the unary operator Also present in the rules are variables, which represent any possible term (though a single variable always represents the same term throughout a single rule). In contrast to string rewriting systems, whose objects are sequences of symbols, the objects of a term rewriting system form a term algebra. A term can be visualized as a tree of symbols, the set of admitted symbols being fixed by a given signature. As a formalism, term rewriting systems have the full power of Turing machines, that is, every computable function can be defined by a term rewriting system.

A rewrite rule is a pair of terms, commonly written as , to indicate that the left hand side l can be replaced by the right hand side r. A term rewriting system is a set R of such rules. A rule can be applied to a term s if the left term l matches some subterm of s, that is, if there is some substitution such that the subterm of rooted at some position p is the result of applying the substitution to the term l. The subterm matching the left hand side of the rule is called a redex or reducible expression. The result term t of this rule application is then the result of replacing the subterm at position p in s by the term with the substitution applied, see picture 1. In this case, is said to be rewritten in one step, or rewritten directly, to by the system , formally denoted as , , or as by some authors. If a term can be rewritten in several steps into a term , that is, if , the term is said to be rewritten to , formally denoted as In other words, the relation is the transitive closure of the relation ; often, also the notation is used to denote the reflexive transitive closure of , that is, if or A term rewriting given by a set of rules can be viewed as an abstract rewriting system as defined above, with terms as its objects and as its rewrite relation. For example, is a rewrite rule, commonly used to establish a normal form with respect to the associativity of That rule can be applied at the numerator in the term with the matching substitution , see picture 2. Applying that substitution to the rule's right hand side yields the term , and replacing the numerator by that term yields , which is the result term of applying the rewrite rule. Altogether, applying the rewrite rule has achieved what is called "applying the associativity law for to " in elementary algebra. Alternately, the rule could have been applied to the denominator of the original term, yielding .

Higher order rewriting systems are a generalization of first order term rewriting systems to lambda terms, allowing higher order functions and bound variables. Various results about first order TRSs can be reformulated for HRSs as well.

Graph rewrite systems are another generalization of term rewrite systems, operating on graphs instead of (ground ) terms / their corresponding tree representation.

Trace theory provides a means for discussing multiprocessing in more formal terms, such as via the trace monoid and the history monoid. Rewriting can be performed in trace systems as well.