Reduction Systems - Term Rewriting Systems

Term Rewriting Systems

This section requires expansion.

A term rewriting system (TRS) is a rewriting system where the objects are terms, or expressions with nested sub-expressions. For example, the system shown under Logic 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 are part of the rules themselves rather than the term; these each represent any possible term (though a single variable always represents the same term throughout a single rule).

The term structure in such a system is usually presented using a grammar. In contrast to string rewriting systems, whose objects are flat sequences of symbols, the objects of a term rewriting system form a term algebra, which can be visualized as a tree of symbols, the structure of the tree fixed by the signature used to define the terms.

The system given under Logic above is an example of a term rewriting system.

Read more about this topic:  Reduction Systems

Famous quotes containing the words term and/or systems:

    Why did you give no hint that night
    That quickly after the morrow’s dawn,
    And calmly, as if indifferent quite,
    You would close your term here, up and be gone
    Thomas Hardy (1840–1928)

    Not out of those, on whom systems of education have exhausted their culture, comes the helpful giant to destroy the old or to build the new, but out of unhandselled savage nature, out of terrible Druids and Berserkirs, come at last Alfred and Shakespeare.
    Ralph Waldo Emerson (1803–1882)