Characterization of normal forms possessing inverse in the λ-β-η-calculus

The aim of this paper is to generalize a result given by Curry and Feys, who have shown that the only regular combinators possessing inverse in the λ-β-η-calculus are the permutators, whose definition is p=λzλx₁…λx_n(zx_i1…x_in) for n?0 where i₁,…, i_r is a permutation of 1,…, n. Here we extend this characterization to the set of normal forms, showing that the only normal forms possessing inverse in the λ-βη-calculus are the “hereditarily finite permutators” (h.f.p.), whose recursive definition is: if n?0, P_j (1?j?n) are h.f.p. and i₁,…,i_n is a permutation of 1,…, n, then the normal form of P = λzλx₁…λx_n(z(P₁x_i1))… (P_nin) is an h.f.p.     

Why clustering in function approximation? Theoretical explanation

Function approximation is a very important practical problem: in many practical applications, we know the exact form of the functional dependence y=f(x₁,…,x_n) between physical quantities, but this exact dependence is complicated, so we need a lot of computer space to store it, and a lot of time to process it, i.e., to predict y from the given x_i. It is therefore necessary to find a simpler approximate expression g(x₁,…,x_n)≈f(x₁,…,x_n) for this same dependence. This problem has been analyzed in numerical mathematics for several centuries, and it is, therefore, one of the most thoroughly analyzed problems of applied mathematics. There are many results related to approximation by polynomials, trigonometric polynomials, splines of different type, etc. Since this problem has been analyzed for so long, no wonder that for many reasonable formulations of the optimality criteria, the corresponding problems of finding the optimal approximations have already been solved. Lately, however, new clustering‐related techniques have been applied to solve this problem (by Yager, Filev, Chu, and others). At first glance, since for most traditional optimality criteria, optimal approximations are already known, the clustering approach can only lead to non‐optimal approximations, i.e., approximations of inferior quality. We show, however, that there exist new reasonable criteria with respect to which clustering‐based function approximation is indeed the optimal method of function approximation. © 2000 John Wiley & Sons, Inc.     

A General Stochastic Programming Problem

Stochastic programming problems appear when we make decisions in situations with uncertainty and risk, when any action has an ambiguous outcome and to each solution x = (x₁ …, x_n) it is possible to associate certain indicators fⁱ (x, ω), i = 1, …, m, that depend on x and on the state of nature ω, which is an element of the probabilistic space (Ω, A, P).

Since for any x the value of the objective function f ¹ (x, ω) and of the constraints functions f(x, ω), i = 2,… m, will depend on the realization ω, we have great freedom in determining the feasible and the optimal solutions in stochastic programming problems; for example, deciding whether they should be deterministic or have random solutions.     

Interpolazione con splines verificanti una opportuna condizione

Summary A partition of the interval [x ₀,x _n+1] inton+1 subintervals [x _i ,x _i+1] (i=0,1,...,n) is considered. A spline functionf(x)∈C ^m , which coincides with a polynomialp _i (x)[p _i (x _i )=y _i ,p _i (x _i+1)=y _i+1] of degreem+1 in [x _i ,x _i+1 ], is introduced. Such a spline depends onm arbitrary constants. These constants are determined minimizing the integral .      

Adaptive beam search lookahead algorithms for the circular packing problem

This paper addresses the circular packing problem (CPP), which consists in packing n circles C_i, each of known radius r_i, i∈N={1, …, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of the center of C_i, i∈N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ?, ?=1, …, n, of the beam search tree corresponds to a partial packing of ? circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms.     

Interpolation that leads to the narrowest intervals and its application to expert systems and intelligent control

In many real-life situations, we want to reconstruct the dependencyy=f(x ₁,…, x_n) from the known experimental resultsx _i ^(k) , y^(k). In other words, we want tointerpolate the functionf from its known valuesy ^(k)=f(x ₁ ^(k) ,…, x _n ^(k) ) in finitely many points $\bar x^{(k)} = (x_1^{(k)} , \ldots ,x_n^{(k)} )$ , 1≤k≤N There are many functions that go through given points. How to choose one of them? The main goal of findingf is to be able to predicty based onx _i. If we getx _i from measurements, then usually, we only getintervals that containx _i. As a result of applyingf, we get an interval y of possible values ofy. It is reasonable to choosef for which the resulting interval is the narrowest possible. In this paper, we formulate this choice problem in mathematical terms, solve the corresponding problem for several simple cases, and describe the application of these solutions to intelligent control.     

Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

The determinantal complexity of a polynomial f(x ₁,x ₂,…,x _n ) is the minimum m such that f=det  _m (L(x ₁,x ₂,…,x _n )), where L(x ₁,x ₂,…,x _n ) is a matrix whose entries are affine forms in the x _i s over some field $\mbox {$\mbox {.     

Generalized consistency and intensity vectors for comparison matrices

A crucial problem in a decision‐making process is the determination of a scale of relative importance for a set X = {x₁, x₂,..., x_n} of alternatives either with respect to a criterion C or an expert E. A widely used tool in Multicriteria Decision Making is the pairwise comparison matrix A = (a_ij), where a_ij is a positive number expressing how much the alternative x_i is preferred to the alternative x_j. Under a suitable hypothesis of no indifference and transitivity over the matrix A = (a_ij), the actual qualitative ranking on the set X is achievable. Then a vector w may represent the actual ranking at two different levels: as an ordinal evaluation vector, or as an intensity vector encoding information about the intensities of the preferences. In this article we focus on the properties of a pairwise comparison matrix A = (a_ij) linked to the existence of intensity vectors. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 1287–1300, 2007.     

Two theorems concerning recognizable N-subsets of σ1

It is proved that the family of recognizable N-subsets is not closed under the operation sup, and that there exists even a DOL length sequence x₀, x₁, … such that, for any k,x_i ? x_i+1 ? … ? x_i+k holds true for some i and the cardinality of the set {n ∈ N|x_n > x_n+1} is infinite.     

RELION—time-sub-optimal variable structure control law

RELION is an abbreviation for the relay-linear control law. It as a double structure—relay and linear—and it is a modification of the constructive time-sub-optimal control law, u = sgn(p_Mx + sgn(p_M-1 + … + sgn(p₂x + sgnp_ix)…)). For determining the RELION it is necessary to calculate the n-vectors p₁,… p_m and to evaluate the factor K of the linear control law u = K_p1x. Two algorithms for calculating these parameters are presented.     

Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

Disjoint paths in hypercubes with prescribed origins and lengths

Given (i) any k vertices u ₁, u ₂, …, u _k (1≤k<n) in the n-cube Q _n , where (u ₁, u ₂), (u ₃, u ₄), …, (u _2m?1, u _2m ) (m≤? k\2 ?) are edges of the same dimension, (ii) any k positive integers a ₁, a ₂, …, a _k such that a ₁, a ₂, …, a _2m are odd and a _2m+1, …, a _k are even, with a ₁+a ₂+···+a _k =2 ⁿ , and (iii) k subsets W ₁, W ₂, …, W _k of V(Q _n ) with |W _i |≤n?k and if a _i =1, then u _i ¬∈W _i , for 1≤i≤k, we show that there exist k vertex-disjoint paths P ₍₁₎, P ₍₂₎, …, P _(k) in Q _n where P _(i) contains a _i vertices, its origin is u _i , and its terminus is in V(Q _n )/ W _i , for 1≤i≤k. We also prove a similar result which extends two well-known results of Havel, [I. Havel On hamilton circuits and spanning trees of hypercubes, ?asopis pro P?stování Matematiky, 109 (1984), pp. 135–152.] and Nebeský, [L. Nebeský Embedding m-quasistars into n-cubes, Czech. Math. J. 38 (1988), pp. 705–712].     

Transitive Matrices, Strict Preference Order and Ordinal Evaluation Operators

Let X ={x ₁, x ₂, ..., x _n } be a set of alternatives and a _ij a positive number expressing how much the alternative x _i is preferred to the alternative x _j . Under suitable hypothesis of no indifference and transitivity over the pairwise comparison matrix A=(a _ij ), the actual qualitative ranking on the set X is achievable. Then a coherent priority vector is a vector giving a weighted ranking agreeing with the actual ranking and an ordinal evaluation operator is a functional F that, acting on the row vectors , translates A in a coherent priority vector. In this paper we focus our attention on the matrix A, looking for conditions ensuring the existence of coherent priority vectors. Then, given a type of matrices, we look for ordinal evaluation operators, including OWA operators, associated to it.     

Fault diagnosis in loop-connected systems

The paper considers fault diagnosis in a large system comprising a collection of small subsystems or units which can test one another for the existence of a faulty condition. If subsystem α is not faulty and tests subsystem β, a correct indication of the status of β is obtained; if α is faulty, the test outcome contains meaningless information. A particular form of interconnection is examined. For a system with n units u_o,u₁,…,u_{n ? 1}, for each i unit u_i tests u_{i + 1},u_{i + 2},…,u_{i + A} (modulo n arithmetic being understood), where A is a preselected integer. If t is the maximum number of faulty units, we show that when t ? A, all faults are immediately diagnosable if n ? 2t + 1; we also show that when t ? A, at least A faults can be diagnosed if and only if n ? s(t ? As) + t + A + 1, where s is the integer which maximizes the quadratic function f(x) = x(t ? Ax) of the integer variable x.     

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

Fast Algorithm for Computing the Upper Endpoint of Sample Variance for Interval Data: Case of Sufficiently Accurate Measurements

When we have n results x₁,...,x_n of repeated measurement of the same quantity, the traditional statistical approach usually starts with computing their sample average E and their sample variance V. Often, due to the inevitable measurement uncertainty, we do not know the exact values of the quantities, we only know the intervals x_i of possible values of x₁ In such situations, for different possible values x_i∈ x_i, we get different values of the variance. We must therefore find the range V of possible values of V. It is known that in general, this problem is NP-hard. For the case when the measurements are sufficiently accurate (in some precise sense), it is known that we can compute the interval V in quadratic time O(n²). In this paper, we describe a new algorithm for computing V that requires time O(n log(n)) (which is much faster than O(n²)).     

On the time-space tradeoff for sorting with linear queries

Extending a result of Borodin et al. [1], we show that any branching program using linear queries “∑_iλ_ix_i:c” to sort n numbers x₁, x₂,…,x_n must satisfy the time-space tradeoff relation $\text{TS = Ω(n}{}^2\text{)}$. The same relation is also shown to be true for branching programs that uses queries “min R = ?” where R is any subset of {x₁, x₂,…,x_n}.     

Optimizing a damped system – a case study

We consider a second-order damped-vibrational system described by the equation M ?+C(v) [xdot]+K x=0, where M, C(v), K are real, symmetric matrices of order n. We assume that the undamped eigenfrequencies (eigenvalues of (λ² M+K) x=0) ω₁, ω₂, …, ω _n , are multiple in the sense that ω₁=ω₂, ω₃=ω₄, …, ω _n?1=ω _n , or are given in close pairs ω₁ ≈ ω₂, ω₃ ≈ ω₄, …, ω _n?1 ≈ ω _n . We present a formula which gives the solution of the corresponding phase space Lyapunov equation, which then allows us to calculate the first and second derivatives of the trace of the solution, with no extra cost. It can serve for the efficient trace minimization.     

A note on a problem on ω-limit sets of N–dimensional skew-product maps

In 2003, Balibrea et al. stated the problem of finding a skew-product map G on 𝕀³ holding ω _G ={0}×𝕀²=ω _G (x, y, z) for any (x, y, z)∈𝕀³, x≠0. We present a method for constructing skew-product maps F on 𝕀 ⁿ⁺¹ holding ω _F ={0}×𝕀 ⁿ =ω _F (x ₁, x ₂, …, x _n+1), (x ₁, x ₂, …, x _n+1)∈𝕀 ⁿ⁺¹, x ₁≠0.     

An informal introduction to a high level language with applications to interval mathematics

The main problem of interval computations is as follows:given sets of possible valuesX _i for variablesx _i, and an algorithmf:R ⁿ → R, to.estimate the rangef(X ₁, ..,X _n ) of the possible values off(x ₁, ...,x _n ). In many real-life, situations setsX _i are not intervals. To handle such problems, it is desirable to add set data type and operations with sets to a programming language. it is well known that the entire mathematics can be formulated in terms of sets. So, if we already have a set as a data type, why have anything else. The main reason, is that expression in terms of sets is often clumsy. To avoid this clumsiness, it has been suggested to use not only sets, but alsobags (multisets), in which an element can have multiple occurrences. Bags are used in many areas of Computer Science, and recently, several languages have appeared that use the bag as a basic data type. In this paper, we explain the main ideas behind bag languages, and we also show:

· that bag languages are naturally parallelizable, thus leading to a parallelization of the coresponding generalized interval computations;

· and that bag languages can be also helpfully applied to traditional interval computations (where setsX _i are intervals).