mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
,
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, and
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
, rewriting covers a wide range of methods of replacing subterms of a
formula
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwee ...
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
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
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 program
A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components.
A computer program ...
declarative programming language
In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.
Many languages that ap ...
s are based on term rewriting.
Example cases
Logic
In
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
, the procedure for obtaining the
conjunctive normal form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a can ...
(CNF) of a formula can be implemented as a rewriting system. The rules of an example of such a system would be:
: (
double negation elimination
In propositional logic, double negation is the theorem that states that "If a statement is true, then it is not the case that the statement is not true." This is expressed by saying that a proposition ''A'' is logically equivalent to ''not (not ...
)
: (
De Morgan's laws
In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathem ...
)
:
: (
distributivity
In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality
x \cdot (y + z) = x \cdot y + x \cdot z
is always true in elementary algebra.
For example, in elementary arithmetic, ...
)
: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 () 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
Equivalence or Equivalent may refer to:
Arts and entertainment
*Album-equivalent unit, a measurement unit in the music industry
* Equivalence class (music)
*'' Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre
*''Equiva ...
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.
Arithmetic
Term rewriting systems can be employed to compute arithmetic operations on
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s.
To this end, each such number has to be encoded as a
term
Term may refer to:
* Terminology, or term, a noun or compound word used in a specific context, in particular:
**Technical term, part of the specialized vocabulary of a particular field, specifically:
***Scientific terminology, terms used by scient ...
.
The simplest encoding is the one used in the
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
, based on the constant 0 (zero) and the
successor function
In mathematics, the successor function or successor operation sends a natural number to the next one. The successor function is denoted by ''S'', so ''S''(''n'') = ''n'' +1. For example, ''S''(1) = 2 and ''S''(2) = 3. The successor functio ...
''S''. For example, the numbers 0, 1, 2, and 3 are represented by the terms 0, S(0), S(S(0)), and S(S(S(0))), respectively.
The following term rewriting system can then be used to compute sum and product of given natural numbers.
:
For example, the computation of 2+2 to result in 4 can be duplicated by term rewriting as follows:
:
where the rule numbers are given above the ''rewrites-to'' arrow.
As another example, the computation of 2⋅2 looks like:
:
where the last step comprises the previous example computation.
Linguistics
In
linguistics
Linguistics is the scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure. Linguis ...
,
phrase structure rule
Phrase structure rules are a type of rewrite rule used to describe a given language's syntax and are closely associated with the early stages of transformational grammar, proposed by Noam Chomsky in 1957. They are used to break down a natural lang ...
s, also called rewrite rules, are used in some systems of
generative grammar
Generative grammar, or generativism , is a linguistic theory that regards linguistics as the study of a hypothesised innate grammatical structure. It is a biological or biologistic modification of earlier structuralist theories of linguistic ...
, 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 A syntactic category is a syntactic unit that theories of syntax assume. Word classes, largely corresponding to traditional parts of speech (e.g. noun, verb, preposition, etc.), are syntactic categories. In phrase structure grammars, the ''phrasal c ...
label, such as
noun phrase
In linguistics, a noun phrase, or nominal (phrase), is a phrase that has a noun or pronoun as its head or performs the same grammatical function as a noun. Noun phrases are very common cross-linguistically, and they may be the most frequently oc ...
or sentence, and X is a sequence of such labels or
morpheme
A morpheme is the smallest meaningful Constituent (linguistics), constituent of a linguistic expression. The field of linguistics, linguistic study dedicated to morphemes is called morphology (linguistics), morphology.
In English, morphemes are ...
s, 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
In linguistics, a verb phrase (VP) is a syntactic unit composed of a verb and its arguments except the subject of an independent clause or coordinate clause. Thus, in the sentence ''A fat man quickly put the money into the box'', the words ''quic ...
(VP); 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''Book and Otto, p. 10 or ''abstract rewriting system'' (abbreviated ''ARS''). An ARS is simply a set ''A'' of objects, together with a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
→ on ''A'' called the ''reduction relation'', ''rewrite relation'' or just ''reduction''.
Many notions and notations can be defined in the general setting of an ARS. is the
reflexive transitive closure
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but ...
of . is the
symmetric closure In mathematics, the symmetric closure of a binary relation R on a set X is the smallest symmetric relation on X that contains R.
For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the ...
of . is the
reflexive transitive symmetric closure
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but n ...
of . The word problem for an ARS is determining, given ''x'' and ''y'', whether . An object ''x'' in ''A'' is called ''reducible'' if there exists some other ''y'' in ''A'' such that ; otherwise it is called ''irreducible'' or a normal form. An object ''y'' is called a "normal form of ''x''" if , and ''y'' is irreducible. If the normal form of ''x'' is unique, then this is usually denoted with . If every object has at least one normal form, the ARS is called ''normalizing''. or ''x'' and ''y'' are said to be ''joinable'' if there exists some ''z'' with the property that . An ARS is said to possess the Church–Rosser property if implies . An ARS is
confluent
In geography, a confluence (also: ''conflux'') occurs where two or more flowing bodies of water join to form a single channel. A confluence can occur in several configurations: at the point where a tributary joins a larger river (main stem); o ...
if for all ''w'', ''x'', and ''y'' in ''A'', implies . An ARS is ''locally confluent'' if and only if for all ''w'', ''x'', and ''y'' in ''A'', implies . An ARS is said to be ''terminating'' or ''noetherian'' if there is no infinite chain . A confluent and terminating ARS is called ''convergent'' or ''canonical''.
Important theorems for abstract rewriting systems are that an ARS is
confluent
In geography, a confluence (also: ''conflux'') occurs where two or more flowing bodies of water join to form a single channel. A confluence can occur in several configurations: at the point where a tributary joins a larger river (main stem); o ...
iff
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicon ...
it has the Church-Rosser property,
Newman's lemma In mathematics, in the theory of rewriting systems, Newman's lemma, also commonly called the diamond lemma, states that a terminating (or strongly normalizing) abstract rewriting system (ARS), that is, one in which there are no infinite reduction ...
which states that a terminating ARS is confluent if and only if it is locally confluent, and that the word problem for an ARS is undecidable in general.
String rewriting systems
A ''string rewriting system'' (SRS), also known as ''semi-Thue system'', exploits the
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...
structure of the
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
(words) over an
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
to extend a rewriting relation, , to ''all'' strings in the alphabet that contain left- and respectively right-hand sides of some rules as
substring
In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequence ...
s. Formally a semi-Thue system is a
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
where is a (usually finite) alphabet, and is a binary relation between some (fixed) strings in the alphabet, called the set of ''rewrite rules''. The ''one-step rewriting relation'' induced by on is defined as: if are any strings, then if there exist such that , , and . Since is a relation on , the pair fits the definition of an abstract rewriting system. Obviously is a subset of . If the relation is
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
, then the system is called a ''Thue system''.
In a SRS, the reduction relation is compatible with the monoid operation, meaning that implies for all strings . Similarly, the reflexive transitive symmetric closure of , denoted , is a congruence, meaning it is an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
(by definition) and it is also compatible with string concatenation. The relation is called the ''Thue congruence'' generated by . In a Thue system, i.e. if is symmetric, the rewrite relation coincides with the Thue congruence .
The notion of a semi-Thue system essentially coincides with the
presentation of a monoid
In algebra, a presentation of a monoid (or a presentation of a semigroup) is a description of a monoid (or a semigroup) in terms of a set of generators and a set of relations on the free monoid (or the free semigroup ) generated by . The monoid ...
. Since is a congruence, we can define the
factor monoid
In mathematics, a semigroup is an algebraic structure consisting of a Set (mathematics), set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplication, multiplicatively ...
of the free monoid by the Thue congruence. If a monoid is
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
with , then the semi-Thue system is called a
monoid presentation
In algebra, a presentation of a monoid (or a presentation of a semigroup) is a description of a monoid (or a semigroup) in terms of a set of generators and a set of relations on the free monoid (or the free semigroup ) generated by . The monoid ...
of .
We immediately get some very useful connections with other areas of algebra. For example, the alphabet with the rules , where is the
empty string
In formal language theory, the empty string, or empty word, is the unique string of length zero.
Formal theory
Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...
, is a presentation of the
free group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
on one generator. If instead the rules are just , then we obtain a presentation of the
bicyclic monoid In mathematics, the bicyclic semigroup is an algebraic object important for the structure theory of semigroups. Although it is in fact a monoid, it is usually referred to as simply a semigroup. It is perhaps most easily understood as the syntactic m ...
. 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 , 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''.
Term rewriting systems
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
In universal algebra and mathematical logic, a term algebra is a freely generated algebraic structure over a given signature. For example, in a signature consisting of a single binary operation, the term algebra over a set ''X'' of variables is exa ...
. A term can be visualized as a tree of symbols, the set of admitted symbols being fixed by a given
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
.
Formal definition
A ''rewrite rule'' is a pair of terms, commonly written as , to indicate that the left-hand side can be replaced by the right-hand side . A ''term rewriting system'' is a set of such rules. A rule can be ''applied'' to a term if the left term
matches
A match is a tool for starting a fire. Typically, matches are made of small wooden sticks or stiff paper. One end is coated with a material that can be ignited by friction generated by striking the match against a suitable surface. Wooden matc ...
some
subterm
In mathematical logic, a term denotes a mathematical object while a formula denotes a mathematical fact. In particular, terms appear as components of a formula. This is analogous to natural language, where a noun phrase refers to an object and a wh ...
of , that is, if there is some
substitution
Substitution may refer to:
Arts and media
*Chord substitution, in music, swapping one chord for a related one within a chord progression
* Substitution (poetry), a variation in poetic scansion
* "Substitution" (song), a 2009 song by Silversun Pi ...
such that the subterm of rooted at some
position
Position often refers to:
* Position (geometry), the spatial location (rather than orientation) of an entity
* Position, a job or occupation
Position may also refer to:
Games and recreation
* Position (poker), location relative to the dealer
* ...
is the result of applying the substitution to the term . The subterm matching the left hand side of the rule is called a redex or reducible expression. The result term of this rule application is then the result of replacing the subterm at position in 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
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite s ...
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.since applying that substitution to the rule's left hand side yields the numerator 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 .
Termination
Termination issues of rewrite systems in general are handled in '' Abstract rewriting system#Termination and convergence''. For term rewriting systems in particular, the following additional subtleties are to be considered.
Termination even of a system consisting of one rule with a
linear
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
left-hand side is undecidable. Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finite ground systems.
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:
The following two examples of terminating term rewrite systems are due to Toyama:
:
and
:
:
Their union is a non-terminating system, since
This result disproves a conjecture of
Dershowitz Dershowitz and Dershwitz is a surname. Notable people with the surname include:
*Alan Dershowitz (born 1938), American lawyer, jurist, writer and political commentator
* Eli Dershwitz (born 1995), American Olympic saber fencer, junior world champio ...
, who claimed that the union of two terminating term rewrite systems and is again terminating if all left-hand sides of and right-hand sides of are
linear
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
, and there are no "''overlaps''" between left-hand sides of and right-hand sides of . All these properties are satisfied by Toyama's examples.
See
Rewrite order
In theoretical computer science, in particular in automated reasoning about formal equations, reduction orderings are used to prevent endless loops. Rewrite orders, and, in turn, rewrite relations, are generalizations of this concept that have tur ...
and
Path ordering (term rewriting)
In theoretical computer science, in particular in term rewriting, a path ordering is a well-founded strict total order (>) on the set of all terms such that
:''f''(...) > ''g''(''s''1,...,''s'n'') if ''f'' .> ''g'' and ...
for ordering relations used in termination proofs for term rewriting systems.
Higher-order rewriting systems
Higher-order rewriting systems are a generalization of first-order term rewriting systems to
lambda term
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation t ...
s, allowing higher order functions and bound variables. Various results about first-order TRSs can be reformulated for HRSs as well.
Graph rewriting systems
Graph rewrite systems are another generalization of term rewrite systems, operating on
graphs
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
representation.
Trace rewriting systems
Trace theory
In mathematics and computer science, trace theory aims to provide a concrete mathematical underpinning for the study of concurrent computation and process calculi. The underpinning is provided by an abstract algebra, algebraic definition of the fr ...
provides a means for discussing multiprocessing in more formal terms, such as via the
trace monoid In computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certa ...
and the
history monoid In mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer process (computer science), processes as a collection of string (computer science), strings, each string representing the i ...
. 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
Causality (also referred to as causation, or cause and effect) is influence by which one event, process, state, or object (''a'' ''cause'') contributes to the production of another event, process, state, or object (an ''effect'') where the cau ...
provers.
See also
*
Critical pair (logic)
A critical pair arises in a term rewriting system when two rewrite rules overlap to yield two different terms. In more detail, (''t''1, ''t''2) is a critical pair if there is a term ''t'' for which two different applications of a rewrite rule (ei ...
*
Compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
*
Knuth–Bendix completion algorithm The Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effectively ...
*
L-system
An L-system or Lindenmayer system is a parallel rewriting system and a type of formal grammar. An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some ...
s specify rewriting that is done in parallel.
*
Referential transparency
In computer science, referential transparency and referential opacity are properties of parts of computer programs. An expression is called ''referentially transparent'' if it can be replaced with its corresponding value (and vice-versa) withou ...
in computer science
*
Regulated rewriting Regulated rewriting is a specific area of formal languages studying grammatical systems which are able to take some kind of control over the production applied in a derivation step. For this reason, the grammatical systems studied in Regulated Rewr ...
*
Rho calculus There are two different calculi that use the name rho-calculus:
* Thfirstis a formalism intended to combine the higher-order facilities of lambda calculus with the pattern matching of term rewriting.
* The second is a reflective higher-order vari ...
Notes
Further reading
* 316 pages.
*
Marc Bezem Marc or MARC may refer to:
People
* Marc (given name), people with the first name
* Marc (surname), people with the family name
Acronyms
* MARC standards, a data format used for library cataloging,
* MARC Train, a regional commuter rail system o ...
,
Jan Willem Klop
Jan Willem Klop (born 1945) is a professor of applied logic at Vrije Universiteit in Amsterdam. He holds a Ph.D. in mathematical logic from Utrecht University. Klop is known for his work on the Algebra of Communicating Processes, co-author of ''T ...
,
Roel de Vrijer Roel son of almighty Zeus and beautiful mortal Alcmene, was the strongest man who ever lived. Now when Roel was eight months old, he woke one night to find a monstrous snake had coiled itself around him. Instead of crying out, baby Roel wrapped his ...
("Terese"), ''Term Rewriting Systems'' ("TeReSe"), Cambridge University Press, 2003, . 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
Nachum Dershowitz is an Israeli computer scientist, known e.g. for the Dershowitz–Manna ordering and the multiset path ordering used to prove termination of term rewrite systems.
He obtained his B.Sc. summa cum laude in 1974 in Computer Scie ...
and
Jean-Pierre Jouannaud
Jean-Pierre Jouannaud is a French computer scientist, known for his work in the area of term rewriting.
He was born on 21 May 1947 in Aix-les-Bains (France).
From 1967 to 1969 he visited the Ecole Polytechnique (Paris).
In 1970, 1972, and 1977, ...
Jan van Leeuwen
Jan van Leeuwen (born December 17, 1946, in Waddinxveen) is a Dutch computer scientist and Emeritus professor of computer science at the Department of Information and Computing Sciences at Utrecht University.
(Ed.), ''
Handbook of Theoretical Computer Science
A handbook is a type of reference work, or other collection of instructions, that is intended to provide ready reference. The term originally applied to a small or portable book containing information useful for its owner, but the ''Oxford Engl ...
, Volume B: Formal Models and Semantics.'', Elsevier and MIT Press, 1990, , pp. 243–320. The
preprint
In academic publishing, a preprint is a version of a scholarly or scientific paper that precedes formal peer review and publication in a peer-reviewed scholarly or scientific journal. The preprint may be available, often as a non-typeset versio ...
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
John Alan Robinson (9 March 1930 – 5 August 2016) was a philosopher, mathematician, and computer scientist. He was a professor emeritus at Syracuse University.
Alan Robinson's major contribution is to the foundations of automated theorem pr ...
and
Andrei Voronkov
Andrei Anatolievič Voronkov (born 1959) is a Professor of Formal methods in the Department of Computer Science at the University of Manchester.
Education
Voronkov was educated at Novosibirsk State University, graduating with a PhD in 1987.
Res ...
(Eds.), ''
Handbook of Automated Reasoning
The ''Handbook of Automated Reasoning'' (, 2128 pages) is a collection of survey articles on the field of automated reasoning. Published in June 2001 by MIT Press, it is edited by John Alan Robinson and Andrei Voronkov. Volume 1 describes methods ...
, Volume 1''.
*
Gérard Huet
Gérard Pierre Huet (; born 7 July 1947) is a French computer scientist, linguist and mathematician. He is senior research director at INRIA and mostly known for his major and seminal contributions to type theory, programming language theory and ...
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
Jan Willem Klop (born 1945) is a professor of applied logic at Vrije Universiteit in Amsterdam. He holds a Ph.D. in mathematical logic from Utrecht University. Klop is known for his work on the Algebra of Communicating Processes, co-author of ''T ...
. "Term Rewriting Systems", Chapter 1 in
Samson Abramsky
Samson Abramsky (born 12 March 1953) is Professor of Computer Science at University College London. He was previously the Christopher Strachey Professor of Computing at the University of Oxford, from 2000 to 2021.
He has made contributions to t ...
,
Dov M. Gabbay
Dov M. Gabbay (; born October 23, 1945) is an Israeli logician. He is Augustus De Morgan Professor Emeritus of Logic at the Group of Logic, Language and Computation, Department of Computer Science, King's College London.
Work
Gabbay has authored ...
and
Tom Maibaum
Thomas Stephen Edward Maibaum Fellow of the Royal Society of Arts (FRSA) is a computer scientist.
Maibaum has a Bachelor of Science (B.Sc.) undergraduate degree in pure mathematics from the University of Toronto, Canada (1970), and a Doctor of Phi ...
(Eds.), ''
Handbook of Logic in Computer Science
A handbook is a type of reference work, or other collection of instructions, that is intended to provide ready reference. The term originally applied to a small or portable book containing information useful for its owner, but the ''Oxford Engl ...
Dov M. Gabbay
Dov M. Gabbay (; born October 23, 1945) is an Israeli logician. He is Augustus De Morgan Professor Emeritus of Logic at the Group of Logic, Language and Computation, Department of Computer Science, King's College London.
Work
Gabbay has authored ...
,
C. J. Hogger
C. or c. may refer to:
* Century, sometimes abbreviated as ''c.'' or ''C.'', a period of 100 years
* Cent (currency), abbreviated ''c.'' or ''¢'', a monetary unit that equals of the basic unit of many currencies
* Caius or Gaius, abbreviated ...
and
John Alan Robinson
John Alan Robinson (9 March 1930 – 5 August 2016) was a philosopher, mathematician, and computer scientist. He was a professor emeritus at Syracuse University.
Alan Robinson's major contribution is to the foundations of automated theorem pr ...
(Eds.), ''
Handbook of Logic in Artificial Intelligence and Logic Programming
A handbook is a type of reference work, or other collection of instructions, that is intended to provide ready reference. The term originally applied to a small or portable book containing information useful for its owner, but the ''Oxford Engl ...
, 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
Ronald Vernon Book (March 5 1937 – May 28, 1997 in Santa Barbara, California) was a theoretical computer scientist. He published more than 150 papers in scientific journals.
His papers are of great impact for computational complexity theory
In ...
and Friedrich Otto, ''String-Rewriting Systems'', Springer (1993).
* Benjamin Benninghofen, Susanne Kemmerich and
Michael M. Richter
Michael M. Richter (21 June 1938 – 10 July 2020) was a German mathematician and computer scientist. Richter is well known for his career in mathematical logic, in particular non-standard analysis, and in artificial intelligence, in partic ...
, ''Systems of Reductions''.
LNCS
''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973.
Overview
The series contains proceedings, post-proceedings, monographs, and Festschrifts. In addition, tutorials, ...
277, Springer-Verlag (1987).
; Other
* Martin Davis,
Ron Sigal Ron is a shortening of the name Ronald.
Ron or RON may also refer to:
Arts and media
* Big Ron (''EastEnders''), a TV character
* Ron (''King of Fighters''), a video game character
*Ron Douglas, the protagonist in ''Lucky Stiff'' played by Joe ...
,
Elaine J. Weyuker
Elaine Jessica Weyuker is an ACM Fellow, an IEEE Fellow (since 2003), and an AT&T Fellow at Bell Labs for research in software metrics and testing as well as elected to the National Academy of Engineering. She is the author of over 130 papers i ...
, (1994) ''Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science – 2nd edition'', Academic Press, .
Aart Middeldorp
Aart is a Dutch short form of the given name Arnout (English Arnold).Aart at the
University of Innsbruck
The University of Innsbruck (german: Leopold-Franzens-Universität Innsbruck; la, Universitas Leopoldino Franciscea) is a public research university in Innsbruck, the capital of the Austrian federal state of Tyrol, founded on October 15, 1669.
...