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 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.     

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.     

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.     

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.     

Bottleneck flows in unit capacity networks

The bottleneck network flow problem (BNFP) is a generalization of several well-studied bottleneck problems such as the bottleneck transportation problem (BTP), bottleneck assignment problem (BAP), bottleneck path problem (BPP), and so on. The BNFP can easily be solved as a sequence of O(logn) maximum flow problems on almost unit capacity networks. We observe that this algorithm runs in O(min{m3/2,n2/3m}logn) time by showing that the maximum flow problem on an almost unit capacity graph can be solved in O(min{m3/2,n2/3m}) time. We then propose a faster algorithm to solve the unit capacity BNFP in time, an improvement by a factor of at least . For dense graphs, the improvement is by a factor of . On unit capacity simple graphs, we show that BNFP can be solved in time, an improvement by a factor of . As a consequence we have an algorithm for the BTP with unit arc capacities.     

Invariance properties in the root sensitivity of time-delay systems with double imaginary roots

If is an eigenvalue of a time-delay system for the delay τ₀ then is also an eigenvalue for the delays τ_k?τ₀+k2π/ω, for any k∈Z. We investigate the sensitivity, periodicity and invariance properties of the root for the case that is a double eigenvalue for some τ_k. It turns out that under natural conditions (the condition that the root exhibits the completely regular splitting property if the delay is perturbed), the presence of a double imaginary root for some delay τ₀ implies that is a simple root for the other delays τ_k, k≠0. Moreover, we show how to characterize the root locus around . The entire local root locus picture can be completely determined from the square root splitting of the double root. We separate the general picture into two cases depending on the sign of a single scalar constant; the imaginary part of the first coefficient in the square root expansion of the double eigenvalue.     

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.     

Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

The k-ary n-cube, denoted by , is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F be a set of faulty nodes and/or edges, and n?2. We show that when |F|?2n-2, there exists a cycle of any length from 3 to in . We also prove that when |F|?2n-3, there exists a path of any length from 2n-1 to between two arbitrary nodes in . Since the k-ary n-cube is regular of degree 2n, the fault-tolerant degrees 2n-2 and 2n-3 are optimal.     

On the complexity of digraph packings

Let be a fixed collection of digraphs. Given a digraph H, a -packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect -packing, in the case that consists of two graphs one of which is a single edge on two vertices. We characterize -packing where consists of two digraphs one of which is a single arc on two vertices.