Misplaced Pages

#670329

112-504: [REDACTED] Look up narrowing in Wiktionary, the free dictionary. Narrowing may refer to: Narrowing (computer science) , a type of algorithm for solving equations between symbolic expressions Narrowing of algebraic value sets , a method for the elimination of values from a solution set which are inconsistent with the equations being solved Narrowing (historical linguistics) ,

224-444: A ∗ a ) ) } {\displaystyle \{z\mapsto a,y\mapsto a*a,x\mapsto (a*a)*(a*a),w\mapsto ((a*a)*(a*a))*((a*a)*(a*a))\}} ⁠ , cf. picture. In order to avoid exponential time complexity caused by such blow-up, advanced unification algorithms work on directed acyclic graphs (dags) rather than trees. The concept of unification is one of the main ideas behind logic programming . Specifically, unification

336-632: A , g ( z 1 ) , y 1 ) {\displaystyle f(x_{1},a,g(z_{1}),y_{1})} is a variant of f ( x 2 , a , g ( z 2 ) , y 2 ) {\displaystyle f(x_{2},a,g(z_{2}),y_{2})} , since f ( x 1 , a , g ( z 1 ) , y 1 ) { x 1 ↦ x 2 , y 1 ↦ y 2 , z 1 ↦ z 2 } = f ( x 2 ,

448-402: A , g ( z 1 ) , y 1 ) . {\displaystyle f(x_{2},a,g(z_{2}),y_{2})\{x_{2}\mapsto x_{1},y_{2}\mapsto y_{1},z_{2}\mapsto z_{1}\}=f(x_{1},a,g(z_{1}),y_{1}).} However, f ( x 1 , a , g ( z 1 ) , y 1 ) {\displaystyle f(x_{1},a,g(z_{1}),y_{1})} is not

560-530: A , g ( z 2 ) , y 2 ) {\displaystyle f(x_{1},a,g(z_{1}),y_{1})\{x_{1}\mapsto x_{2},y_{1}\mapsto y_{2},z_{1}\mapsto z_{2}\}=f(x_{2},a,g(z_{2}),y_{2})} and f ( x 2 , a , g ( z 2 ) , y 2 ) { x 2 ↦ x 1 , y 2 ↦ y 1 , z 2 ↦ z 1 } = f ( x 1 ,

672-447: A , y ↦ a } {\displaystyle \{x\mapsto a,y\mapsto a\}} is subsumed by τ = { x ↦ y } {\displaystyle \tau =\{x\mapsto y\}} , using θ = { y ↦ a } {\displaystyle \theta =\{y\mapsto a\}} , but σ = { x ↦ a } {\displaystyle \sigma =\{x\mapsto a\}}

784-433: A r , n l h s , n e q n ⟩ {\displaystyle \langle n_{var},n_{lhs},n_{eqn}\rangle } where n var is the number of variables that occur more than once in the equation set, n lhs is the number of function symbols and constants on the left hand sides of potential equations, and n eqn is the number of equations. When rule eliminate

896-511: A dual pair to show the underlying duality . This is similar to the use of bra–ket notation in quantum mechanics. In logic and the theory of computation , the function notation of lambda calculus is used to explicitly express the basic notions of function abstraction and application . In category theory and homological algebra , networks of functions are described in terms of how they and their compositions commute with each other using commutative diagrams that extend and generalize

1008-406: A function from a set X to a set Y assigns to each element of X exactly one element of Y . The set X is called the domain of the function and the set Y is called the codomain of the function. Functions were originally the idealization of how a varying quantity depends on another quantity. For example, the position of a planet is a function of time. Historically , the concept

1120-432: A map or a mapping , but some authors make a distinction between the term "map" and "function". For example, the term "map" is often reserved for a "function" with some sort of special structure (e.g. maps of manifolds ). In particular map may be used in place of homomorphism for the sake of succinctness (e.g., linear map or map from G to H instead of group homomorphism from G to H ). Some authors reserve

1232-405: A roman type is customarily used instead, such as " sin " for the sine function , in contrast to italic font for single-letter symbols. The functional notation is often used colloquially for referring to a function and simultaneously naming its argument, such as in "let f ( x ) {\displaystyle f(x)} be a function". This is an abuse of notation that is useful for

SECTION 10

#1732852340671

1344-555: A constant declaration lassie : dog , the term mother ( lassie ) is perfectly valid and has the sort animal . In order to supply the information that the mother of a dog is a dog in turn, another declaration mother : dog → dog may be issued; this is called function overloading , similar to overloading in programming languages . Walther gave a unification algorithm for terms in order-sorted logic, requiring for any two declared sorts s 1 , s 2 their intersection s 1 ∩ s 2 to be declared, too: if x 1 and x 2

1456-469: A first-order example, applying the substitution { x ↦ h ( a , y ), z ↦ b } to the term If a term t {\displaystyle t} has an instance equivalent to a term u {\displaystyle u} , that is, if t σ ≡ u {\displaystyle t\sigma \equiv u} for some substitution σ {\displaystyle \sigma } , then t {\displaystyle t}

1568-429: A function defined by an integral with variable upper bound: x ↦ ∫ a x f ( u ) d u {\textstyle x\mapsto \int _{a}^{x}f(u)\,du} . There are other, specialized notations for functions in sub-disciplines of mathematics. For example, in linear algebra and functional analysis , linear forms and the vectors they act upon are denoted using

1680-401: A function has evolved significantly over centuries, from its informal origins in ancient mathematics to its formalization in the 19th century. See History of the function concept for details. A function f from a set X to a set Y is an assignment of one element of Y to each element of X . The set X is called the domain of the function and the set Y is called the codomain of

1792-523: A function is commonly written as f ( x , y ) = x 2 + y 2 {\displaystyle f(x,y)=x^{2}+y^{2}} and referred to as "a function of two variables". Likewise one can have a function of three or more variables, with notations such as f ( w , x , y ) {\displaystyle f(w,x,y)} , f ( w , x , y , z ) {\displaystyle f(w,x,y,z)} . A function may also be called

1904-513: A function is defined. In particular, it is common that one might only know, without some (possibly difficult) computation, that the domain of a specific function is contained in a larger set. For example, if f : R → R {\displaystyle f:\mathbb {R} \to \mathbb {R} } is a real function , the determination of the domain of the function x ↦ 1 / f ( x ) {\displaystyle x\mapsto 1/f(x)} requires knowing

2016-405: A function is then called a partial function . The range or image of a function is the set of the images of all elements in the domain. A function f on a set S means a function from the domain S , without specifying a codomain. However, some authors use it as shorthand for saying that the function is f  : S → S . The above definition of a function is essentially that of

2128-552: A letter such as f , g or h . The value of a function f at an element x of its domain (that is, the element of the codomain that is associated with x ) is denoted by f ( x ) ; for example, the value of f at x = 4 is denoted by f (4) . Commonly, a specific function is defined by means of an expression depending on x , such as f ( x ) = x 2 + 1 ; {\displaystyle f(x)=x^{2}+1;} in this case, some computation, called function evaluation , may be needed for deducing

2240-417: A multivariate function is a function that has a Cartesian product or a proper subset of a Cartesian product as a domain. where the domain U has the form If all the X i {\displaystyle X_{i}} are equal to the set R {\displaystyle \mathbb {R} } of the real numbers or to the set C {\displaystyle \mathbb {C} } of

2352-465: A programming example, a parametric sort list ( X ) may be declared (with X being a type parameter as in a C++ template ), and from a subsort declaration int ⊆ float the relation list ( int ) ⊆ list ( float ) is automatically inferred, meaning that each list of integers is also a list of floats. Schmidt-Schauß generalized order-sorted logic to allow for term declarations. As an example, assuming subsort declarations even ⊆ int and odd ⊆ int ,

SECTION 20

#1732852340671

2464-495: A similar technique as Paterson-Wegman, hence is linear, but like most linear-time unification algorithms is slower than the Robinson version on small sized inputs due to the overhead of preprocessing the inputs and postprocessing of the output, such as construction of a DAG representation. de Champeaux (2022) is also of linear complexity in the input size but is competitive with the Robinson algorithm on small size inputs. The speedup

2576-450: A simpler formulation. Arrow notation defines the rule of a function inline, without requiring a name to be given to the function. It uses the ↦ arrow symbol, pronounced " maps to ". For example, x ↦ x + 1 {\displaystyle x\mapsto x+1} is the function which takes a real number as input and outputs that number plus 1. Again, a domain and codomain of R {\displaystyle \mathbb {R} }

2688-406: A solution is required to make both sides of each equation literally equal, the process is called syntactic or free unification , otherwise semantic or equational unification , or E-unification , or unification modulo theory . If the right side of each equation is closed (no free variables), the problem is called (pattern) matching . The left side (with variables) of each equation is called

2800-403: A sort s 1 a subsort of another sort s 2 , commonly written as s 1 ⊆ s 2 . For example, when reаsoning about biological creatures, it is useful to declare a sort dog to be a subsort of a sort animal . Wherever a term of some sort s is required, a term of any subsort of s may be supplied instead. For example, assuming a function declaration mother : animal → animal , and

2912-571: A substitution σ {\displaystyle \sigma } is subsumed by another substitution τ {\displaystyle \tau } if there is a substitution θ {\displaystyle \theta } such that for all terms X ∉ V {\displaystyle X\notin V} , X σ ≡ X τ θ {\displaystyle X\sigma \equiv X\tau \theta } . For instance { x ↦

3024-436: A substitution mapping each variable x i {\displaystyle x_{i}} to the term t i {\displaystyle t_{i}} , for i = 1 , . . . , k {\displaystyle i=1,...,k} , and every other variable to itself; the x i {\displaystyle x_{i}} must be pairwise distinct. Applying that substitution to

3136-431: A syntactic first-order unification problem of size n may have a size of 2 . For example, the problem ⁠ ( ( ( a ∗ z ) ∗ y ) ∗ x ) ∗ w ≐ w ∗ ( x ∗ ( y ∗ ( z ∗ a ) ) ) {\displaystyle (((a*z)*y)*x)*w\doteq w*(x*(y*(z*a)))} ⁠ has

3248-450: A term t {\displaystyle t} is written in postfix notation as t { x 1 ↦ t 1 , . . . , x k ↦ t k } {\displaystyle t\{x_{1}\mapsto t_{1},...,x_{k}\mapsto t_{k}\}} ; it means to (simultaneously) replace every occurrence of each variable x i {\displaystyle x_{i}} in

3360-413: A term declaration like ∀ i  : int . ( i + i ) : even allows to declare a property of integer addition that could not be expressed by ordinary overloading. Background on infinite trees: Unification algorithm, Prolog II: Applications: E-unification is the problem of finding solutions to a given set of equations , taking into account some equational background knowledge E . The latter

3472-637: A term may be both more general and more special than a structurally different term. For example, if ⊕ is idempotent , that is, if always x ⊕ x ≡ x {\displaystyle x\oplus x\equiv x} , then the term x ⊕ y {\displaystyle x\oplus y} is more general than z {\displaystyle z} , and vice versa, although x ⊕ y {\displaystyle x\oplus y} and z {\displaystyle z} are of different structure. A substitution σ {\displaystyle \sigma }

Narrowing - Misplaced Pages Continue

3584-402: A term rewrite system R is used defining the append operator of lists built from cons and nil ; where cons ( x , y ) is written in infix notation as x . y for brevity; e.g. app ( a . b . nil , c . d . nil ) → a . app ( b . nil , c . d . nil ) → a . b . app ( nil , c . d . nil ) → a . b . c . d . nil demonstrates the concatenation of the lists a . b . nil and c . d . nil , employing

3696-486: A type of semantic change Collisional narrowing of a spectral line due to collisions of the emitting species Motional narrowing of a resonant frequency due to the inhomogeneity of the system averaging out over time Perceptual narrowing , a process in brain development Q-based narrowing , a concept in pragmatics Stenosis , the narrowing of a blood vessel or other tubular organ See also [ edit ] Narrow (disambiguation) Topics referred to by

3808-405: A variant of f ( x 2 , a , g ( x 2 ) , x 2 ) {\displaystyle f(x_{2},a,g(x_{2}),x_{2})} , since no substitution can transform the latter term into the former one. The latter term is therefore properly more special than the former one. For arbitrary ≡ {\displaystyle \equiv } ,

3920-427: A ⋅ x = x ⋅ a } has each substitution of the form { x ↦ a ⋅...⋅ a } as a solution in a semigroup , i.e. if (⋅) is considered associative . But the same problem, viewed in an abelian group , where (⋅) is considered also commutative , has any substitution at all as a solution. As an example of higher-order unification, the singleton set { a = y ( x ) } is a syntactic second-order unification problem, since y

4032-573: Is commutative , since then ( x ⊕ a ) { x ↦ b } = b ⊕ a ≡ a ⊕ b {\displaystyle (x\oplus a)\{x\mapsto b\}=b\oplus a\equiv a\oplus b} . If ≡ is literal (syntactic) identity of terms, a term may be both more general and more special than another one only if both terms differ just in their variable names, not in their syntactic structure; such terms are called variants , or renamings of each other. For example, f ( x 1 ,

4144-391: Is more special than, or subsumed by, a substitution τ {\displaystyle \tau } if t σ {\displaystyle t\sigma } is subsumed by t τ {\displaystyle t\tau } for each term t {\displaystyle t} . We also say that τ {\displaystyle \tau }

4256-701: Is a singleton set then         return σ {\displaystyle \sigma }     fi     let D be the disagreement set of T σ {\displaystyle T\sigma }     let s , t be the two lexicographically least terms in D     if s is not a variable or s occurs in t then         return "NONUNIFIABLE"     fi     σ := σ { s ↦ t } {\displaystyle \sigma :=\sigma \{s\mapsto t\}} done Jacques Herbrand discussed

4368-404: Is a solution of the unification problem E if l i σ ≡ r i σ for i = 1 , . . . , n {\displaystyle i=1,...,n} . Such a substitution is also called a unifier of E . For example, if ⊕ is associative , the unification problem { x ⊕ a ≐ a ⊕ x } has the solutions { x ↦ a }, { x ↦ a ⊕ a }, { x ↦ a ⊕ a ⊕ a }, etc., while

4480-431: Is a basic building block of resolution , a rule of inference for determining formula satisfiability. In Prolog , the equality symbol = implies first-order syntactic unification. It represents the mechanism of binding the contents of variables and can be viewed as a kind of one-time assignment. In Prolog: Type inference algorithms are typically based on unification, particularly Hindley-Milner type inference which

4592-423: Is a function in two variables, and we want to refer to a partially applied function X → Y {\displaystyle X\to Y} produced by fixing the second argument to the value t 0 without introducing a new function name. The map in question could be denoted x ↦ f ( x , t 0 ) {\displaystyle x\mapsto f(x,t_{0})} using

Narrowing - Misplaced Pages Continue

4704-400: Is a function that depends on several arguments. Such functions are commonly encountered. For example, the position of a car on a road is a function of the time travelled and its average speed. Formally, a function of n variables is a function whose domain is a set of n -tuples. For example, multiplication of integers is a function of two variables, or bivariate function , whose domain is

4816-579: Is a function variable. One solution is { x ↦ a , y ↦ ( identity function ) }; another one is { y ↦ ( constant function mapping each value to a ), x ↦ (any value) }. A substitution is a mapping σ : V → T {\displaystyle \sigma :V\rightarrow T} from variables to terms; the notation { x 1 ↦ t 1 , . . . , x k ↦ t k } {\displaystyle \{x_{1}\mapsto t_{1},...,x_{k}\mapsto t_{k}\}} refers to

4928-592: Is a variable of sort s 1 and s 2 , respectively, the equation x 1 ≐ x 2 has the solution { x 1 = x , x 2 = x }, where x : s 1 ∩ s 2 . After incorporating this algorithm into a clause-based automated theorem prover, he could solve a benchmark problem by translating it into order-sorted logic, thereby boiling it down an order of magnitude, as many unary predicates turned into sorts. Smolka generalized order-sorted logic to allow for parametric polymorphism . In his framework, subsort declarations are propagated to complex type expressions. As

5040-467: Is applied, n var decreases, since x is eliminated from G and kept only in { x ≐ t }. Applying any other rule can never increase n var again. When rule decompose , conflict , or swap is applied, n lhs decreases, since at least the left hand side's outermost f disappears. Applying any of the remaining rules delete or check can't increase n lhs , but decreases n eqn . Hence, any rule application decreases

5152-405: Is called more general than u {\displaystyle u} , and u {\displaystyle u} is called more special than, or subsumed by, t {\displaystyle t} . For example, x ⊕ a {\displaystyle x\oplus a} is more general than a ⊕ b {\displaystyle a\oplus b} if ⊕

5264-479: Is called the Cartesian product of X and Y and denoted X × Y . {\displaystyle X\times Y.} Thus, the above definition may be formalized as follows. A function with domain X and codomain Y is a binary relation R between X and Y that satisfies the two following conditions: This definition may be rewritten more formally, without referring explicitly to

5376-418: Is called the most general unifier ( mgu ) of the problem. The terms on the left and the right hand side of each potential equation become syntactically equal when the mgu is applied i.e. l 1 σ = r 1 σ ∧ ... ∧ l n σ = r n σ . Any unifier of the problem is subsumed by the mgu σ . The mgu is unique up to variants: if S 1 and S 2 are both complete and minimal solution sets of

5488-429: Is commonly presented and originates from Martelli & Montanari (1982) . Given a finite set G = { s 1 ≐ t 1 , . . . , s n ≐ t n } {\displaystyle G=\{s_{1}\doteq t_{1},...,s_{n}\doteq t_{n}\}} of potential equations, the algorithm applies rules to transform it to an equivalent set of equations of

5600-427: Is decidable for the following theories: Unification is semi-decidable for the following theories: If there is a convergent term rewriting system R available for E , the one-sided paramodulation algorithm can be used to enumerate all solutions of given equations. Starting with G being the unification problem to be solved and S being the identity substitution, rules are applied nondeterministically until

5712-443: Is denoted G { x ↦ t }. For simplicity, constant symbols are regarded as function symbols having zero arguments. An attempt to unify a variable x with a term containing x as a strict subterm x ≐ f (..., x , ...) would lead to an infinite term as solution for x , since x would occur as a subterm of itself. In the set of (finite) first-order terms as defined above, the equation x ≐ f (..., x , ...) has no solution; hence

SECTION 50

#1732852340671

5824-499: Is given as a set of universal equalities . For some particular sets E , equation solving algorithms (a.k.a. E-unification algorithms ) have been devised; for others it has been proven that no such algorithms can exist. For example, if a and b are distinct constants, the equation ⁠ x ∗ a ≐ y ∗ b {\displaystyle x*a\doteq y*b} ⁠ has no solution with respect to purely syntactic unification , where nothing

5936-438: Is implied. The domain and codomain can also be explicitly stated, for example: This defines a function sqr from the integers to the integers that returns the square of its input. As a common application of the arrow notation, suppose f : X × X → Y ; ( x , t ) ↦ f ( x , t ) {\displaystyle f:X\times X\to Y;\;(x,t)\mapsto f(x,t)}

6048-432: Is in Y , or it is undefined. The set of the elements of X such that f ( x ) {\displaystyle f(x)} is defined and belongs to Y is called the domain of definition of the function. A partial function from X to Y is thus a ordinary function that has as its domain a subset of X called the domain of definition of the function. If the domain of definition equals X , one often says that

6160-431: Is known about the operator ⁠ ∗ {\displaystyle *} ⁠ . However, if the ⁠ ∗ {\displaystyle *} ⁠ is known to be commutative , then the substitution { x ↦ b , y ↦ a } solves the above equation, since The background knowledge E could state the commutativity of ⁠ ∗ {\displaystyle *} ⁠ by

6272-425: Is more general than σ {\displaystyle \sigma } . More formally, take a nonempty infinite set V {\displaystyle V} of auxiliary variables such that no equation l i ≐ r i {\displaystyle l_{i}\doteq r_{i}} in the unification problem contains variables from V {\displaystyle V} . Then

6384-449: Is not subsumed by τ = { x ↦ y } {\displaystyle \tau =\{x\mapsto y\}} , as f ( x , y ) σ = f ( a , y ) {\displaystyle f(x,y)\sigma =f(a,y)} is not an instance of f ( x , y ) τ = f ( y , y ) {\displaystyle f(x,y)\tau =f(y,y)} . A substitution σ

6496-451: Is obtained by using an object-oriented representation of the predicate calculus that avoids the need for pre- and post-processing, instead making variable objects responsible for creating a substitution and for dealing with aliasing. de Champeaux claims that the ability to add functionality to predicate calculus represented as programmatic objects provides opportunities for optimizing other logic operations as well. The following algorithm

6608-451: Is often the letter f . Then, the application of the function to an argument is denoted by its name followed by its argument (or, in the case of a multivariate functions, its arguments) enclosed between parentheses, such as in The argument between the parentheses may be a variable , often x , that represents an arbitrary element of the domain of the function, a specific element of the domain ( 3 in

6720-460: Is syntactic. This version of unification has a unique "best" answer and is used in logic programming and programming language type system implementation, especially in Hindley–Milner based type inference algorithms. In higher-order unification, possibly restricted to higher-order pattern unification , terms may include lambda expressions, and equivalence is up to beta-reduction. This version

6832-440: Is the value of the function at x , or the image of x under the function. A function f , its domain X , and its codomain Y are often specified by the notation f : X → Y . {\displaystyle f:X\to Y.} One may write x ↦ y {\displaystyle x\mapsto y} instead of y = f ( x ) {\displaystyle y=f(x)} , where

SECTION 60

#1732852340671

6944-433: Is the most widely used unification framework. It is based on T being the set of first-order terms (over some given set V of variables, C of constants and F n of n -ary function symbols) and on ≡ being syntactic equality . In this framework, each solvable unification problem { l 1 ≐ r 1 , ..., l n ≐ r n } has a complete, and obviously minimal, singleton solution set { σ } . Its member σ

7056-462: Is the set of subterms starting at p , formally: { t | p  : t ∈ T {\displaystyle t\in T} }. Algorithm: Given a set T of terms to be unified Let σ {\displaystyle \sigma } initially be the identity substitution do forever     if T σ {\displaystyle T\sigma }

7168-469: Is typically the case for functions whose domain is the set of the natural numbers . Such a function is called a sequence , and, in this case the element f n {\displaystyle f_{n}} is called the n th element of the sequence. The index notation can also be used for distinguishing some variables called parameters from the "true variables". In fact, parameters are specific variables that are considered as being fixed during

7280-479: Is used by the functional languages Haskell and ML . For example, when attempting to infer the type of the Haskell expression True : ['x'] , the compiler will use the type a -> [a] -> [a] of the list construction function (:) , the type Bool of the first argument True , and the type [Char] of the second argument ['x'] . The polymorphic type variable a will be unified with Bool and

7392-573: Is used in proof assistants and higher-order logic programming, for example Isabelle , Twelf , and lambdaProlog . Finally, in semantic unification or E-unification, equality is subject to background knowledge and variables range over a variety of domains. This version is used in SMT solvers , term rewriting algorithms, and cryptographic protocol analysis. A unification problem is a finite set E ={ l 1 ≐ r 1 , ..., l n ≐ r n } of equations to solve, where l i , r i are in

7504-442: The graph of the function , a popular means of illustrating the function. When the domain and the codomain are sets of real numbers, each such pair may be thought of as the Cartesian coordinates of a point in the plane. Functions are widely used in science , engineering , and in most fields of mathematics. It has been said that functions are "the central objects of investigation" in most fields of mathematics. The concept of

7616-687: The Riemann hypothesis . In computability theory , a general recursive function is a partial function from the integers to the integers whose values can be computed by an algorithm (roughly speaking). The domain of definition of such a function is the set of inputs for which the algorithm does not run forever. A fundamental theorem of computability theory is that there cannot exist an algorithm that takes an arbitrary general recursive function as input and tests whether 0 belongs to its domain of definition (see Halting problem ). A multivariate function , multivariable function , or function of several variables

7728-413: The complex numbers , one talks respectively of a function of several real variables or of a function of several complex variables . There are various standard ways for denoting functions. The most commonly used notation is functional notation, which is the first notation described below. The functional notation requires that a name is given to the function, which, in the case of a unspecified function

7840-431: The eliminate rule may only be applied if x ∉ vars ( t ). Since that additional check, called occurs check , slows down the algorithm, it is omitted e.g. in most Prolog systems. From a theoretical point of view, omitting the check amounts to solving equations over infinite trees, see #Unification of infinite terms below. For the proof of termination of the algorithm consider a triple ⟨ n v

7952-438: The pattern . Formally, a unification approach presupposes As an example of how the set of terms and theory affects the set of solutions, the syntactic first-order unification problem { y = cons (2, y ) } has no solution over the set of finite terms . However, it has the single solution { y ↦ cons (2, cons (2, cons (2,...))) } over the set of infinite tree terms. Similarly, the semantic first-order unification problem {

8064-420: The zeros of f. This is one of the reasons for which, in mathematical analysis , "a function from X to Y " may refer to a function having a proper subset of X as a domain. For example, a "function from the reals to the reals" may refer to a real-valued function of a real variable whose domain is a proper subset of the real numbers , typically a subset that contains a non-empty open interval . Such

8176-550: The "total" condition removed. That is, a partial function from X to Y is a binary relation R between X and Y such that, for every x ∈ X , {\displaystyle x\in X,} there is at most one y in Y such that ( x , y ) ∈ R . {\displaystyle (x,y)\in R.} Using functional notation, this means that, given x ∈ X , {\displaystyle x\in X,} either f ( x ) {\displaystyle f(x)}

8288-452: The above example), or an expression that can be evaluated to an element of the domain ( x 2 + 1 {\displaystyle x^{2}+1} in the above example). The use of a unspecified variable between parentheses is useful for defining a function explicitly such as in "let f ( x ) = sin ⁡ ( x 2 + 1 ) {\displaystyle f(x)=\sin(x^{2}+1)} ". When

8400-432: The arrow notation for functions described above. In some cases the argument of a function may be an ordered pair of elements taken from some set or sets. For example, a function f can be defined as mapping any pair of real numbers ( x , y ) {\displaystyle (x,y)} to the sum of their squares, x 2 + y 2 {\displaystyle x^{2}+y^{2}} . Such

8512-590: The arrow notation. The expression x ↦ f ( x , t 0 ) {\displaystyle x\mapsto f(x,t_{0})} (read: "the map taking x to f of x comma t nought") represents this new function with just one argument, whereas the expression f ( x 0 , t 0 ) refers to the value of the function f at the point ( x 0 , t 0 ) . Index notation may be used instead of functional notation. That is, instead of writing f  ( x ) , one writes f x . {\displaystyle f_{x}.} This

8624-507: The basic concepts of unification and sketched an algorithm in 1930. But most authors attribute the first unification algorithm to John Alan Robinson (cf. box). Robinson's algorithm had worst-case exponential behavior in both time and space. Numerous authors have proposed more efficient unification algorithms. Algorithms with worst-case linear-time behavior were discovered independently by Martelli & Montanari (1976) and Paterson & Wegman (1976) Baader & Snyder (2001) uses

8736-398: The complete set, which may or may not be minimal, although most algorithms avoid redundant unifiers when possible. For first-order syntactical unification, Martelli and Montanari gave an algorithm that reports unsolvability or computes a single unifier that by itself forms a complete and minimal substitution set, called the most general unifier . Syntactic unification of first-order terms

8848-415: The complete substitution set is nonempty) is undecidable. The set S is called minimal if none of its members subsumes another one. Depending on the framework, a complete and minimal substitution set may have zero, one, finitely many, or infinitely many members, or may not exist at all due to an infinite chain of redundant members. Thus, in general, unification algorithms compute a finite approximation of

8960-434: The concept of a relation, but using more notation (including set-builder notation ): A function is formed by three sets, the domain X , {\displaystyle X,} the codomain Y , {\displaystyle Y,} and the graph R {\displaystyle R} that satisfy the three following conditions. Partial functions are defined similarly to ordinary functions, with

9072-476: The domain and some (possibly all) elements of the codomain. Mathematically, a binary relation between two sets X and Y is a subset of the set of all ordered pairs ( x , y ) {\displaystyle (x,y)} such that x ∈ X {\displaystyle x\in X} and y ∈ Y . {\displaystyle y\in Y.} The set of all these pairs

9184-410: The domain of definition of a complex function is illustrated by the multiplicative inverse of the Riemann zeta function : the determination of the domain of definition of the function z ↦ 1 / ζ ( z ) {\displaystyle z\mapsto 1/\zeta (z)} is more or less equivalent to the proof or disproof of one of the major open problems in mathematics,

9296-448: The domain of definition of a multiplicative inverse of a (partial) function amounts to compute the zeros of the function, the values where the function is defined but not its multiplicative inverse. Similarly, a function of a complex variable is generally a partial function with a domain of definition included in the set C {\displaystyle \mathbb {C} } of the complex numbers . The difficulty of determining

9408-453: The empty set appears as the actual G , in which case the actual S is a unifying substitution. Depending on the order the paramodulation rules are applied, on the choice of the actual equation from G , and on the choice of R ' s rules in mutate , different computations paths are possible. Only some lead to a solution, while others end at a G ≠ {} where no further rule is applicable (e.g. G = { f (...) ≐ g (...) }). For an example,

9520-439: The form { x 1 ≐ u 1 , ..., x m ≐ u m } where x 1 , ..., x m are distinct variables and u 1 , ..., u m are terms containing none of the x i . A set of this form can be read as a substitution. If there is no solution the algorithm terminates with ⊥; other authors use "Ω", or " fail " in that case. The operation of substituting all occurrences of variable x in problem G with term t

9632-408: The founders of calculus , Leibniz , Newton and Euler . However, it cannot be formalized , since there is no mathematical definition of an "assignment". It is only at the end of the 19th century that the first formal definition of a function could be provided, in terms of set theory . This set-theoretic definition is based on the fact that a function establishes a relation between the elements of

9744-474: The function f  (⋅) from its value f  ( x ) at x . For example, a ( ⋅ ) 2 {\displaystyle a(\cdot )^{2}} may stand for the function x ↦ a x 2 {\displaystyle x\mapsto ax^{2}} , and ∫ a ( ⋅ ) f ( u ) d u {\textstyle \int _{a}^{\,(\cdot )}f(u)\,du} may stand for

9856-407: The function. If the element y in Y is assigned to x in X by the function f , one says that f maps x to y , and this is commonly written y = f ( x ) . {\displaystyle y=f(x).} In this notation, x is the argument or variable of the function. A specific element x of X is a value of the variable , and the corresponding element of Y

9968-397: The most general unifier ⁠ { z ↦ a , y ↦ a ∗ a , x ↦ ( a ∗ a ) ∗ ( a ∗ a ) , w ↦ ( ( a ∗ a ) ∗ ( a ∗ a ) ) ∗ ( ( a ∗ a ) ∗ (

10080-436: The notation x ↦ f ( x ) , {\displaystyle x\mapsto f(x),} the symbol x does not represent any value; it is simply a placeholder , meaning that, if x is replaced by any value on the left of the arrow, it should be replaced by the same value on the right of the arrow. Therefore, x may be replaced by any symbol, often an interpunct " ⋅ ". This may be useful for distinguishing

10192-654: The number of variables , in which case a separate termination proof becomes unnecessary. In the Prolog syntactical convention a symbol starting with an upper case letter is a variable name; a symbol that starts with a lowercase letter is a function symbol; the comma is used as the logical and operator. For mathematical notation, x,y,z are used as variables, f,g as function symbols, and a,b as constants. Succeeds in traditional Prolog and in Prolog II, unifying x with infinite term x=f(f(f(f(...)))) . The most general unifier of

10304-440: The outermost g and f , respectively, and terms with different outermost function symbols are syntactically different. Symbols are ordered such that variables precede function symbols. Terms are ordered by increasing written length; equally long terms are ordered lexicographically . For a set T of terms, its disagreement path p is the lexicographically least path where two member terms of T differ. Its disagreement set

10416-404: The partial function is a total function . In several areas of mathematics the term "function" refers to partial functions rather than to ordinary functions. This is typically the case when functions may be specified in a way that makes difficult or even impossible to determine their domain. In calculus , a real-valued function of a real variable or real function is a partial function from

10528-417: The problem { x ⊕ a ≐ a } has no solution. For a given unification problem E , a set S of unifiers is called complete if each solution substitution is subsumed by some substitution in S . A complete substitution set always exists (e.g. the set of all solutions), but in some frameworks (such as unrestricted higher-order unification) the problem of determining whether any solution exists (i.e., whether

10640-434: The rewrite rule 2,2, and 1. The equational theory E corresponding to R is the congruence closure of R , both viewed as binary relations on terms. For example, app ( a . b . nil , c . d . nil ) ≡ a . b . c . d . nil ≡ app ( a . b . c . d . nil , nil ). The paramodulation algorithm enumerates solutions to equations with respect to that E when fed with the example R . Function (mathematics) In mathematics ,

10752-428: The same problem are e.g. { x ↦ f ( x 1 ), y ↦ f ( f ( x 1 )), z ↦ f ( x 1 ) }, { x ↦ f ( f ( x 1 )), y ↦ f ( f ( f ( x 1 ))), z ↦ f ( f ( x 1 )) }, and so on; there are infinitely many similar unifiers. As another example, the problem g ( x , x ) ≐ f ( y ) has no solution with respect to ≡ being literal identity, since any substitution applied to the left and right hand side will keep

10864-422: The same syntactical unification problem, then S 1 = { σ 1 } and S 2 = { σ 2 } for some substitutions σ 1 and σ 2 , and xσ 1 is a variant of xσ 2 for each variable x occurring in the problem. For example, the unification problem { x ≐ z , y ≐ f ( x ) } has a unifier { x ↦ z , y ↦ f ( z ) }, because This is also the most general unifier. Other unifiers for

10976-744: The same term [REDACTED] This disambiguation page lists articles associated with the title Narrowing . 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=Narrowing&oldid=1111184557 " Category : Disambiguation pages Hidden categories: Short description matches Wikidata All article disambiguation pages All disambiguation pages Narrowing (computer science) Conventions differ on what values variables may assume and which expressions are considered equivalent. In first-order syntactic unification, variables range over first-order terms and equivalence

11088-420: The second argument [a] will be unified with [Char] . a cannot be both Bool and Char at the same time, therefore this expression is not correctly typed. Like for Prolog, an algorithm for type inference can be given: Unification has been used in different research areas of computational linguistics. Order-sorted logic allows one to assign a sort , or type , to each term, and to declare

11200-408: The set R {\displaystyle \mathbb {R} } of the real numbers to itself. Given a real function f : x ↦ f ( x ) {\displaystyle f:x\mapsto f(x)} its multiplicative inverse x ↦ 1 / f ( x ) {\displaystyle x\mapsto 1/f(x)} is also a real function. The determination of

11312-475: The set T {\displaystyle T} of terms or expressions . Depending on which expressions or terms are allowed to occur in an equation set or unification problem, and which expressions are considered equal, several frameworks of unification are distinguished. If higher-order variables, that is, variables representing functions , are allowed in an expression, the process is called higher-order unification , otherwise first-order unification . If

11424-795: The set of all n -tuples ( x 1 , … , x n ) {\displaystyle (x_{1},\ldots ,x_{n})} such that x 1 ∈ X 1 , … , x n ∈ X n {\displaystyle x_{1}\in X_{1},\ldots ,x_{n}\in X_{n}} is called the Cartesian product of X 1 , … , X n , {\displaystyle X_{1},\ldots ,X_{n},} and denoted X 1 × ⋯ × X n . {\displaystyle X_{1}\times \cdots \times X_{n}.} Therefore,

11536-865: The set of all ordered pairs (2-tuples) of integers, and whose codomain is the set of integers. The same is true for every binary operation . Commonly, an n -tuple is denoted enclosed between parentheses, such as in ( 1 , 2 , … , n ) . {\displaystyle (1,2,\ldots ,n).} When using functional notation , one usually omits the parentheses surrounding tuples, writing f ( x 1 , … , x n ) {\displaystyle f(x_{1},\ldots ,x_{n})} instead of f ( ( x 1 , … , x n ) ) . {\displaystyle f((x_{1},\ldots ,x_{n})).} Given n sets X 1 , … , X n , {\displaystyle X_{1},\ldots ,X_{n},}

11648-594: The study of a problem. For example, the map x ↦ f ( x , t ) {\displaystyle x\mapsto f(x,t)} (see above) would be denoted f t {\displaystyle f_{t}} using index notation, if we define the collection of maps f t {\displaystyle f_{t}} by the formula f t ( x ) = f ( x , t ) {\displaystyle f_{t}(x)=f(x,t)} for all x , t ∈ X {\displaystyle x,t\in X} . In

11760-443: The symbol ↦ {\displaystyle \mapsto } (read ' maps to ') is used to specify where a particular element x in the domain is mapped to by f . This allows the definition of a function without naming. For example, the square function is the function x ↦ x 2 . {\displaystyle x\mapsto x^{2}.} The domain and codomain are not always explicitly given when

11872-447: The symbol denoting the function consists of several characters and no ambiguity may arise, the parentheses of functional notation might be omitted. For example, it is common to write sin x instead of sin( x ) . Functional notation was first used by Leonhard Euler in 1734. Some widely used functions are represented by a symbol consisting of several letters (usually two or three, generally an abbreviation of their name). In this case,

11984-424: The term t {\displaystyle t} by t i {\displaystyle t_{i}} . The result t τ {\displaystyle t\tau } of applying a substitution τ {\displaystyle \tau } to a term t {\displaystyle t} is called an instance of that term t {\displaystyle t} . As

12096-507: The triple ⟨ n v a r , n l h s , n e q n ⟩ {\displaystyle \langle n_{var},n_{lhs},n_{eqn}\rangle } with respect to the lexicographical order , which is possible only a finite number of times. Conor McBride observes that "by expressing the structure which unification exploits" in a dependently typed language such as Epigram , Robinson's unification algorithm can be made recursive on

12208-566: The universal equality " ⁠ u ∗ v = v ∗ u {\displaystyle u*v=v*u} ⁠ for all u , v ". It is said that unification is decidable for a theory, if a unification algorithm has been devised for it that terminates for any input problem. It is said that unification is semi-decidable for a theory, if a unification algorithm has been devised for it that terminates for any solvable input problem, but may keep searching forever for solutions of an unsolvable input problem. Unification

12320-432: The value of the function at a particular value; for example, if f ( x ) = x 2 + 1 , {\displaystyle f(x)=x^{2}+1,} then f ( 4 ) = 4 2 + 1 = 17. {\displaystyle f(4)=4^{2}+1=17.} Given its domain and its codomain, a function is uniquely represented by the set of all pairs ( x , f  ( x )) , called

12432-504: The word mapping for the case where the structure of the codomain belongs explicitly to the definition of the function. Some authors, such as Serge Lang , use "function" only to refer to maps for which the codomain is a subset of the real or complex numbers, and use the term mapping for more general functions. In the theory of dynamical systems , a map denotes an evolution function used to create discrete dynamical systems . See also Poincaré map . Whichever definition of map

12544-415: Was elaborated with the infinitesimal calculus at the end of the 17th century, and, until the 19th century, the functions that were considered were differentiable (that is, they had a high degree of regularity). The concept of a function was formalized at the end of the 19th century in terms of set theory , and this greatly increased the possible applications of the concept. A function is often denoted by

#670329