Multi-degree reduction of Bézier curves using reparameterization

L₂-norms are often used in the multi-degree reduction problem of Bézier curves or surfaces. Conventional methods on curve cases are to minimize , where and are the given curve and the approximation curve, respectively. A much better solution is to minimize , where is the closest point to point , that produces a similar effect as that of the Hausdorff distance. This paper uses a piecewise linear function L(t) instead of t to approximate the function φ(t) for a constrained multi-degree reduction of Bézier curves. Numerical examples show that this new reparameterization-based method has a much better approximation effect under Hausdorff distance than those of previous methods.     

Nonlinear minimum-time control with pre- and post-actuation

This article studies the time-optimal output transition problem to change the system output, from an initial value (for all time ) to a final value (for all time ), for invertible nonlinear systems. The main contribution of the article is to show that the use of pre- and post-actuation input outside the transition interval I_T=[0,T] can reduce the transition time T beyond the standard bang–bang-type inputs for optimal state transition. The advantage of using pre- and post-actuation is demonstrated with an illustrative nonlinear example.     

Resonance states of Ps using correlated wave functions

We have investigated the resonance states of positronium negative ion below the N=3, 4 and 5 Ps thresholds using highly correlated exponential wave functions. Resonance parameters (positions and widths) are extracted employing both the stabilization method and the complex-coordinate rotation method. In addition to many Feshbach resonances below the various Ps thresholds, we have identified two shape resonances with one each lying above the N=3 and N=5 thresholds, respectively. We have also identified three shape resonances with one lying above the N=3 threshold and two lying above N=4 threshold. The shape resonances associated with N=3 Ps threshold and some other Feshbach resonances are reported for the first time in the literature.     

Periodically switched stability induces exponential stability of discrete-time linear switched systems in the sense of Markovian probabilities

The conjecture that periodically switched stability implies absolute asymptotic stability of random infinite products of a finite set of square matrices, has recently been disproved under the guise of the finiteness conjecture. In this paper, we show that this conjecture holds in terms of Markovian probabilities. More specifically, let S_k∈C^n×n,1≤k≤K, be arbitrarily given K matrices and , where n,K≥2. Then we study the exponential stability of the following discrete-time switched dynamics S: where can be an arbitrary switching sequence.For a probability row-vector and an irreducible Markov transition matrix with , we denote by the Markovian probability on corresponding to . By using symbolic dynamics and ergodic-theoretic approaches, we show that, if S possesses the periodically switched stability then, (i) it is exponentially stable -almost surely; (ii) the set of stable switching sequences has the same Hausdorff dimension as . Thus, the periodically switched stability of a discrete-time linear switched dynamics implies that the system is exponentially stable for “almost” all switching sequences.     

Computing the nearest polynomial with a zero in a given domain by using piecewise rational functions

For a real univariate polynomial f and a closed complex domain D whose boundary C is a simple curve parameterized by a univariate piecewise rational function, a rigorous method is given for finding a real univariate polynomial such that has a zero in D and is minimal. First, it is proved that the minimum distance between f and polynomials having a zero at α∈C is a piecewise rational function of the real and imaginary parts of α. Thus, on C, the minimum distance is a piecewise rational function of a parameter obtained through the parameterization of C. Therefore, can be constructed by using the property that has a zero on C and computing the minimum distance on C. We analyze the asymptotic bit complexity of the method and show that it is of polynomial order in the size of the input.     

From Youla–Kucera to Identification, Adaptive and Nonlinear Control

Some 20 years ago, formulae were presented for the set of all linear time-invariant controllers stabilizing a linear time-invariant plant. This paper traces the development of many ideas from these formulae, covering linear and control, identification, adaptive control and nonlinear systems.     

Pentagons: A weakly relational abstract domain for the efficient validation of array accesses

We introduce Pentagons (), a weakly relational numerical abstract domain useful for the validation of array accesses in byte-code and intermediate languages (IL). This abstract domain captures properties of the form of . It is more precise than the well known Interval domain, but it is less precise than the Octagon domain.The goal of is to be a lightweight numerical domain useful for adaptive static analysis, where is used to quickly prove the safety of most array accesses, restricting the use of more precise (but also more expensive) domains to only a small fraction of the code.We implemented the abstract domain in , a generic abstract interpreter for.NET assemblies. Using it, we were able to validate 83% of array accesses in the core runtime library in a little bit more than 3 minutes.     

On Bézier surfaces in three-dimensional Minkowski space

In this paper, we study Bézier surfaces in three-dimensional Minkowski space. In particular, we focus on timelike and spacelike cases for Bézier surfaces. We also deal with the Plateau–Bézier problem in , obtaining conditions over the control net to be extremal of the Dirichlet function for both timelike and spacelike Bézier surfaces. Moreover, we provide interesting examples showing the behavior of the Plateau–Bézier problem in and illustrating the relationship between it and the corresponding Plateau–Bézier problem in the Euclidean space R³.     

Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions

A k-bounded pseudo-Boolean function is a real-valued function on n{0,1} that can be expressed as a sum of functions depending on at most k input bits. The k-bounded functions play an important role in a number of areas including molecular biology, biophysics, and evolutionary computation. We consider the problem of finding the Fourier coefficients of k-bounded functions, or equivalently, finding the coefficients of multilinear polynomials on n{−1,1} of degree k or less. Given a k-bounded function f with m non-zero Fourier coefficients for constant k, we present a randomized algorithm to find the Fourier coefficients of f with high probability in function evaluations. The best known upper bound was , where λ(n,m) is between and n depending on m. Our bound improves the previous bound by a factor of . It is almost tight with respect to the lower bound . In the process, we also consider the problem of finding k-bounded hypergraphs with a certain type of queries under an oracle with one-sided error. The problem is of self interest and we give an optimal algorithm for the problem.     

Stability of discrete-time systems joined with a saturation operator on the state–space: Generalized form of Liu-Michel’s criterion

A novel criterion for the global asymptotic stability of discrete-time systems in a state–space realization using saturation arithmetic was previously given by Liu and Michel. In their approach, as in most (or probably all) existing approaches, the matrix is assumed to be symmetric. In this communique, it is shown that their approach is such as to be extended to allow the use of an unsymmetric matrix . Taking note of this, a more general form of their criterion is presented. A modified form of the criterion is also presented. Examples show the effectiveness of the generalized approach. To the best of author’s knowledge, this communique is the first report of exploiting an unsymmetric to obtain a stability condition with reduced conservatism.     

On generalized middle-level problem

Let be the subgraph of the hypercube Q_n induced by levels between k and n-k, where n?2k+1 is odd. The well-known middle-level conjecture asserts that is Hamiltonian for all k?1. We study this problem in for fixed k. It is known that and are Hamiltonian for all odd n?3. In this paper we prove that also is Hamiltonian for all odd n?5, and we conjecture that is Hamiltonian for every k?0 and every odd n?2k+1.     

Estimation of Kendall’s tau from censored data

This paper considers the nonparametric estimation of Kendall’s tau for bivariate censored data. Under censoring, there have been some papers discussing the nonparametric estimation of Kendall’s tau, such as Wang and Wells (2000), Oakes (2008) and Lakhal et al. (2009). In this article, we consider an alternative approach to estimate Kendall’s tau. The main idea is to replace a censored event-time by a proper imputation. Thus, it induces three estimators, say , , and . We also apply the bootstrap method to estimate the variance of , and and to construct the corresponding confidence interval. Furthermore, we analyze two data sets by the suggested approach, and compare these practical estimators of Kendall’s tau in simulation studies.     

Convex invariant sets for discrete-time Lur’e systems

In this paper, a method to estimate the domain of attraction of a class of discrete-time Lur’e systems is presented. A new notion of invariance, denoted -invariance, is introduced. An algorithm to determinate the largest -invariant set for this class of systems is proposed. Moreover, it is proven that the -invariant sets provided by this algorithm are polyhedral convex sets and constitute an estimation of the domain of attraction of the non-linear system. It is shown that any contractive set for the Lur’e system is contained in the -invariant set obtained applying the results of this paper. Two illustrative examples are given.     

A class of meromorphic multivalent functions with negative coefficients defined by a differential operator

For 0≤μ≤λ, 0<α≤1, 1/(p+1)<τ≤1, m∈N₀=N∪{0} and p∈N, a new class of meromorphic p-valent functions defined by means of the differential operator is introduced and systematically studied. Membership in this class is characterized through coefficient estimates. Distortion, radii of starlikeness and convexity of order , Hadamard convolution product, an integral operator, convex combinations and neighborhoods are also investigated.     

Learning of event-recording automata

In regular inference, a regular language is inferred from answers to a finite set of membership queries, each of which asks whether the language contains a certain word. One of the most well-known regular inference algorithms is the L^∗ algorithm due to Dana Angluin. However, there are almost no extensions of these algorithms to the setting of timed systems. We extend Angluin’s algorithm for on-line learning of regular languages to the setting of timed systems. Since timed automata can freely use an arbitrary number of clocks, we restrict our attention to systems that can be described by deterministic event-recording automata (DERAs). We present three algorithms, , and , for inference of DERAs. In and , we further restrict event-recording automata to be event-deterministic in the sense that each state has at most one outgoing transition per action; learning such an automaton becomes significantly more tractable. The algorithm builds on , by attempts to construct a smaller (in number of locations) automaton. Finally, is a learning algorithm for a full class of deterministic event-recording automata, which infers a so called simple DERA, which is similar in spirit to the region graph.     

Regularization parameter estimation for large-scale Tikhonov regularization using a priori information

Solutions of numerically ill-posed least squares problems for A∈R^m×n by Tikhonov regularization are considered. For D∈R^p×n, the Tikhonov regularized least squares functional is given by where matrix W is a weighting matrix and is given. Given a priori estimates on the covariance structure of errors in the measurement data , the weighting matrix may be taken as which is the inverse covariance matrix of the mean 0 normally distributed measurement errors in . If in addition is an estimate of the mean value of , and σ is a suitable statistically-chosen value, J evaluated at its minimizer approximately follows a χ² distribution with degrees of freedom. Using the generalized singular value decomposition of the matrix pair , σ can then be found such that the resulting J follows this χ² distribution. But the use of an algorithm which explicitly relies on the direct solution of the problem obtained using the generalized singular value decomposition is not practical for large-scale problems. Instead an approach using the Golub-Kahan iterative bidiagonalization of the regularized problem is presented. The original algorithm is extended for cases in which is not available, but instead a set of measurement data provides an estimate of the mean value of . The sensitivity of the Newton algorithm to the number of steps used in the Golub-Kahan iterative bidiagonalization, and the relation between the size of the projected subproblem and σ are discussed. Experiments presented contrast the efficiency and robustness with other standard methods for finding the regularization parameter for a set of test problems and for the restoration of a relatively large real seismic signal. An application for image deblurring also validates the approach for large-scale problems. It is concluded that the presented approach is robust for both small and large-scale discretely ill-posed least squares problems.     

A compact data structure for representing a dynamic multiset

We develop a data structure for maintaining a dynamic multiset that uses bits and O(1) words, in addition to the space required by the n elements stored, supports searches in worst-case time and updates in amortized time. Compared to earlier data structures, we improve the space requirements from O(n) bits to bits, but the running time of updates is amortized, not worst-case.     

Heavy-baryon spectroscopy from lattice QCD

We use a four-dimensional lattice calculation of the full-QCD (quantum chromodynamics, the non-abelian gauge theory of the strong interactions of quarks and gluons) path integrals needed to determine the masses of the charmed and bottom baryons. In the charm sector, our results are in good agreement with experiment within our systematics, except for the spin-1/2 Ξcc, for which we found the isospin-averaged mass to be Ξcc to be . We predict the mass of the (isospin-averaged) spin-1/2 Ωcc to be . In the bottom sector, our results are also in agreement with experimental observations and other lattice calculations within our statistical and systematic errors. In particular, we find the mass of the Ωb to be consistent with the recent CDF measurement. We also predict the mass for the as yet unobserved to be 5955(27) MeV.     

Acyclic chromatic index of planar graphs with triangles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by , is the least number of colors in an acyclic edge coloring of G. Let G be a planar graph with maximum degree Δ(G). In this paper, we show that , if G contains no 4-cycle; , if G contains no intersecting triangles; and if G contains no adjacent triangles.