Strong Normalizability of Typed Lambda-Calculi for Substructural Logics

The strong normalization theorem is uniformly proved for typed λ-calculi for a wide range of substructural logics with or without strong negation. We would like to thank the referees for their valuable comments and suggestions. This research was supported by the Alexander von Humboldt Foundation. The second author is grateful to the Foundation for providing excellent working conditions and generous support of this research. This work was also supported by the Japanese Ministry of Education, Culture, Sports, Science and Technology, Grant-in-Aid for Young Scientists (B) 20700015, 2008.     

Limit Property for Regular and Weak Generalized Convolution

We denote by ? \((\mathcal{P_{+}})\) the set of all probability measures defined on the Borel subsets of the real line (the positive half-line [0,∞)). K. Urbanik defined the generalized convolution as a commutative and associative ?₊-valued binary operation ? on ? ₊ ² which is continuous in each variable separately. This convolution is distributive with respect to convex combinations and scale changes T _a (a>0) with δ ₀ as the unit element. The key axiom of a generalized convolution is the following: there exist norming constants c _n and a measure ν other than δ ₀ such that \(T_{c_{n}}\delta_{1}^{\bullet n}\to\nu\).In Sect. 2 we discuss basic properties of the generalized convolution on ? which hold for the convolutions without the key axiom. This rather technical discussion is important for the weak generalized convolution where the key axiom is not a natural assumption. In Sect. 4 we show that if the weak generalized convolution defined by a weakly stable measure μ has this property, then μ is a factor of strictly stable distribution.     

A Mathematica package for q-holonomic sequences and power series

We describe a Mathematica package for dealing with q-holonomic sequences and power series. The package is intended as a q-analogue of the Maple package gfun and the Mathematica package GeneratingFunctions. It provides commands for addition, multiplication, and substitution of these objects, for converting between various representations (q-differential equations, q-recurrence equations, q-shift equations), for computing sequence terms and power series coefficients, and for guessing recurrence equations given initial terms of a sequence. C. Koutschan partially supported by the Austrian Science Foundation (FWF) grants SFB F1305.     

Perturbation resilience for the facility location problem

We analyze a simple local search heuristic for the facility location problem using the notion of perturbation resilience: an instance is $\gamma$-perturbation resilient if all costs can be perturbed by a factor of $\gamma$ without changing the optimal solution.We prove that local search for FLP succeeds in finding the optimal solution for $\gamma$-perturbation resilient instances for $\gamma \ge 3$, and we show that this is tight.     

Isochronicity at infinity for a class of polynomial differential system

In this paper, we explore the problem of isochronicity at infinity for a class of polynomial differential system. The technique is based on taking infinity into the origin by means of a homeomorphism. Simultaneously, we derive a recursive algorithm to compute period constants at the origin of the transformed system. At the end, as an application of our algorithm, we study pseudo-isochronous center conditions at infinity for a class of septic system.     

Switching Time Optimization for Bang-Bang and Singular Controls

Optimal control problems with the control variable appearing linearly are studied. A method for optimization with respect to the switching times of controls containing both bang-bang and singular arcs is presented. This method is based on the transformation of the control problem into a finite-dimensional optimization problem. Therein, first and second-order optimality conditions are thoroughly discussed. Explicit representations of first and second-order variational derivatives of the state trajectory with respect to the switching times are given. These formulas are used to prove that the second-order sufficient conditions can be verified on the basis of only first-order variational derivatives of the state trajectory. The effectiveness of the proposed method is tested with two numerical examples.     

Martingale Approximation and Optimality of Some Conditions for the Central Limit Theorem

Let (X _i ) be a stationary and ergodic Markov chain with kernel Q and f an L ² function on its state space. If Q is a normal operator and f=(I?Q)^1/2 g (which is equivalent to the convergence of \(\sum_{n=1}^{\infty}\frac{\sum_{k=0}^{n-1}Q^{k}f}{n^{3/2}}\) in L ²), we have the central limit theorem [cf. (Derriennic and Lin in C.R. Acad. Sci. Paris, Sér. I 323:1053–1057, 1996; Gordin and Lif?ic in Third Vilnius conference on probability and statistics, vol. 1, pp. 147–148, 1981)]. Without assuming normality of Q, the CLT is implied by the convergence of \(\sum_{n=1}^{\infty}\frac{\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}}{n^{3/2}}\), in particular by \(\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}=o(\sqrt{n}/\log^{q}n)\), q>1 by Maxwell and Woodroofe (Ann. Probab. 28:713–724, 2000) and Wu and Woodroofe (Ann. Probab. 32:1674–1690, 2004), respectively. We show that if Q is not normal and f∈(I?Q)^1/2 L ², or if the conditions of Maxwell and Woodroofe or of Wu and Woodroofe are weakened to \(\sum_{n=1}^{\infty}c_{n}\frac{\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}}{n^{3/2}}<\infty\) for some sequence c _n ↘0, or by \(\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}=O(\sqrt{n}/\log n)\), the CLT need not hold.     

A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing

The three-dimensional bin packing problem consists of packing a set of boxes into the minimum number of bins. In this paper we propose a new GRASP algorithm for solving three-dimensional bin packing problems which can also be directly applied to the two-dimensional case. The constructive phase is based on a maximal-space heuristic developed for the container loading problem. In the improvement phase, several new moves are designed and combined in a VND structure. The resulting hybrid GRASP/VND algorithm is simple and quite fast and the extensive computational results on test instances from the literature show that the quality of the solutions is equal to or better than that obtained by the best existing heuristic procedures.     

Transient solutions for multi-server queues with finite buffers

Transient solutions for M/M/c queues are important for staffing call centers, police stations, hospitals and similar institutions. In this paper we show how to find transient solutions for M/M/c queues with finite buffers by using eigenvalues and eigenvectors. To find the eigenvalues, we create a system of difference equations where the coefficients depend on a parameter x. These difference equations allow us to search for all eigenvalues by changing x. To facilitate the search, we use Sturm sequences for locating the eigenvalues. We also show that the resulting method is numerically stable.     

Lower Bounds for Dimensions of Sums of Sets

We study lower bounds for the Minkowski and Hausdorff dimensions of the algebraic sum E+K of two sets E,K⊂ℝ ^d .     

Optimal control for quasi-linear systems with small parameters

We consider the controlled systems where the non-linear term is multiplied by a small scalar parameter ε. In the class of these quasi-linear systems, we shall determine the control and optimal trajectory which minimizes the index of performance represented by quadratics functionals. The initial and final conditions are specified and the final time is free. The presence of the small parameter leads to an approximate solution of the formulated problem of optimum. Thus, the zeroth-order solution is obtained for ε=0. The first order solution results by using the sweep method which determines the perturbation of the control and of the state variable on the optimal neighboring trajectory.     

Logarithmic Estimates for Submartingales and Their Differential Subordinates

In the paper we determine, for any K>0 and α∈[0,1], the optimal constant L(K,α)∈(0,∞] for which the following holds: If X is a nonnegative submartingale and Y is α-strongly differentially subordinate to X, then

Existence of a periodic solution for continuous and discrete periodic second-order equations with variable potentials

Green’s functions for new second-order periodic differential and difference equations with variable potentials are found, then used as kernels in integral operators to guarantee the existence of a positive periodic solution to continuous and discrete second-order periodic boundary value problems with periodic coefficient functions. A new version of the Leggett-Williams fixed point theorem is employed.     

On the Existence of Optimal Unions of Subspaces for Data Modeling and Clustering

Given a set of vectors F={f ₁,…,f _m } in a Hilbert space H\mathcal {H}, and given a family C\mathcal {C} of closed subspaces of H\mathcal {H}, the subspace clustering problem consists in finding a union of subspaces in C\mathcal {C} that best approximates (is nearest to) the data F. This problem has applications to and connections with many areas of mathematics, computer science and engineering, such as Generalized Principal Component Analysis (GPCA), learning theory, compressed sensing, and sampling with finite rate of innovation. In this paper, we characterize families of subspaces C\mathcal {C} for which such a best approximation exists. In finite dimensions the characterization is in terms of the convex hull of an augmented set C⁺\mathcal {C}^{+}. In infinite dimensions, however, the characterization is in terms of a new but related notion; that of contact half-spaces. As an application, the existence of best approximations from π(G)-invariant families C\mathcal {C} of unitary representations of Abelian groups is derived.     

Dynamical behavior for an eco-epidemiological model with discrete and distributed delay

In this paper, the dynamical behavior of an eco-epidemiological model with discrete and distributed delay is studied. Sufficient conditions for the local asymptotical stability of the nonnegative equilibria are obtained. We prove that there exists a threshold value of the feedback time delay τ beyond which the positive equilibrium bifurcates towards a periodic solution. Using the normal form theory and center manifold argument, the explicit formulae which determine the stability, the direction and the periodic of bifurcating period solutions are derived. Numerical simulations are carried out to explain the mathematical conclusions.     

New Risk-Averse Control Paradigm for Stochastic Two-Time-Scale Systems and Performance Robustness

This work is concerned with the optimal control of stochastic two-time-scale linear systems with performance measure in a finite-horizon integral-quadratic form. Nature, modeled by stationary Wiener processes whose mean and covariance statistics are known, malevolently affects the state dynamics and output observations of the control problem class. With particular focus on the system performance robustness, the use of higher-order statistics or cumulants associated with the performance measure of chi-squared random variable type makes it possible to restate the stochastic control problem as the solution of a deterministic one, which subsequently allows disregarding all sample-path realizations by Nature acting on the original problem.     

High order local linearization methods: An approach for constructing A-stable explicit schemes for stochastic differential equations with additive noise

An approach for the construction of A-stable high order explicit strong schemes for stochastic differential equations (SDEs) with additive noise is proposed. We prove that such schemes also have the dynamical property that we call Random A-stability (RA-stability), which ensures that, for linear equations with stationary solutions, the numerical scheme has a random attractor that converges to the exact one as the step size decreases. Basically, the proposed integrators are obtained by splitting, at each time step, the solution of the original equation into two parts: the solution of a linear ordinary differential equation plus the solution of an auxiliary SDE. The first one is solved by the Local Linearization scheme in such a way that A-stability is guaranteed, while the second one is approximated by any extant scheme, preferably an explicit one that yields high order of convergence with low computational cost. Numerical integrators constructed in this way are called High Order Local Linearization (HOLL) methods. Various efficient HOLL schemes are elaborated in detail, and their performance is illustrated through computer simulations. Furthermore, mean-square convergence of the introduced methods is studied.     

Decomposition Algorithm Model for Singly Linearly-Constrained Problems Subject to Lower and Upper Bounds

Many real applications can be formulated as nonlinear minimization problems with a single linear equality constraint and box constraints. We are interested in solving problems where the number of variables is so huge that basic operations, such as the evaluation of the objective function or the updating of its gradient, are very time consuming. Thus, for the considered class of problems (including dense quadratic programs), traditional optimization methods cannot be applied directly. In this paper, we define a decomposition algorithm model which employs, at each iteration, a descent search direction selected among a suitable set of sparse feasible directions. The algorithm is characterized by an acceptance rule of the updated point which on the one hand permits to choose the variables to be modified with a certain degree of freedom and on the other hand does not require the exact solution of any subproblem. The global convergence of the algorithm model is proved by assuming that the objective function is continuously differentiable and that the points of the level set have at least one component strictly between the lower and upper bounds. Numerical results on large-scale quadratic problems arising in the training of support vector machines show the effectiveness of an implemented decomposition scheme derived from the general algorithm model.     

Asymptotic behavior for non-oscillatory solutions of difference equations with several delays in the neutral term

In this paper, we first consider difference equations with several delays in the neutral term of the form * $$\Delta\left(y_{n}+\sum_{i=1}^{L}p_{i}y_{n-{k_{i}}}-\sum_{j=1}^{M}r_{j}y_{n-{\rho_{j}}}\right)+q_{n}y_{n-\tau}=0\quad \mbox{for}\ n\in\mathbb{Z}^{+}(0),$$ study various cases of coefficients in the neutral term and obtain the asymptotic behavior for non-oscillatory solution of (*) under some hypotheses. Moreover, we consider reaction-diffusion difference equations with several delays in the neutral term of the form $$\begin{array}{l}\Delta_{1}\left(u_{n,m}+\displaystyle \sum_{i=1}^{L}p_{i}u_{n-{k_{i}},m}-\displaystyle \sum_{j=1}^{M}r_{j}u_{n-{\rho_{j}},m}\right)+q_{n,m}u_{n-\tau,m}\\[18pt]\quad {}=a^{2}\Delta_{2}^{2}u_{n+1,m-1}\end{array}$$ for (n,m)∈?⁺(0)×Ω, study various cases of coefficients in the neutral term and obtain the asymptotic behavior for non-oscillatory solution under some hypotheses.     

A presentation for the singular part of the full transformation semigroup

The (full) transformation semigroup T_n\mathcal{T}_{n} is the semigroup of all functions from the finite set {1,…,n} to itself, under the operation of composition. The symmetric group S_n í T_n{\mathcal{S}_{n}\subseteq \mathcal{T}_{n}} is the group of all permutations on {1,…,n} and is the group of units of T_n\mathcal{T}_{n}. The complement T_n\S_n\mathcal{T}_{n}\setminus \mathcal{S}_{n} is a subsemigroup (indeed an ideal) of T_n\mathcal{T}_{n}. In this article we give a presentation, in terms of generators and relations, for T_n\S_n\mathcal{T}_{n}\setminus \mathcal{S}_{n}, the so-called singular part of T_n\mathcal{T}_{n}.