High quantile estimation for heavy-tailed distributions

Different estimators of high quantiles, such as proposed in [N.M. Markovitch, U.R. Krieger, The estimation of heavy-tailed probability density functions, their mixtures and quantiles. Computer Networks 40 (3) (2002) 459–474], Weissman’s estimator and the POT-method are considered. Regarding the estimators and the asymptotic normality of the logarithms of ratios of these estimators to the true value of the quantile is proved. These estimators are applied to real data of Web sessions and pages. Furthermore, bootstrap confidence intervals of and are constructed for modelled data of different heavy-tailed distributions as well as for Web-traffic data.     

Hermite interpolation with simple planar PH curves by speed reparametrization

We introduce a new method of solving C¹ Hermite interpolation problems, which makes it possible to use a wider range of PH curves with potentially better shapes. By characterizing PH curves by roots of their hodographs in the complex representation, we introduce PH curves of type K(t−c)²ⁿ⁺¹+d. Next, we introduce a speed reparametrization. Finally, we show that, for C¹ Hermite data, we can use PH curves of type K(t−c)²ⁿ⁺¹+d or strongly regular PH quintics satisfying the G¹ reduction of C¹ data, and use these curves to solve the original C¹ Hermite interpolation problem.     

Real time identification of discrete event systems using Petri nets

The paper defines the identification problem for Discrete Event Systems (DES) as the problem of inferring a Petri Net () model using the observation of the events and the available output vectors, that correspond to the markings of the measurable places. Two cases are studied considering different levels of the system knowledge. In the first case the place and transition sets are assumed known. Hence, an integer linear programming problem is defined in order to determine a modelling the DES. In the second case the transition and place sets are assumed unknown and only an upper bound of the number of places is given. Hence, the identification problem is solved by an identification algorithm that observes in real time the occurred events and the corresponding output vectors. The integer linear programming problem is defined at each observation so that the can be recursively identified. Some results and examples characterize the identified systems and show the flexibility and simplicity of the proposed technique. Moreover, an application to the synthesis of supervisory control of systems via monitor places is proposed.     

Stability for first order delay dynamic equations on time scales

In this paper, we establish some sufficient conditions for the uniform stability and the uniformly asymptotical stability of the first order delay dynamic equation

where is a time scale, p(.) is rd-continuous and positive, the delay function . Our results unify the corresponding ones for differential and difference equations. To the best of our knowledge, this is the first time to discuss the asymptotical behavior of delay dynamic equations on time scales.     

A new algebra of Toeplitz-plus-Hankel matrices and applications

We introduce a new simultaneously diagonalizable real algebra of symmetrical centrosymmetrical matrices having a Toeplitz-plus-Hankel structure. We give the corresponding orthonormal basis of eigenvectors which are alternately symmetrical and skewsymmetrical vectors. An application is the construction of a symmetrical Toeplitz-plus-centrosymmetrical Hankel matrix of equal row sums having a prescribed real spectrum. This matrix can be used as the starting matrix for symmetrical centrosymmetrical isospectral flows. In particular, for the isospectral flow corresponding to the construction of a regular Toeplitz matrix having prescribed eigenvalues. Moreover, if A is a noise representation of an unknown matrix in of rank k then we give a procedure to approximate A by a matrix in of rank k.     

Squaring the circle: An algorithm for generating polyhedral invariant sets from ellipsoidal ones

This paper presents a new (geometrical) approach to the computation of polyhedral (robustly) positively invariant (PI) sets for general (possibly discontinuous) nonlinear discrete-time systems possibly affected by disturbances. Given a β-contractive ellipsoidal set , the key idea is to construct a polyhedral set that lies between the ellipsoidal sets and . A proof that the resulting polyhedral set is contractive and thus, PI, is given, and a new algorithm is developed to construct the desired polyhedral set. The problem of computing polyhedral invariant sets is formulated as a number of quadratic programming (QP) problems. The number of QP problems is guaranteed to be finite and therefore, the algorithm has finite termination. An important application of the proposed algorithm is the computation of polyhedral terminal constraint sets for model predictive control based on quadratic costs.     

A minimal representation of Markov arrival processes and a moments matching method

The paper investigates the problem of minimal representation of Markov arrival processes of order n (MAP(n)). The minimal representation of MAPs is crucial for developing effective fitting methods. It seems that all existing MAP fitting methods are based on the , representation which is known to be redundant. We present the minimal number of parameters to define a MAP(n) and provide a numerical moments-matching method based on a minimal representation.

The discussion starts with a characterization of phase type (PH) distributions and then the analysis of MAPs follows a similar pattern. This characterization contains essential results on the identity of stationary behaviour of MAPs and on the number of parameters required to describe the stationary behaviour.

The proposed moments matching method is also applicable for PH distributions. In this case it is a unique method that fits a general PH distribution of order n based on 2n−1 parameters.     

Third-order Idealized Algol with iteration is decidable

The problems of contextual equivalence and approximation are studied for the third-order fragment of Idealized Algol with iteration (). They are approached via a combination of game semantics and language theory. It is shown that for each -term one can construct a pushdown automaton recognizing a representation of the strategy induced by the term. The automata have some additional properties ensuring that the associated equivalence and inclusion problems are solvable in Ptime. This gives an Exptime decision procedure for the problems of contextual equivalence and approximation for β-normal terms. Exptime-hardness of the problems, even for terms without iteration, is also shown.     

On the static and dynamic extents of delimited continuations

We show that breadth-first traversal exploits the difference between the static delimited-control operator shift (alias ) and the dynamic delimited-control operator control (alias ). For the last 15 years, this difference has been repeatedly mentioned in the literature but it has only been illustrated with one-line toy examples. Breadth-first traversal fills this vacuum.

We also point out where static delimited continuations naturally give rise to the notion of control stack whereas dynamic delimited continuations can be made to account for a notion of ‘control queue’.     

Robust control of flexible structures with stable bandpass controllers

In this paper, a control law for the active vibration control of mechanical flexible systems is considered. The proposed strategy minimizes an index and results in a stable stabilizing controller with bandpass frequency shape, due to the presence of zeros at the origin. The control authority is thus effective in a chosen band of frequency, resulting in a selective broadband control action, as opposed to narrow-band (tonal) vibration reduction. Moreover, the explicit closed-form solution of the controller is also obtained, thus avoiding numerical calculation of the solution of the Riccati equations, which can be ill-conditioned in the case of very high-order, poorly damped flexible systems. The parametrization of all the controllers is also given and a family of controllers with the above properties is deduced. The case is also obtained as a byproduct. The controller is based on a colocated actuators/sensors pair strategy and numerical simulations are presented, showing the robustness of the proposed approach even for systems with zero damping. Finally, experimental results on a skin panel of a Boeing 717 aircraft also prove the effectiveness of the proposed approach in practical complex applications, with global vibration reduction performances.     

Cycle bases of graphs and sampled manifolds

Point samples of a surface in are the dominant output of a multitude of 3D scanning devices. The usefulness of these devices rests on being able to extract properties of the surface from the sample. We show that, under certain sampling conditions, the minimum cycle basis of a nearest neighbor graph of the sample encodes topological information about the surface and yields bases for the trivial and non-trivial loops of the surface. We validate our results by experiments.     

Hamiltonian-connected graphs

For a simple graph G, let . In this paper, we prove that if NCD(G)≥|V(G)|, then either G is Hamiltonian-connected, or G belongs to a well-characterized class of graphs. The former results by Dirac, Ore and Faudree et al. are extended.     

A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs

Many robust control problems can be formulated in abstract form as convex feasibility programs, where one seeks a solution x that satisfies a set of inequalities of the form . This set typically contains an infinite and uncountable number of inequalities, and it has been proved that the related robust feasibility problem is numerically hard to solve in general.

In this paper, we discuss a family of cutting plane methods that solve efficiently a probabilistically relaxed version of the problem. Specifically, under suitable hypotheses, we show that an Analytic Center Cutting Plane scheme based on a probabilistic oracle returns in a finite and pre-specified number of iterations a solution x which is feasible for most of the members of , except possibly for a subset having arbitrarily small probability measure.     

Branching blend of natural quadrics based on surfaces with rational offsets

A new branching blend between two natural quadrics (circular cylinders/cones or spheres) in many positions is proposed. The blend is a ring shaped patch of a PN surface (surface with rational offset) parametrized by rational bivariant functions of degree (6,3). The general theory of PN surfaces is developed using Laguerre geometry and a universal rational parametrization of the Blaschke cylinder. The construction is extended via inversion to a PN branching blend of degree (8,4) between Dupin cyclide and a natural quadric.     

Reconstruction of convergent smooth B-spline surfaces

Recently, there have been improvements on reconstruction of smooth B-spline surfaces of arbitrary topological type, but the most important problem of smoothly stitching B-spline surface patches (the continuity problem of B-spline surface patches) in surface reconstruction has not been solved in an effective way. Therefore, the motivation of this paper is to study how to better improve and control the continuity between adjacent B-spline surfaces.

In this paper, we present a local scheme of constructing convergent G¹ smooth bicubic B-spline surface patches with single interior knots over a given arbitrary quad partition of a polygonal model. Unlike previous work which only produces (non-controllable) toleranced G¹ smooth B-spline surfaces, our algorithm generates convergent G¹ smooth B-spline surfaces, which means the continuity of the B-spline surfaces tends to G¹ smoothness as the number of control points increases. The most important feature of our algorithm is, in the meaning of convergent approximation order, the ability to control the continuity of B-spline surfaces within the given tolerance and capture the geometric details presented by the given data points.     

A parallel method for large sparse generalized eigenvalue problems using a GridRPC system

In this paper we present a master–worker type parallel method for finding several eigenvalues and eigenvectors of a generalized eigenvalue problem , where A and B are large sparse matrices. A moment-based method that finds all of the eigenvalues that lie inside a given domain is used. In this method, a small matrix pencil that has only the desired eigenvalues is derived by solving large sparse systems of linear equations constructed from A and B. Since these equations can be solved independently, we solve them on remote servers in parallel. This approach is suitable for master–worker programming models. We have implemented and tested the proposed method in a grid environment using a grid RPC (remote procedure call) system called OmniRPC. The performance of the method on PC clusters that were used over a wide-area network was evaluated.     

An approximate algorithm for top-k closest pairs join query in large high dimensional data

In this paper we present a novel approximate algorithm to calculate the top-k closest pairs join query of two large and high dimensional data sets. The algorithm has worst case time complexity and space complexity and guarantees a solution within a factor of the exact one, where t  {1, 2, … , ∞} denotes the Minkowski metrics L_t of interest and d the dimensionality. It makes use of the concept of space filling curve to establish an order between the points of the space and performs at most d + 1 sorts and scans of the two data sets. During a scan, each point from one data set is compared with its closest points, according to the space filling curve order, in the other data set and points whose contribution to the solution has already been analyzed are detected and eliminated. Experimental results on real and synthetic data sets show that our algorithm behaves as an exact algorithm in low dimensional spaces; it is able to prune the entire (or a considerable fraction of the) data set even for high dimensions if certain separation conditions are satisfied; in any case it returns a solution within a small error to the exact one.