Misplaced Pages

#0

83-525: (Redirected from Reduce ) [REDACTED] Look up reduce , reduced , or reduction in Wiktionary, the free dictionary. Reduction , reduced , or reduce may refer to: Science and technology [ edit ] Chemistry [ edit ] Reduction (chemistry) , part of a reduction-oxidation (redox) reaction in which atoms have their oxidation state changed. Organic redox reaction ,

166-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 ) ∗ (

249-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

332-871: 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

415-519: 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

498-877: 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

581-463: A family of higher-order functions that process a data structure in some order and build up a return value Reduced instruction set computing , a CPU design philosophy favoring an instruction set reduced in size and complexity of addressing, to simplify implementation, instruction level parallelism, and compiling Pure mathematics and statistics [ edit ] Reducible as the opposite of irreducible (mathematics) Reduction (mathematics) ,

664-628: A form of argument in which a proposition is disproven by following its implications to an absurd consequence Eidetic reduction , a technique in the study of essences in phenomenology whose goal is to identify the basic components of phenomena Intertheoretic reduction , in philosophy of science, one theory makes predictions that perfectly or almost perfectly match the predictions of a second theory Settlements [ edit ] Reductions , settlements in Spanish America intended to control and Christianize Indians Indian reductions in

747-563: A form of argument in which a proposition is disproven by following its implications to an absurd consequence Eidetic reduction , a technique in the study of essences in phenomenology whose goal is to identify the basic components of phenomena Intertheoretic reduction , in philosophy of science, one theory makes predictions that perfectly or almost perfectly match the predictions of a second theory Settlements [ edit ] Reductions , settlements in Spanish America intended to control and Christianize Indians Indian reductions in

830-534: A general-purpose computer algebra system geared towards applications in physics Reduce (higher-order function) , in functional programming, a family of higher-order functions that process a data structure in some order and build up a return value Reduced instruction set computing , a CPU design philosophy favoring an instruction set reduced in size and complexity of addressing, to simplify implementation, instruction level parallelism, and compiling Pure mathematics and statistics [ edit ] Reducible as

913-407: 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

SECTION 10

#1732786858000

996-437: A lump of tool stone Noise reduction , in acoustic or signal processing Reduction drive , a mechanical device to shift rotational speed Arts and media [ edit ] Reducing (film) , a 1931 American film Reduction (music) , music arranged for smaller resources (piano) for easier analysis or performance Linguistics [ edit ] Accent reduction , modifying one's foreign accent towards that of

1079-437: A lump of tool stone Noise reduction , in acoustic or signal processing Reduction drive , a mechanical device to shift rotational speed Arts and media [ edit ] Reducing (film) , a 1931 American film Reduction (music) , music arranged for smaller resources (piano) for easier analysis or performance Linguistics [ edit ] Accent reduction , modifying one's foreign accent towards that of

1162-616: A native speaker Vowel reduction , any change in vowel quality perceived as "weakening" Vowel reduction in English Relaxed pronunciation , slurring of syllables of common words Definite article reduction , use of vowel-less forms of the English definite article in Northern England Philosophy [ edit ] Reductionism , a range of philosophical systems Reductio ad absurdum ,

1245-415: A native speaker Vowel reduction , any change in vowel quality perceived as "weakening" Vowel reduction in English Relaxed pronunciation , slurring of syllables of common words Definite article reduction , use of vowel-less forms of the English definite article in Northern England Philosophy [ edit ] Reductionism , a range of philosophical systems Reductio ad absurdum ,

1328-537: 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,

1411-625: A redox reaction that takes place with organic compounds Ore reduction: see smelting Computing and algorithms [ edit ] Reduction (complexity) , a transformation of one problem into another problem Reduction (recursion theory) , given sets A and B of natural numbers, is it possible to effectively convert a method for deciding membership in B into a method for deciding membership in A? Bit Rate Reduction , an audio compression method Data reduction , simplifying data in order to facilitate analysis Graph reduction , an efficient version of non-strict evaluation L-reduction ,

1494-416: A reduction-oxidation (redox) reaction in which atoms have their oxidation state changed. Organic redox reaction , a redox reaction that takes place with organic compounds Ore reduction: see smelting Computing and algorithms [ edit ] Reduction (complexity) , a transformation of one problem into another problem Reduction (recursion theory) , given sets A and B of natural numbers,

1577-502: A rewrite of an expression that does not change its type Reduction of order , a technique for solving second-order ordinary differential equations Reduction of the structure group , for a G {\displaystyle G} -bundle B {\displaystyle B} and a map H → G {\displaystyle H\to G} an H {\displaystyle H} -bundle B H {\displaystyle B_{H}} such that

1660-502: A rewrite of an expression that does not change its type Reduction of order , a technique for solving second-order ordinary differential equations Reduction of the structure group , for a G {\displaystyle G} -bundle B {\displaystyle B} and a map H → G {\displaystyle H\to G} an H {\displaystyle H} -bundle B H {\displaystyle B_{H}} such that

1743-507: A ring with no non-zero nilpotent elements Reduced row echelon form , a certain reduced row echelon form of a matrix which completely and uniquely determines its row space Reduced word , in a free group, a word with no adjacent generator-inverse pairs Variance reduction , a procedure used to increase the precision of the estimates that can be obtained for a given number of iterations Medicine [ edit ] Medical procedures [ edit ] Lung volume reduction surgery ,

SECTION 20

#1732786858000

1826-507: A ring with no non-zero nilpotent elements Reduced row echelon form , a certain reduced row echelon form of a matrix which completely and uniquely determines its row space Reduced word , in a free group, a word with no adjacent generator-inverse pairs Variance reduction , a procedure used to increase the precision of the estimates that can be obtained for a given number of iterations Medicine [ edit ] Medical procedures [ edit ] Lung volume reduction surgery ,

1909-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

1992-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

2075-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}

2158-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

2241-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

2324-460: A technique for reducing the size of the state-space to be searched by a model checking algorithm Strength reduction , a compiler optimization where a function of some systematically changing variable is calculated more efficiently by using previous values of the function Reduce (computer algebra system) , a general-purpose computer algebra system geared towards applications in physics Reduce (higher-order function) , in functional programming,

2407-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}} ,

2490-429: 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

2573-428: A transformation of optimization problems which keeps the approximability features Partial order reduction , a technique for reducing the size of the state-space to be searched by a model checking algorithm Strength reduction , a compiler optimization where a function of some systematically changing variable is calculated more efficiently by using previous values of the function Reduce (computer algebra system) ,

Reduction - Misplaced Pages Continue

2656-539: A treatment for chronic obstructive pulmonary disease Selective reduction (or fetal reduction), the practice of reducing the number of fetuses in a multifetal pregnancy Reduction (orthopedic surgery) , a medical procedure to restore a fracture or dislocation to the correct alignment Ventricular reduction , a type of operation in cardiac surgery Cosmetic surgery: Breast reduction Jaw reduction Other uses in medicine [ edit ] Weight loss In epidemiology: Relative risk reduction ,

2739-539: A treatment for chronic obstructive pulmonary disease Selective reduction (or fetal reduction), the practice of reducing the number of fetuses in a multifetal pregnancy Reduction (orthopedic surgery) , a medical procedure to restore a fracture or dislocation to the correct alignment Ventricular reduction , a type of operation in cardiac surgery Cosmetic surgery: Breast reduction Jaw reduction Other uses in medicine [ edit ] Weight loss In epidemiology: Relative risk reduction ,

2822-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

2905-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

2988-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

3071-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}

3154-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

3237-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

3320-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

3403-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 }

Reduction - Misplaced Pages Continue

3486-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

3569-423: 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 }}}

3652-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

3735-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

3818-463: Is different from Wikidata All article disambiguation pages All disambiguation pages reduce (Redirected from Reduce ) [REDACTED] Look up reduce , reduced , or reduction in Wiktionary, the free dictionary. Reduction , reduced , or reduce may refer to: Science and technology [ edit ] Chemistry [ edit ] Reduction (chemistry) , part of

3901-639: Is different from Wikidata All article disambiguation pages All disambiguation pages Reduction system 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 ,

3984-441: Is it possible to effectively convert a method for deciding membership in B into a method for deciding membership in A? Bit Rate Reduction , an audio compression method Data reduction , simplifying data in order to facilitate analysis Graph reduction , an efficient version of non-strict evaluation L-reduction , a transformation of optimization problems which keeps the approximability features Partial order reduction ,

4067-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

4150-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

4233-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

SECTION 50

#1732786858000

4316-812: 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

4399-403: 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

4482-740: The Spanish colonization of the Americas See also [ edit ] Prevention (disambiguation) Risk reduction (disambiguation) Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title Reduction . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=Reduction&oldid=1183076657 " Categories : Disambiguation pages Mathematics disambiguation pages Hidden categories: Short description

4565-625: The Spanish colonization of the Americas See also [ edit ] Prevention (disambiguation) Risk reduction (disambiguation) Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title Reduction . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=Reduction&oldid=1183076657 " Categories : Disambiguation pages Mathematics disambiguation pages Hidden categories: Short description

4648-514: The Andes , settlements in the Andes to control and Christianize Indians Other uses [ edit ] Reduction (cooking) , the process of thickening or intensifying the flavor of a liquid mixture such as a soup, sauce, wine, or juice by evaporation Reduction (military) , the siege and capture of a fortified place Reduction (Sweden) , a return to the Crown of fiefs that had been granted to

4731-410: The Andes , settlements in the Andes to control and Christianize Indians Other uses [ edit ] Reduction (cooking) , the process of thickening or intensifying the flavor of a liquid mixture such as a soup, sauce, wine, or juice by evaporation Reduction (military) , the siege and capture of a fortified place Reduction (Sweden) , a return to the Crown of fiefs that had been granted to

4814-541: The Swedish nobility Reduce (waste) , practices of minimizing waste Reduction, Pennsylvania , unincorporated community, United States Reduction in rank , in military law Reduction to practice , in United States patent law, the embodiment of the concept of an invention Ego reduction , predicated on the use of Sigmund Freud's concept of the ego Reductions , resettlement of indigenous peoples during

4897-423: The Swedish nobility Reduce (waste) , practices of minimizing waste Reduction, Pennsylvania , unincorporated community, United States Reduction in rank , in military law Reduction to practice , in United States patent law, the embodiment of the concept of an invention Ego reduction , predicated on the use of Sigmund Freud's concept of the ego Reductions , resettlement of indigenous peoples during

4980-405: The absolute risk reduction by the control event rate Absolute risk reduction , the decrease in risk of a given activity or treatment in relation to a control activity or treatment Urea reduction ratio (URR), a dimensionless number used to quantify hemodialysis treatment adequacy Physics [ edit ] Dimensional reduction , the limit of a compactified theory where the size of

5063-405: The absolute risk reduction by the control event rate Absolute risk reduction , the decrease in risk of a given activity or treatment in relation to a control activity or treatment Urea reduction ratio (URR), a dimensionless number used to quantify hemodialysis treatment adequacy Physics [ edit ] Dimensional reduction , the limit of a compactified theory where the size of

SECTION 60

#1732786858000

5146-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

5229-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 }}}

5312-588: The compact dimension goes to zero Reduction criterion , in quantum information theory, a necessary condition a mixed state must satisfy in order for it to be separable Reduced mass , the "effective" inertial mass appearing in the two-body problem of Newtonian mechanics Reduced properties (pressure, temperature, or volume) of a fluid, defined based on the fluid's critical point Other uses in science and technology [ edit ] Lithic reduction , in Stone Age toolmaking, to detach lithic flakes from

5395-531: The compact dimension goes to zero Reduction criterion , in quantum information theory, a necessary condition a mixed state must satisfy in order for it to be separable Reduced mass , the "effective" inertial mass appearing in the two-body problem of Newtonian mechanics Reduced properties (pressure, temperature, or volume) of a fluid, defined based on the fluid's critical point Other uses in science and technology [ edit ] Lithic reduction , in Stone Age toolmaking, to detach lithic flakes from

5478-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

5561-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)}

5644-473: 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

5727-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,

5810-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

5893-477: The opposite of irreducible (mathematics) Reduction (mathematics) , the rewriting of an expression into a simpler form Beta reduction , the rewriting of an expression from lambda calculus into a simpler form Dimension reduction , the process of reducing the number of random variables under consideration Lattice reduction , given an integer lattice basis as input, to find a basis with short, nearly orthogonal vectors Subject reduction or preservation,

5976-400: 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

6059-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

6142-446: The pushout B H × H G {\displaystyle B_{H}\times _{H}G} is isomorphic to B {\displaystyle B} Reduction system , reduction strategy, the application of rewriting systems to eliminate reducible expressions Reduced form , in statistics, an equation which relates the endogenous variable X to all the available exogenous variables, both those included in

6225-446: The pushout B H × H G {\displaystyle B_{H}\times _{H}G} is isomorphic to B {\displaystyle B} Reduction system , reduction strategy, the application of rewriting systems to eliminate reducible expressions Reduced form , in statistics, an equation which relates the endogenous variable X to all the available exogenous variables, both those included in

6308-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 }}}}

6391-448: The regression of interest (W) and the instruments (Z) Reduced homology , a minor modification made to homology theory in algebraic topology, designed to make a point have all its homology groups zero Reduced product , a construction that generalizes both direct product and ultraproduct Reduced residue system , a set of φ(n) integers such that each integer is relatively prime to n and no two are congruent modulo n Reduced ring ,

6474-448: The regression of interest (W) and the instruments (Z) Reduced homology , a minor modification made to homology theory in algebraic topology, designed to make a point have all its homology groups zero Reduced product , a construction that generalizes both direct product and ultraproduct Reduced residue system , a set of φ(n) integers such that each integer is relatively prime to n and no two are congruent modulo n Reduced ring ,

6557-403: The rewriting of an expression into a simpler form Beta reduction , the rewriting of an expression from lambda calculus into a simpler form Dimension reduction , the process of reducing the number of random variables under consideration Lattice reduction , given an integer lattice basis as input, to find a basis with short, nearly orthogonal vectors Subject reduction or preservation,

6640-410: 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

6723-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

6806-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

6889-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 }}}}

#0