GetWiki
rewriting
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
rewriting
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{other uses}}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. The objects of focus for this article include rewriting systems (also known as rewrite systems, rewrite enginesJOURNAL, Sculthorpe, Neil, Frisby, Nicolas, Gill, Andy, The Kansas University rewrite engine, Journal of Functional Programming, 24, 4, 2014, 434â€“473, 0956-7968, 10.1017/S0956796814000185,weblink 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 proversHsiang, Jieh, et al. "The term rewriting approach to automated theorem proving." The Journal of Logic Programming 14.1-2 (1992): 71â€“99. and declarative programming languages are based on term rewriting.FrÃ¼hwirth, Thom. "Theory and practice of constraint handling rules." The Journal of Logic Programming 37.1 (1998): 95â€“138.Clavel, Manuel, et al. "Maude: Specification and programming in rewriting logic." Theoretical Computer Science 285.2 (2002): 187â€“243.- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
Intuitive examples
Logic
In logic, the procedure for obtaining the conjunctive normal form (CNF) of a formula can be implemented as a rewriting system.BOOK, Kim Marriott, Peter J. Stuckey, Programming with Constraints: An Introduction,weblink 1998, MIT Press, 978-0-262-13341-8, 436â€“, The rules of an example of such a system would be:
negneg A to A (double negation elimination)
neg(A land B) to neg A lor neg B (De Morgan's laws)
neg(A lor B) to neg A landneg 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),This variant of the previous rule is needed since the commutative law Aâˆ¨B = Bâˆ¨A cannot be turned into a rewrite rule. A rule like Aâˆ¨B â†’ Bâˆ¨A would cause the rewrite system to be nonterminating.
where the symbol (to) indicates that an expression matching the left hand side of the rule can be rewritten to one formed by the right hand side, and the symbols each denote a subexpression. In such a system, each rule is chosen so that the left side is equivalent to the right side, and consequently when the left side matches a subexpression, performing a rewrite of that subexpression from left to right maintains logical consistency and value of the entire expression.Linguistics
In linguistics, rewrite rules, also called phrase structure rules, are used in some systems of generative grammar,BOOK, Robert Freidin, Foundations of Generative Syntax,weblink 1992, MIT Press, 978-0-262-06144-5, as a means of generating the grammatically correct sentences of a language. Such a rule typically takes the form A â†’ X, 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 S â†’ NP VP means that a sentence can consist of a noun phrase followed by a verb phrase; further rules will specify what sub-constituents a noun phrase and a verb phrase can consist of, and so on.Abstract rewriting systems
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, (abbreviated ARS), although more recently authors use abstract rewriting system as well.Bezem et al., p. 7, (The preference for the word "reduction" here instead of "rewriting" constitutes a departure from the uniform use of "rewriting" in the names of systems that are particularizations of ARS. Because the word "reduction" does not appear in the names of more specialized systems, in older texts reduction system is a synonym for ARS).Book and Otto, p. 10An ARS is simply a set A, whose elements are usually called objects, together with a binary relation on A, traditionally denoted by â†’, and called the reduction relation, rewrite relationBezem et al., p. 7 or just reduction. This (entrenched) terminology using "reduction" is a little misleading, because the relation is not necessarily reducing some measure of the objects; this will become more apparent when we discuss string-rewriting systems further in this article.Example 1. Suppose the set of objects is T = {a, b, c} and the binary relation is given by the rules a â†’ b, b â†’ a, a â†’ c, and b â†’ c. 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. This example leads us to define some important notions in the general setting of an ARS. First we need some basic notions and notations.Baader and Nipkow, pp. 8â€“9- stackrel{}{rightarrow} is the transitive closure of rightarrow cup =, where = is the identity relation, i.e. stackrel{}{rightarrow} is the smallest preorder (reflexive and transitive relation) containing rightarrow. It is also called the reflexive transitive closure of rightarrow.
- leftrightarrow is rightarrow cup xrightarrow{-1}, that is the union of the relation â†’ with its converse relation, also known as the symmetric closure of rightarrow.
- stackrel{}{leftrightarrow} is the transitive closure of leftrightarrow cup =, that is stackrel{}{leftrightarrow} is the smallest equivalence relation containing rightarrow. It is also known as the reflexive transitive symmetric closure of rightarrow.
Normal forms, joinability and the word problem
An object x in A is called reducible if there exists some other y in A such that x rightarrow y; otherwise it is called irreducible or a normal form. An object y is called a normal form of x if x stackrel{*}{,rightarrow,} y, and y is irreducible. If x has a unique normal form, then this is usually denoted with x{downarrow}. In example 1 above, c is a normal form, and c = a{downarrow} = b{downarrow}. If every object has at least one normal form, the ARS is called normalizing.A related, but weaker notion than the existence of normal forms is that of two objects being joinable: x and y are said to be joinable if there exists some z with the property that x stackrel{*}{,rightarrow,} z stackrel{*}{,leftarrow,} y. From this definition, it is apparent that one may define the joinability relation as stackrel{*}{,rightarrow} circ stackrel{*}{,leftarrow}, where circ is the composition of relations. Joinability is usually denoted, somewhat confusingly, also with downarrow, but in this notation the down arrow is a binary relation, i.e. we write x downarrow y if x and y are joinable.One of the important problems that may be formulated in an ARS is the word problem: given x and y, are they equivalent under stackrel{*}{,leftrightarrow,}? This is a very general setting for formulating the word problem for the presentation of an algebraic structure. For instance, the word problem for groups is a particular case of an ARS word problem. Central to an "easy" solution for the word problem is the existence of unique normal forms: in this case if two objects have the same normal form, then they are equivalent under stackrel{*}{leftrightarrow}. The word problem for an ARS is undecidable in general.The Churchâ€“Rosser property and confluence
An ARS is said to possess the Churchâ€“Rosser property if x stackrel{*}{,leftrightarrow,} y implies x downarrow y. In words, the Churchâ€“Rosser property means that any two equivalent objects are joinable. Alonzo Church and J. Barkley Rosser proved in 1936 that lambda calculus has this property;Alonzo Church and J. Barkley Rosser. Some properties of conversion. Trans.AMS, 39:472â€“482, 1936 hence the name of the property.Baader and Nipkow, p. 9 (That lambda calculus has this property is also known as the Churchâ€“Rosser theorem.) In an ARS with the Churchâ€“Rosser property the word problem may be reduced to the search for a common successor. In a Churchâ€“Rosser system, an object has at most one normal form; that is the normal form of an object is unique if it exists, but it may well not exist.Several different properties are equivalent to the Churchâ€“Rosser property, but may be simpler to check in some particular setting. In particular, confluence is equivalent to Churchâ€“Rosser. An ARS (A,rightarrow) is said:- confluent if for all w, x, and y in A, x stackrel{}{,leftarrow,} w stackrel{}{,rightarrow,} y implies x downarrow y. Roughly speaking, confluence says that no matter how two paths diverge from a common ancestor (w), the paths are joining at some common successor. This notion may be refined as property of a particular object w, and the system called confluent if all its elements are confluent.
- locally confluent if for all w, x, and y in A, x leftarrow w rightarrow y implies x downarrow y. This property is sometimes called weak confluence.
- If both x and y are normal forms, then {{math|1=x = y}}.
- If y is a normal form, then x stackrel{}{,rightarrow,} y
Termination and convergence
An abstract rewriting system is said to be terminating or noetherian if there is no infinite chain x_0 rightarrow x_1 rightarrow x_2 rightarrow cdots. In a terminating ARS, every object has at least one normal form, thus it is normalizing. The converse is not true. In example 1 for instance, there is an infinite rewriting chain, namely a rightarrow b rightarrow a rightarrow b rightarrow cdots, even though the system is normalizing. A confluent and terminating ARS is called convergent. In a convergent ARS, every object has a unique normal form. Theorem (Newman's Lemma): A terminating ARS is confluent if and only if it is locally confluent.String rewriting systems
A string rewriting system (SRS), also known as semi-Thue system, exploits the free monoid structure of the strings (words) over an alphabet to extend a rewriting relation, R to all strings in the alphabet that contain left- and respectively right-hand sides of some rules as substrings. Formally a semi-Thue systems is a tuple (Sigma, R) where Sigma is a (usually finite) alphabet, and R is a binary relation between some (fixed) strings in the alphabet, called rewrite rules. The one-step rewriting relation relation xrightarrow[R]{} induced by R on Sigma^* is defined as: for any strings s, t in Sigma^* s ,xrightarrow[R]{}, t if and only if there exist x, y, u, v in Sigma^* such that s = xuy, t = xvy, and u R v. Since xrightarrow[R]{} is a relation on Sigma^*, the pair (Sigma^*, xrightarrow[R]{}) fits the definition of an abstract rewriting system. Obviously R is subset of xrightarrow[R]{}. If the relation R is symmetric, then the system is called a Thue system.In a SRS, the reduction relation xrightarrow[R]{*} is compatible with the monoid operation, meaning that x ,xrightarrow[R]{*}, y implies uxv ,xrightarrow[R]{*}, uyv for all strings x, y, u, v in Sigma^*. Similarly, the reflexive transitive symmetric closure of xrightarrow[R]{}, denoted overset{*}{underset R leftrightarrow}, is a congruence, meaning it is an equivalence relation (by definition) and it is also compatible with string concatenation. The relation overset{*}{underset R leftrightarrow} is called the Thue congruence generated by R. In a Thue system, i.e. if R is symmetric, the rewrite relation xrightarrow[R]{*} coincides with the Thue congruence overset{*}{underset R leftrightarrow}.The notion of a semi-Thue system essentially coincides with the presentation of a monoid. Since overset{*}{underset R leftrightarrow} is a congruence, we can define the factor monoid mathcal{M}_R = Sigma^*/overset{*}{underset R leftrightarrow} of the free monoid Sigma^* by the Thue congruence in the usual manner. If a monoid mathcal{M} is isomorphic with mathcal{M}_R, then the semi-Thue system (Sigma, R) is called a monoid presentation of mathcal{M}.We immediately get some very useful connections with other areas of algebra. For example, the alphabet {a, b} with the rules { ab â†’ Îµ, ba â†’ Îµ }, where Îµ is the empty string, is a presentation of the free group on one generator. If instead the rules are just { ab â†’ Îµ }, then we obtain a presentation of the bicyclic monoid. Thus semi-Thue systems constitute a natural framework for solving the word problem for monoids and groups. In fact, every monoid has a presentation of the form (Sigma, R), i.e. it may always be presented by a semi-Thue system, possibly over an infinite alphabet.The word problem for a semi-Thue system is undecidable in general; this result is sometimes known as the Post-Markov theorem.Martin Davis et al. 1994, p. 178Term rewriting systems
{{Expand section|date=October 2009}}(File:Triangle diagram of rewrite rule application svg.svg|thumb|Pic.1: Schematic triangle diagram of application of a rewrite rule l longrightarrow r at position p in a term, with matching substitution sigma)(File:Example term for position, path, depth, match svg.svg|thumb|Pic.2: Rule lhs term x*(y*z) matching in term frac{a*((a+1)*(a+2))}{1*(2*3)})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 {{section link||Logic}} above is a term rewriting system. The terms in this system are composed of binary operators (vee) and (wedge) and the unary operator (neg). Also present in the rules are variables,these each 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.Formal definition
A term rewriting rule is a pair of terms, commonly written as l rightarrow r, 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 l rightarrow r can be applied to a term s if the left term l matches some subterm of s, that is, if s|_p = l sigmahere, s mid_p denotes the subterm of s rooted at position p,while l sigma denotes the result of applying the substitution sigma to the term lfor some position p in s and some substitution sigma. The result term t of this rule application is then obtained as t = s[r sigma]_p;here, s[r sigma]_p denotes the result of replacing the subterm at position p in s by the term r sigmasee picture 1. In this case, s is said to be rewritten in one step, or rewritten directly, to t by the system R, formally denoted as s rightarrow_R t, s ,xrightarrow[R]{}, t, or as s ,xrightarrow{R}, t by some authors. If a term t_1 can be rewritten in several steps into a term t_n, that is, if t_1 ,xrightarrow[R]{}, t_2 ,xrightarrow[R]{}, ldots ,xrightarrow[R]{}, t_n, the term t_1 is said to be rewritten to t_n, formally denoted as t_1 ,xrightarrow[R]{+}, t_n.In other words, the relation xrightarrow[R]{+} is the transitive closure of the relation xrightarrow[R]{};often, also the notation xrightarrow[R]{*} is used to denote the reflexive-transitive closure of xrightarrow[R]{}, that is,s ,xrightarrow[R]{*}, t if s = t or {{nobreak|s ,xrightarrow[R]{+}, t.BOOK, N. Dershowitz, J.-P. Jouannaud, Rewrite Systems, 1990, B, 243â€“320, Elsevier, Jan van Leeuwen, Handbook of Theoretical Computer Science, ; here: Sect. 2.3}}A term rewriting given by a set R of rules can be viewed as an abstract rewriting system as defined above, with terms as its objects and xrightarrow[R]{} as its rewrite relation.For example, x*(y*z) rightarrow (x*y)*z 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 frac{a*((a+1)*(a+2))}{1*(2*3)} with the matching substitution { x mapsto a, ; y mapsto a+1, ; z mapsto a+2 }, see picture 2.since applying that substitution to the rule's left hand side x*(y*z) yields the numerator a*((a+1)*(a+2))Applying that substitution to the rule's right hand side yields the term (a*(a+1))*(a+2), and replacing the numerator by that term yields frac{(a*(a+1))*(a+2)}{1*(2*3)}, 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 frac{a*((a+1)*(a+2))}{1*(2*3)}" in elementary algebra.Alternatively, the rule could have been applied to the denominator of the original term, yielding frac{a*((a+1)*(a+2))}{(1*2)*3}.Termination
Beyond section Termination and convergence, additional subtleties are to be considered for term rewriting systems.Termination even of a system consisting of one rule with a linear left-hand side is undecidable.BOOK, M. Dauchet, Simulation of Turing Machines by a Left-Linear Rewrite Rule, Proc. 3rd RTA, 1989, 355, 109â€“120, Springer LNCS, LNCS, Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finite ground systems.TECHREPORT, Gerard Huet, D.S. Lankford, On the Uniform Halting Problem for Term Rewriting Systems, Mar 1978, 283, 8, IRIA,weblink 16 June 2013, The following term rewrite system is normalizing,i.e. for each term, some normal form exists, e.g. h(c,c) has the normal forms b and g(b), since h(c,c) â†’ f(h(c,c),h(c,c)) â†’ f(h(c,c),f(h(c,c),h(c,c))) â†’ f(h(c,c),g(h(c,c))) â†’ b, and h(c,c) â†’ f(h(c,c),h(c,c)) â†’ g(h(c,c),h(c,c)) â†’ ... â†’ g(b); neither b nor g(b) can be rewritten any further, therefore the system is not confluent but not terminating,i.e., there are infinite derivations, e.g. h(c,c) â†’ f(h(c,c),h(c,c)) â†’ f(f(h(c,c),h(c,c)) ,h(c,c)) â†’ f(f(f(h(c,c),h(c,c)),h(c,c)) ,h(c,c)) â†’ ... and not confluent:BOOK, Bernhard Gramlich, Relating Innermost, Weak, Uniform, and Modular Termination of Term Rewriting Systems, Proc. International Conference on Logic Programming and Automated Reasoning (LPAR), Jun 1993, 624, 285â€“296, Springer, Voronkov, Andrei, LNAI,weblink International Conference on Logic Programming and Automated Reasoning, Here: Example 3.3
f(x,x) rightarrow g(x),
f(x,g(x)) rightarrow b,
h(c,x) rightarrow f(h(x,c),h(x,x)).
The following two examples of terminating term rewrite systems are due to Toyama:JOURNAL, Y. Toyama, Counterexamples to Termination for the Direct Sum of Term Rewriting Systems, Inf. Process. Lett., 1987, 25, 3, 141â€“143,weblink 10.1016/0020-0190(87)90122-0,
f(0,1,x) rightarrow f(x,x,x)
and
g(x,y) rightarrow x,
g(x,y) rightarrow y.
Their union is a non-terminating system, since f(g(0,1),g(0,1),g(0,1)) rightarrow f(0,g(0,1),g(0,1)) rightarrow f(0,1,g(0,1)) rightarrow f(g(0,1),g(0,1),g(0,1)) rightarrow ldots. This result disproves a conjecture of Dershowitz,BOOK, N. Dershowitz, Termination, Proc. RTA, 1985, 220, 180â€“224, Springer, Jean-Pierre Jouannaud, LNCS,weblink ; here: p.210 who claimed that the union of two terminating term rewrite systems R_1 and R_2 is again terminating if all left-hand sides of R_1 and right-hand sides of R_2 are linear, and there are no "overlaps" between left-hand sides of R_1 and right-hand sides of R_2. All these properties are satisfied by Toyama's examples.See Rewrite order and Path ordering (term rewriting) for ordering relations used in termination proofs for term rewriting systems.Graph rewriting systems
A generalization of term rewrite systems are graph rewrite systems, operating on graphs instead of (ground-) terms / their corresponding tree representation.Trace rewriting systems
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.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.{{citation needed|date=December 2014}}See also
- Critical pair (logic)
- Knuthâ€“Bendix completion algorithm
- L-systems specify rewriting that is done in parallel.
- Referential transparency in computer science
- Regulated rewriting
- Rho calculus
Notes
{{reflist|group=note}}References
{{reflist|3}}Further reading
- BOOK, Franz, Baader, Franz Baader, Tobias, Nipkow, Tobias Nipkow, Term rewriting and all that, Cambridge University Press, 978-0-521-77920-3, 1999, 316 pages. A textbook suitable for undergraduates.
- Marc Bezem, Jan Willem Klop, Roel de Vrijer ("Terese"), Term Rewriting Systems ("TeReSe"), Cambridge University Press, 2003, {{isbn|0-521-39115-6}}. This is the most recent comprehensive monograph. It uses however a fair deal of non-yet-standard notations and definitions. For instance, the Churchâ€“Rosser property is defined to be identical with confluence.
- Nachum Dershowitz and Jean-Pierre Jouannaud "Rewrite Systems", Chapter 6 in Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics., Elsevier and MIT Press, 1990, {{isbn|0-444-88074-7}}, pp. 243–320. The preprint of this chapter is freely available from the authors, but it is missing the figures.
- Nachum Dershowitz and David Plaisted. "Rewriting", Chapter 9 in John Alan Robinson and Andrei Voronkov (Eds.), Handbook of Automated Reasoning, Volume 1.
- GÃ©rard Huet et Derek Oppen, Equations and Rewrite Rules, A Survey (1980) Stanford Verification Group, Report NÂ° 15 Computer Science Department Report NÂ° STAN-CS-80-785
- Jan Willem Klop. "Term Rewriting Systems", Chapter 1 in Samson Abramsky, Dov M. Gabbay and Tom Maibaum (Eds.), Handbook of Logic in Computer Science, Volume 2: Background: Computational Structures.
- David Plaisted. "Equational reasoning and term rewriting systems", in Dov M. Gabbay, C. J. Hogger and John Alan Robinson (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 1.
- JÃ¼rgen Avenhaus and Klaus Madlener. "Term rewriting and equational reasoning". In Ranan B. Banerji (Ed.), Formal Techniques in Artificial Intelligence: A Sourcebook, Elsevier (1990).
- String rewriting
- Ronald V. Book and Friedrich Otto, String-Rewriting Systems, Springer (1993).
- Benjamin Benninghofen, Susanne Kemmerich and Michael M. Richter, Systems of Reductions. LNCS 277, Springer-Verlag (1987).
- Other
- Martin Davis, Ron Sigal, Elaine J. Weyuker, (1994) Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science â€“ 2nd edition, Academic Press, {{isbn|0-12-206382-1}}.
External links
{{Wiktionary}}- The Rewriting Home Page
- IFIP Working Group 1.6
- Researchers in rewriting by Aart Middeldorp, University of Innsbruck
- Termination Portal
- content above as imported from Wikipedia
- "rewriting" does not exist on GetWiki (yet)
- time: 9:30am EDT - Wed, May 22 2019
- "rewriting" does not exist on GetWiki (yet)
- time: 9:30am EDT - Wed, May 22 2019
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
Culture
© 2019 M.R.M. PARROTT | ALL RIGHTS RESERVED