Misplaced Pages

#927072

107-510: 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 logic ,

214-414: A ∗ ( ( a + 1 ) ∗ ( a + 2 ) ) 1 ∗ ( 2 ∗ 3 ) {\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}} " in elementary algebra. Alternately, the rule could have been applied to the denominator of the original term, yielding a ∗ ( ( a + 1 ) ∗ (

321-487: A + 2 ) ) ( 1 ∗ 2 ) ∗ 3 {\displaystyle {\frac {a*((a+1)*(a+2))}{(1*2)*3}}} . 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

428-428: A , b , c , {\displaystyle a,b,c,} if a R b {\displaystyle aRb} and b R c {\displaystyle bRc} then a R c . {\displaystyle aRc.} A term's definition may require additional properties that are not listed in this table. In mathematics , a binary relation associates elements of one set called

535-653: A complete lattice . In some systems of axiomatic set theory , relations are extended to classes , which are generalizations of sets. This extension is needed for, among other things, modeling the concepts of "is an element of" or "is a subset of" in set theory, without running into logical inconsistencies such as Russell's paradox . A binary relation is the most studied special case n = 2 {\displaystyle n=2} of an n {\displaystyle n} -ary relation over sets X 1 , … , X n {\displaystyle X_{1},\dots ,X_{n}} , which

642-436: A deterministic algorithm . Different models of computation give rise to different reasons that an algorithm may be non-deterministic, and different ways to evaluate its performance or correctness: The notion of nondeterminism was introduced by Robert W. Floyd in 1967. Binary relation All definitions tacitly require the homogeneous relation R {\displaystyle R} be transitive : for all

749-526: A heterogeneous relation . The prefix hetero is from the Greek ἕτερος ( heteros , "other, another, different"). A heterogeneous relation has been called a rectangular relation , suggesting that it does not have the square-like symmetry of a homogeneous relation on a set where A = B . {\displaystyle A=B.} Commenting on the development of binary relations beyond homogeneous relations, researchers wrote, "... a variant of

856-508: A least upper bound (also called supremum) in R . {\displaystyle \mathbb {R} .} However, for the rational numbers this supremum is not necessarily rational, so the same property does not hold on the restriction of the relation ≤ {\displaystyle \leq } to the rational numbers. A binary relation R {\displaystyle R} over sets X {\displaystyle X} and Y {\displaystyle Y}

963-864: A linear 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, but not terminating, and not confluent: f ( x , x ) → g ( x ) , f ( x , g ( x ) ) → b , h ( c , x ) → f ( h ( x , c ) , h ( x , x ) ) . {\displaystyle {\begin{aligned}f(x,x)&\rightarrow g(x),\\f(x,g(x))&\rightarrow b,\\h(c,x)&\rightarrow f(h(x,c),h(x,x)).\\\end{aligned}}} The following two examples of terminating term rewrite systems are due to Toyama: and Their union

1070-401: A semigroup with involution . Some important properties that a homogeneous relation R {\displaystyle R} over a set X {\displaystyle X} may have are: A partial order is a relation that is reflexive, antisymmetric, and transitive. A strict partial order is a relation that is irreflexive, asymmetric, and transitive. A total order

1177-518: A term . The simplest encoding is the one used in the Peano axioms , based on the constant 0 (zero) and the successor function 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

SECTION 10

#1732772378928

1284-463: A binary relation is the " divides " relation over the set of prime numbers P {\displaystyle \mathbb {P} } and the set of integers Z {\displaystyle \mathbb {Z} } , in which each prime p {\displaystyle p} is related to each integer z {\displaystyle z} that is a multiple of p {\displaystyle p} , but not to an integer that

1391-575: A binary relation over every set and its power set. A homogeneous relation over a set X {\displaystyle X} is a binary relation over X {\displaystyle X} and itself, i.e. it is a subset of the Cartesian product X × X . {\displaystyle X\times X.} It is also simply called a (binary) relation over X {\displaystyle X} . A homogeneous relation R {\displaystyle R} over

1498-876: A conjecture of Dershowitz , who claimed that the union of two terminating term rewrite systems R 1 {\displaystyle R_{1}} and R 2 {\displaystyle R_{2}} is again terminating if all left-hand sides of R 1 {\displaystyle R_{1}} and right-hand sides of R 2 {\displaystyle R_{2}} are linear , and there are no " overlaps " between left-hand sides of R 1 {\displaystyle R_{1}} and right-hand sides of R 2 {\displaystyle 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. Higher-order rewriting systems are

1605-405: 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

1712-406: 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. Non-deterministic algorithm In computer science and computer programming , a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to

1819-536: A presentation of the form ( Σ , R ) {\displaystyle (\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 . A term rewriting system ( TRS ) is a rewriting system whose objects are terms , which are expressions with nested sub-expressions. For example,

1926-434: A relation is reflexive , irreflexive, symmetric , antisymmetric , asymmetric , transitive , total , trichotomous , a partial order , total order , strict weak order , total preorder (weak order), or an equivalence relation , then so too are its restrictions. However, the transitive closure of a restriction is a subset of the restriction of the transitive closure, i.e., in general not equal. For example, restricting

2033-502: A semi-Thue system essentially coincides with the presentation of a monoid . Since ↔ R ∗ {\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}} is a congruence, we can define the factor monoid M R = Σ ∗ / ↔ R ∗ {\displaystyle {\mathcal {M}}_{R}=\Sigma ^{*}/{\overset {*}{\underset {R}{\leftrightarrow }}}} of

2140-433: 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

2247-464: A set R {\displaystyle R} of rules can be viewed as an abstract rewriting system as defined above , with terms as its objects and → R {\displaystyle {\underset {R}{\rightarrow }}} as its rewrite relation. For example, x ∗ ( y ∗ z ) → ( x ∗ y ) ∗ z {\displaystyle x*(y*z)\rightarrow (x*y)*z}

SECTION 20

#1732772378928

2354-434: A set X {\displaystyle X} is the power set 2 X × X {\displaystyle 2^{X\times X}} which is a Boolean algebra augmented with the involution of mapping of a relation to its converse relation . Considering composition of relations as a binary operation on B ( X ) {\displaystyle {\mathcal {B}}(X)} , it forms

2461-592: A set X {\displaystyle X} may be identified with a directed simple graph permitting loops , where X {\displaystyle X} is the vertex set and R {\displaystyle R} is the edge set (there is an edge from a vertex x {\displaystyle x} to a vertex y {\displaystyle y} if and only if x R y {\displaystyle xRy} ). The set of all homogeneous relations B ( X ) {\displaystyle {\mathcal {B}}(X)} over

2568-468: 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

2675-492: A specific set A {\displaystyle A} ): the resulting set relation can be denoted by ⊆ A . {\displaystyle \subseteq _{A}.} Also, the "member of" relation needs to be restricted to have domain A {\displaystyle A} and codomain P ( A ) {\displaystyle P(A)} to obtain a binary relation ∈ A {\displaystyle \in _{A}} that

2782-447: 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. Term rewriting systems can be employed to compute arithmetic operations on natural numbers . To this end, each such number has to be encoded as

2889-486: A term t 1 {\displaystyle t_{1}} can be rewritten in several steps into a term t n {\displaystyle t_{n}} , that is, if t 1 → R t 2 → R ⋯ → R t n {\displaystyle t_{1}{\underset {R}{\rightarrow }}t_{2}{\underset {R}{\rightarrow }}\cdots {\underset {R}{\rightarrow }}t_{n}} ,

2996-426: A term rewriting system. Some programming languages are based on term rewriting. One such example is Pure, a functional programming language for mathematical applications. A rewrite rule is a pair of terms , commonly written as l → r {\displaystyle l\rightarrow r} , to indicate that the left-hand side l can be replaced by the right-hand side r . A term rewriting system

3103-447: A theory, equality, membership, and subset are binary relations without special comment. (A minor modification needs to be made to the concept of the ordered triple ( X , Y , G ) {\displaystyle (X,Y,G)} , as normally a proper class cannot be a member of an ordered tuple; or of course one can identify the binary relation with its graph in this context.) With this definition one can for instance define

3210-404: A total order on natural numbers N , {\displaystyle \mathbb {N} ,} " x < y {\displaystyle x<y} " is a strict total order on N , {\displaystyle \mathbb {N} ,} and " x {\displaystyle x} is parallel to y {\displaystyle y} " is an equivalence relation on

3317-451: A wide variety of concepts. These include, among others: A function may be defined as a binary relation that meets additional constraints. Binary relations are also heavily used in computer science . A binary relation over sets X {\displaystyle X} and Y {\displaystyle Y} is an element of the power set of X × Y . {\displaystyle X\times Y.} Since

Rewriting - Misplaced Pages Continue

3424-520: Is confluent iff it has the Church–Rosser property, Newman's lemma (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. 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 {\displaystyle R} , to all strings in

3531-618: Is confluent if for all w , x , and y in A , x ← ∗ w → ∗ y {\displaystyle x{\overset {*}{\leftarrow }}w{\overset {*}{\rightarrow }}y} implies x ↓ y {\displaystyle x\downarrow y} . An ARS is locally confluent if and only if for all w , x , and y in A , x ← w → y {\displaystyle x\leftarrow w\rightarrow y} implies x ↓ y {\displaystyle x{\mathbin {\downarrow }}y} . An ARS

3638-555: Is "is ancestor of"; its restriction to females does relate a woman with her paternal grandmother. Also, the various concepts of completeness (not to be confused with being "total") do not carry over to restrictions. For example, over the real numbers a property of the relation ≤ {\displaystyle \leq } is that every non-empty subset S ⊆ R {\displaystyle S\subseteq \mathbb {R} } with an upper bound in R {\displaystyle \mathbb {R} } has

3745-785: Is a binary relation over sets X {\displaystyle X} and Y {\displaystyle Y} , and S {\displaystyle S} is a binary relation over sets Y {\displaystyle Y} and Z {\displaystyle Z} then S ∘ R = { ( x , z ) ∣  there exists  y ∈ Y  such that  x R y  and  y S z } {\displaystyle S\circ R=\{(x,z)\mid {\text{ there exists }}y\in Y{\text{ such that }}xRy{\text{ and }}ySz\}} (also denoted by R ; S {\displaystyle R;S} )

3852-813: Is a non-terminating system, since f ( g ( 0 , 1 ) , g ( 0 , 1 ) , g ( 0 , 1 ) ) → f ( 0 , g ( 0 , 1 ) , g ( 0 , 1 ) ) → f ( 0 , 1 , g ( 0 , 1 ) ) → f ( g ( 0 , 1 ) , g ( 0 , 1 ) , g ( 0 , 1 ) ) → ⋯ {\displaystyle {\begin{aligned}&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 &\cdots \end{aligned}}} This result disproves

3959-475: Is a relation on Σ ∗ {\displaystyle \Sigma ^{*}} , the pair ( Σ ∗ , → R ) {\displaystyle (\Sigma ^{*},{\underset {R}{\rightarrow }})} fits the definition of an abstract rewriting system. Since the empty string is in Σ ∗ {\displaystyle \Sigma ^{*}} , R {\displaystyle R}

4066-401: Is a relation that is reflexive, antisymmetric, transitive and connected. A strict total order is a relation that is irreflexive, asymmetric, transitive and connected. An equivalence relation is a relation that is reflexive, symmetric, and transitive. For example, " x {\displaystyle x} divides y {\displaystyle y} " is a partial, but not

4173-442: Is a rewrite rule, commonly used to establish a normal form with respect to the associativity of ∗ {\displaystyle *} . That rule can be applied at the numerator in the term a ∗ ( ( a + 1 ) ∗ ( a + 2 ) ) 1 ∗ ( 2 ∗ 3 ) {\displaystyle {\frac {a*((a+1)*(a+2))}{1*(2*3)}}} with

4280-404: Is a set R of such rules. A rule l → r {\displaystyle l\rightarrow r} can be applied to a term s if the left term l matches some subterm of s , that is, if there is some substitution σ {\displaystyle \sigma } such that the subterm of s {\displaystyle s} rooted at some position p

4387-420: Is a set. Bertrand Russell has shown that assuming ∈ {\displaystyle \in } to be defined over all sets leads to a contradiction in naive set theory , see Russell's paradox . Another solution to this problem is to use a set theory with proper classes, such as NBG or Morse–Kelley set theory , and allow the domain and codomain (and so the graph) to be proper classes : in such

Rewriting - Misplaced Pages Continue

4494-411: Is a subset of → R {\displaystyle {\underset {R}{\rightarrow }}} . If the relation R {\displaystyle R} is symmetric , then the system is called a Thue system . In a SRS, the reduction relation → R ∗ {\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}} is compatible with

4601-585: Is a subset of X {\displaystyle X} then R | S = { ( x , y ) ∣ x R y  and  x ∈ S } {\displaystyle R_{\vert S}=\{(x,y)\mid xRy{\text{ and }}x\in S\}} is the left-restriction relation of R {\displaystyle R} to S {\displaystyle S} over X {\displaystyle X} and Y {\displaystyle Y} . If

4708-419: Is a subset of X × Y . {\displaystyle X\times Y.} The set X {\displaystyle X} is called the domain or set of departure of R {\displaystyle R} , and the set Y {\displaystyle Y} the codomain or set of destination of R {\displaystyle R} . In order to specify

4815-983: Is a subset of the Cartesian product X 1 × ⋯ × X n . {\displaystyle X_{1}\times \cdots \times X_{n}.} Given sets X {\displaystyle X} and Y {\displaystyle Y} , the Cartesian product X × Y {\displaystyle X\times Y} is defined as { ( x , y ) ∣ x ∈ X  and  y ∈ Y } , {\displaystyle \{(x,y)\mid x\in X{\text{ and }}y\in Y\},} and its elements are called ordered pairs . A binary relation R {\displaystyle R} over sets X {\displaystyle X} and Y {\displaystyle Y}

4922-544: Is called a monoid presentation of M {\displaystyle {\mathcal {M}}} . We immediately get some very useful connections with other areas of algebra. For example, the alphabet { a , b } {\displaystyle \{a,b\}} with the rules { a b → ε , b a → ε } {\displaystyle \{ab\rightarrow \varepsilon ,ba\rightarrow \varepsilon \}} , where ε {\displaystyle \varepsilon }

5029-610: Is called a "normal form of x " if x → ∗ y {\displaystyle x{\stackrel {*}{\rightarrow }}y} , and y is irreducible. If the normal form of x is unique, then this is usually denoted with x ↓ {\displaystyle x{\downarrow }} . If every object has at least one normal form, the ARS is called normalizing . x ↓ y {\displaystyle x\downarrow y} or x and y are said to be joinable if there exists some z with

5136-419: 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 . Many notions and notations can be defined in the general setting of an ARS. → ∗ {\displaystyle {\overset {*}{\rightarrow }}}

5243-607: Is called the Thue congruence generated by R {\displaystyle R} . In a Thue system, i.e. if R {\displaystyle R} is symmetric, the rewrite relation → R ∗ {\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}} coincides with the Thue congruence ↔ R ∗ {\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}} . The notion of

5350-404: Is contained in S {\displaystyle S} and S {\displaystyle S} is contained in R {\displaystyle R} , then R {\displaystyle R} and S {\displaystyle S} are called equal written R = S {\displaystyle R=S} . If R {\displaystyle R}

5457-417: Is contained in S {\displaystyle S} but S {\displaystyle S} is not contained in R {\displaystyle R} , then R {\displaystyle R} is said to be smaller than S {\displaystyle S} , written R ⊊ S . {\displaystyle R\subsetneq S.} For example, on

SECTION 50

#1732772378928

5564-400: Is determining, given x and y , whether x ↔ ∗ y {\displaystyle x{\overset {*}{\leftrightarrow }}y} . An object x in A is called reducible if there exists some other y in A such that x → y {\displaystyle x\rightarrow y} ; otherwise it is called irreducible or a normal form . An object y

5671-507: Is equal to its converse if and only if it is symmetric . If R {\displaystyle R} is a binary relation over sets X {\displaystyle X} and Y {\displaystyle Y} then R ¯ = { ( x , y ) ∣ ¬ x R y } {\displaystyle {\bar {R}}=\{(x,y)\mid \neg xRy\}} (also denoted by ¬ R {\displaystyle \neg R} )

5778-409: Is in Y {\displaystyle Y} . It encodes the common concept of relation: an element x {\displaystyle x} is related to an element y {\displaystyle y} , if and only if the pair ( x , y ) {\displaystyle (x,y)} belongs to the set of ordered pairs that defines the binary relation. An example of

5885-513: Is not a multiple of p {\displaystyle p} . In this relation, for instance, the prime number 2 {\displaystyle 2} is related to numbers such as − 4 {\displaystyle -4} , 0 {\displaystyle 0} , 6 {\displaystyle 6} , 10 {\displaystyle 10} , but not to 1 {\displaystyle 1} or 9 {\displaystyle 9} , just as

5992-623: Is not necessary that X = Y {\displaystyle X=Y} . Since relations are sets, they can be manipulated using set operations, including union , intersection , and complementation , and satisfying the laws of an algebra of sets . Beyond that, operations like the converse of a relation and the composition of relations are available, satisfying the laws of a calculus of relations , for which there are textbooks by Ernst Schröder , Clarence Lewis , and Gunther Schmidt . A deeper analysis of relations involves decomposing them into subsets called concepts , and placing them in

6099-772: Is said to be contained in a relation S {\displaystyle S} over X {\displaystyle X} and Y {\displaystyle Y} , written R ⊆ S , {\displaystyle R\subseteq S,} if R {\displaystyle R} is a subset of S {\displaystyle S} , that is, for all x ∈ X {\displaystyle x\in X} and y ∈ Y , {\displaystyle y\in Y,} if x R y {\displaystyle xRy} , then x S y {\displaystyle xSy} . If R {\displaystyle R}

6206-417: Is said to be terminating or noetherian if there is no infinite chain x 0 → x 1 → x 2 → ⋯ {\displaystyle x_{0}\rightarrow x_{1}\rightarrow x_{2}\rightarrow \cdots } . A confluent and terminating ARS is called convergent or canonical . Important theorems for abstract rewriting systems are that an ARS

6313-1018: Is the complementary relation of R {\displaystyle R} over X {\displaystyle X} and Y {\displaystyle Y} . For example, = {\displaystyle =} and ≠ {\displaystyle \neq } are each other's complement, as are ⊆ {\displaystyle \subseteq } and ⊈ {\displaystyle \not \subseteq } , ⊇ {\displaystyle \supseteq } and ⊉ {\displaystyle \not \supseteq } , ∈ {\displaystyle \in } and ∉ {\displaystyle \not \in } , and for total orders also < {\displaystyle <} and ≥ {\displaystyle \geq } , and > {\displaystyle >} and ≤ {\displaystyle \leq } . The complement of

6420-505: Is the composition relation of R {\displaystyle R} and S {\displaystyle S} over X {\displaystyle X} and Z {\displaystyle Z} . The identity element is the identity relation. The order of R {\displaystyle R} and S {\displaystyle S} in the notation S ∘ R , {\displaystyle S\circ R,} used here agrees with

6527-654: Is the converse relation , also called inverse relation , of R {\displaystyle R} over Y {\displaystyle Y} and X {\displaystyle X} . For example, = {\displaystyle =} is the converse of itself, as is ≠ {\displaystyle \neq } , and < {\displaystyle <} and > {\displaystyle >} are each other's converse, as are ≤ {\displaystyle \leq } and ≥ {\displaystyle \geq } . A binary relation

SECTION 60

#1732772378928

6634-454: Is the intersection relation of R {\displaystyle R} and S {\displaystyle S} over X {\displaystyle X} and Y {\displaystyle Y} . The identity element is the universal relation. For example, the relation "is divisible by 6" is the intersection of the relations "is divisible by 3" and "is divisible by 2". If R {\displaystyle R}

6741-406: Is the restriction relation of R {\displaystyle R} to S {\displaystyle S} over X {\displaystyle X} . If R {\displaystyle R} is a binary relation over sets X {\displaystyle X} and Y {\displaystyle Y} and if S {\displaystyle S}

6848-425: Is the union relation of R {\displaystyle R} and S {\displaystyle S} over X {\displaystyle X} and Y {\displaystyle Y} . The identity element is the empty relation. For example, ≤ {\displaystyle \leq } is the union of < and =, and ≥ {\displaystyle \geq }

6955-416: Is the empty string , is a presentation of the free group on one generator. If instead the rules are just { a b → ε } {\displaystyle \{ab\rightarrow \varepsilon \}} , 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

7062-524: Is the reflexive transitive closure of → {\displaystyle \rightarrow } . ↔ {\displaystyle \leftrightarrow } is the symmetric closure of → {\displaystyle \rightarrow } . ↔ ∗ {\displaystyle {\overset {*}{\leftrightarrow }}} is the reflexive transitive symmetric closure of → {\displaystyle \rightarrow } . The word problem for an ARS

7169-811: Is the transitive closure of the relation → R {\displaystyle {\underset {R}{\rightarrow }}} ; often, also the notation → R ∗ {\displaystyle {\overset {*}{\underset {R}{\rightarrow }}}} is used to denote the reflexive-transitive closure of → R {\displaystyle {\underset {R}{\rightarrow }}} , that is, s → R ∗ t {\displaystyle s{\overset {*}{\underset {R}{\rightarrow }}}t} if s = t {\displaystyle s=t} or s → R + t {\displaystyle s{\overset {+}{\underset {R}{\rightarrow }}}t} . A term rewriting given by

7276-643: Is the parent of y {\displaystyle y} and y {\displaystyle y} is the mother of z {\displaystyle z} , then x {\displaystyle x} is the maternal grandparent of z {\displaystyle z} . If R {\displaystyle R} is a binary relation over sets X {\displaystyle X} and Y {\displaystyle Y} then R T = { ( y , x ) ∣ x R y } {\displaystyle R^{\textsf {T}}=\{(y,x)\mid xRy\}}

7383-402: Is the result of applying the substitution σ {\displaystyle \sigma } 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 r {\displaystyle r} with

7490-570: Is the set of all x {\displaystyle x} such that x R y {\displaystyle xRy} for at least one y {\displaystyle y} . The codomain of definition , active codomain , image or range of R {\displaystyle R} is the set of all y {\displaystyle y} such that x R y {\displaystyle xRy} for at least one x {\displaystyle x} . The field of R {\displaystyle R}

7597-463: Is the union of > and =. If R {\displaystyle R} and S {\displaystyle S} are binary relations over sets X {\displaystyle X} and Y {\displaystyle Y} then R ∩ S = { ( x , y ) ∣ x R y  and  x S y } {\displaystyle R\cap S=\{(x,y)\mid xRy{\text{ and }}xSy\}}

7704-411: Is the union of its domain of definition and its codomain of definition. When X = Y , {\displaystyle X=Y,} a binary relation is called a homogeneous relation (or endorelation ). To emphasize the fact that X {\displaystyle X} and Y {\displaystyle Y} are allowed to be different, a binary relation is also called

7811-506: Is to select a "large enough" set A {\displaystyle A} , that contains all the objects of interest, and work with the restriction = A {\displaystyle =_{A}} instead of = {\displaystyle =} . Similarly, the "subset of" relation ⊆ {\displaystyle \subseteq } needs to be restricted to have domain and codomain P ( A ) {\displaystyle P(A)} (the power set of

7918-524: The graph of the binary relation. The statement ( x , y ) ∈ R {\displaystyle (x,y)\in R} reads " x {\displaystyle x} is R {\displaystyle R} -related to y {\displaystyle y} " and is denoted by x R y {\displaystyle xRy} . The domain of definition or active domain of R {\displaystyle R}

8025-488: The Boolean semiring (addition corresponds to OR and multiplication to AND) where matrix addition corresponds to union of relations, matrix multiplication corresponds to composition of relations (of a relation over X {\displaystyle X} and Y {\displaystyle Y} and a relation over Y {\displaystyle Y} and Z {\displaystyle Z} ),

8132-537: The Hadamard product corresponds to intersection of relations, the zero matrix corresponds to the empty relation, and the matrix of ones corresponds to the universal relation. Homogeneous relations (when X = Y {\displaystyle X=Y} ) form a matrix semiring (indeed, a matrix semialgebra over the Boolean semiring) where the identity matrix corresponds to the identity relation. While

8239-391: The converse relation R T {\displaystyle R^{\textsf {T}}} is the converse of the complement: R T ¯ = R ¯ T . {\displaystyle {\overline {R^{\mathsf {T}}}}={\bar {R}}^{\mathsf {T}}.} If X = Y , {\displaystyle X=Y,}

8346-444: The domain with elements of another set called the codomain . Precisely, a binary relation over sets X {\displaystyle X} and Y {\displaystyle Y} is a set of ordered pairs ( x , y ) {\displaystyle (x,y)} where x {\displaystyle x} is in X {\displaystyle X} and y {\displaystyle y}

8453-579: The rational numbers , the relation > {\displaystyle >} is smaller than ≥ {\displaystyle \geq } , and equal to the composition > ∘ > {\displaystyle >\circ >} . Binary relations over sets X {\displaystyle X} and Y {\displaystyle Y} can be represented algebraically by logical matrices indexed by X {\displaystyle X} and Y {\displaystyle Y} with entries in

8560-536: The 2nd example relation is surjective (see below ), the 1st is not. Some important types of binary relations R {\displaystyle R} over sets X {\displaystyle X} and Y {\displaystyle Y} are listed below. Uniqueness properties: Totality properties (only definable if the domain X {\displaystyle X} and codomain Y {\displaystyle Y} are specified): Uniqueness and totality properties (only definable if

8667-422: The alphabet that contain left- and respectively right-hand sides of some rules as substrings . Formally a semi-Thue system is a tuple ( Σ , R ) {\displaystyle (\Sigma ,R)} where Σ {\displaystyle \Sigma } is a (usually finite) alphabet, and R {\displaystyle R} is a binary relation between some (fixed) strings in

8774-1056: The alphabet, called the set of rewrite rules . The one-step rewriting relation → R {\displaystyle {\underset {R}{\rightarrow }}} induced by R {\displaystyle R} on Σ ∗ {\displaystyle \Sigma ^{*}} is defined as: if s , t ∈ Σ ∗ {\displaystyle s,t\in \Sigma ^{*}} are any strings, then s → R t {\displaystyle s{\underset {R}{\rightarrow }}t} if there exist x , y , u , v ∈ Σ ∗ {\displaystyle x,y,u,v\in \Sigma ^{*}} such that s = x u y {\displaystyle s=xuy} , t = x v y {\displaystyle t=xvy} , and u R v {\displaystyle uRv} . Since → R {\displaystyle {\underset {R}{\rightarrow }}}

8881-434: The choices of the sets X {\displaystyle X} and Y {\displaystyle Y} , some authors define a binary relation or correspondence as an ordered triple ( X , Y , G ) {\displaystyle (X,Y,G)} , where G {\displaystyle G} is a subset of X × Y {\displaystyle X\times Y} called

8988-642: The complement has the following properties: If R {\displaystyle R} is a binary homogeneous relation over a set X {\displaystyle X} and S {\displaystyle S} is a subset of X {\displaystyle X} then R | S = { ( x , y ) ∣ x R y  and  x ∈ S  and  y ∈ S } {\displaystyle R_{\vert S}=\{(x,y)\mid xRy{\text{ and }}x\in S{\text{ and }}y\in S\}}

9095-461: The domain X {\displaystyle X} and codomain Y {\displaystyle Y} are specified): If relations over proper classes are allowed: Certain mathematical "relations", such as "equal to", "subset of", and "member of", cannot be understood to be binary relations as defined above, because their domains and codomains cannot be taken to be sets in the usual systems of axiomatic set theory . For example, to model

9202-490: The form A → X {\displaystyle {\rm {A\rightarrow 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 → N P   V P {\displaystyle {\rm {S\rightarrow NP\ VP}}} means that

9309-411: The free monoid Σ ∗ {\displaystyle \Sigma ^{*}} by the Thue congruence. If a monoid M {\displaystyle {\mathcal {M}}} is isomorphic with M R {\displaystyle {\mathcal {M}}_{R}} , then the semi-Thue system ( Σ , R ) {\displaystyle (\Sigma ,R)}

9416-439: The general concept of "equality" as a binary relation = {\displaystyle =} , take the domain and codomain to be the "class of all sets", which is not a set in the usual set theory. In most mathematical contexts, references to the relations of equality, membership and subset are harmless because they can be understood implicitly to be restricted to some set in the context. The usual work-around to this problem

9523-455: The inclusion symbol is superfluous. Nevertheless, composition of relations and manipulation of the operators according to Schröder rules , provides a calculus to work in the power set of A × B . {\displaystyle A\times B.} In contrast to homogeneous relations, the composition of relations operation is only a partial function . The necessity of matching target to source of composed relations has led to

9630-428: The latter set is ordered by inclusion ( ⊆ {\displaystyle \subseteq } ), each relation has a place in the lattice of subsets of X × Y . {\displaystyle X\times Y.} A binary relation is called a homogeneous relation when X = Y {\displaystyle X=Y} . A binary relation is also called a heterogeneous relation when it

9737-472: The matching substitution { x ↦ a , y ↦ a + 1 , z ↦ a + 2 } {\displaystyle \{x\mapsto a,\;y\mapsto a+1,\;z\mapsto a+2\}} , see picture 2. Applying that substitution to the rule's right-hand side yields the term ( a ∗ ( a + 1 ) ) ∗ ( a + 2 ) {\displaystyle (a*(a+1))*(a+2)} , and replacing

9844-514: The monoid operation, meaning that x → R ∗ y {\displaystyle x{\overset {*}{\underset {R}{\rightarrow }}}y} implies u x v → R ∗ u y v {\displaystyle uxv{\overset {*}{\underset {R}{\rightarrow }}}uyv} for all strings x , y , u , v ∈ Σ ∗ {\displaystyle x,y,u,v\in \Sigma ^{*}} . Similarly,

9951-480: The numerator by that term yields ( a ∗ ( a + 1 ) ) ∗ ( a + 2 ) 1 ∗ ( 2 ∗ 3 ) {\displaystyle {\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 ∗ {\displaystyle *} to

10058-440: The prime number 3 {\displaystyle 3} is related to 0 {\displaystyle 0} , 6 {\displaystyle 6} , and 9 {\displaystyle 9} , but not to 4 {\displaystyle 4} or 13 {\displaystyle 13} . Binary relations, and especially homogeneous relations , are used in many branches of mathematics to model

10165-399: The procedure for obtaining the conjunctive normal form (CNF) of a formula can be implemented as a rewriting system. The rules of an example of such a system would be: where the symbol ( → {\displaystyle \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

10272-522: The property that x → ∗ z ← ∗ y {\displaystyle x{\overset {*}{\rightarrow }}z{\overset {*}{\leftarrow }}y} . An ARS is said to possess the Church–Rosser property if x ↔ ∗ y {\displaystyle x{\overset {*}{\leftrightarrow }}y} implies x ↓ y {\displaystyle x\downarrow y} . An ARS

10379-543: The reflexive transitive symmetric closure of → R {\displaystyle {\underset {R}{\rightarrow }}} , denoted ↔ R ∗ {\displaystyle {\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 ↔ R ∗ {\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}

10486-406: The relation " x {\displaystyle x} is parent of y {\displaystyle y} " to females yields the relation " x {\displaystyle x} is mother of the woman y {\displaystyle y} "; its transitive closure does not relate a woman with her paternal grandmother. On the other hand, the transitive closure of "is parent of"

10593-409: 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. 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

10700-516: The set of all lines in the Euclidean plane . All operations defined in section § Operations also apply to homogeneous relations. Beyond that, a homogeneous relation over a set X {\displaystyle X} may be subjected to closure operations like: Developments in algebraic logic have facilitated usage of binary relations. The calculus of relations includes the algebra of sets , extended by composition of relations and

10807-413: The standard notational order for composition of functions . For example, the composition (is parent of) ∘ {\displaystyle \circ } (is mother of) yields (is maternal grandparent of), while the composition (is mother of) ∘ {\displaystyle \circ } (is parent of) yields (is grandmother of). For the former case, if x {\displaystyle x}

10914-691: The substitution σ {\displaystyle \sigma } applied, see picture 1. In this case, s {\displaystyle s} is said to be rewritten in one step , or rewritten directly , to t {\displaystyle t} by the system R {\displaystyle R} , formally denoted as s → R t {\displaystyle s\rightarrow _{R}t} , s → R t {\displaystyle s{\underset {R}{\rightarrow }}t} , or as s → R t {\displaystyle s{\overset {R}{\rightarrow }}t} by some authors. If

11021-454: The system shown under § Logic above is a term rewriting system. The terms in this system are composed of binary operators ( ∨ ) {\displaystyle (\vee )} and ( ∧ ) {\displaystyle (\wedge )} and the unary operator ( ¬ ) {\displaystyle (\neg )} . Also present in the rules are variables, which represent any possible term (though

11128-488: The term t 1 {\displaystyle t_{1}} is said to be rewritten to t n {\displaystyle t_{n}} , formally denoted as t 1 → R + t n {\displaystyle t_{1}{\overset {+}{\underset {R}{\rightarrow }}}t_{n}} . In other words, the relation → R + {\displaystyle {\overset {+}{\underset {R}{\rightarrow }}}}

11235-1121: The term "correspondence" for a binary relation with reference to X {\displaystyle X} and Y {\displaystyle Y} . In a binary relation, the order of the elements is important; if x ≠ y {\displaystyle x\neq y} then y R x {\displaystyle yRx} can be true or false independently of x R y {\displaystyle xRy} . For example, 3 {\displaystyle 3} divides 9 {\displaystyle 9} , but 9 {\displaystyle 9} does not divide 3 {\displaystyle 3} . If R {\displaystyle R} and S {\displaystyle S} are binary relations over sets X {\displaystyle X} and Y {\displaystyle Y} then R ∪ S = { ( x , y ) ∣ x R y  or  x S y } {\displaystyle R\cup S=\{(x,y)\mid xRy{\text{ or }}xSy\}}

11342-601: The theory has evolved that treats relations from the very beginning as heterogeneous or rectangular , i.e. as relations where the normal case is that they are relations between different sets." The terms correspondence , dyadic relation and two-place relation are synonyms for binary relation, though some authors use the term "binary relation" for any subset of a Cartesian product X × Y {\displaystyle X\times Y} without reference to X {\displaystyle X} and Y {\displaystyle Y} , and reserve

11449-593: The use of converse relations . The inclusion R ⊆ S , {\displaystyle R\subseteq S,} meaning that a R b {\displaystyle aRb} implies a S b {\displaystyle aSb} , sets the scene in a lattice of relations. But since P ⊆ Q ≡ ( P ∩ Q ¯ = ∅ ) ≡ ( P ∩ Q = P ) , {\displaystyle P\subseteq Q\equiv (P\cap {\bar {Q}}=\varnothing )\equiv (P\cap Q=P),}

#927072