Partial-order reduction and trail improvement in directed model checking

In this paper we present work on trail improvement and partial-order reduction in the context of directed explicit-state model checking. Directed explicit-state model checking employs directed heuristic search algorithms such as A* or best-first search to improve the error-detection capabilities of explicit-state model checking. We first present the use of directed explicit-state model checking to improve the length of already established error trails. Second, we show that partial-order reduction, which aims at reducing the size of the state space by exploiting the commutativity of concurrent transitions in asynchronous systems, can coexist well with directed explicit-state model checking. Finally, we illustrate how to mitigate the excessive length of error trails produced by partial-order reduction in explicit-state model checking. In this context we also propose a combination of heuristic search and partial-order reduction to improve the length to already provided counterexamples.     

Partial-order Reduction Techniques for Real-time Model Checking

A new notion, covering, generalising independence is introduced. It enables improved effects of partial-order reduction techniques when applied to real-time systems. Furthermore, we formulate a number of locally checkable conditions for covering that can be used as the basis for a practical algorithm. Correctness is proven with respect to a chosen discretisation method. Received March 1998 / Accepted in revised form October 1998     

Approximation algorithms for general parallel task scheduling

A general parallel task scheduling problem is considered. A task can be processed in parallel on one of several alternative subsets of processors. The processing time of the task depends on the subset of processors assigned to the task. We first show the hardness of approximating the problem for both preemptive and nonpreemptive cases in the general setting. Next we focus on linear array network of m processors. We give an approximation algorithm of ratio O(logm) for nonpreemptive scheduling, and another algorithm of ratio 2 for preemptive scheduling. Finally, we give a nonpreemptive scheduling algorithm of ratio O(log²m) for m×m two-dimensional meshes.     

Efficient parsing algorithms for general context-free parsers

A family of parsing algorithms for general context-free grammars is described. Its members have a top-down structure, while performing tests similar to those introduced in both LR and LL algorithms. A theoretical study shows that the algorithms have the same time and space bounds as Earley's algorithms, which are particular members of the family. Empirical comparisons show the effectiveness of the new members of the family, which appear to be definitely better than Earley's algorithms, except for a few pathological grammars.     

DESH: overhead reduction algorithms for deferrable scheduling

Although the deferrable scheduling algorithm for fixed priority transactions (DS-FP) has been shown to be a very effective approach for minimizing real-time update transaction workload, it suffers from its on-line scheduling overhead. In this work, we propose two extensions of DS-FP to minimize the on-line scheduling overhead. The proposed algorithms produce a hyperperiod from DS-FP so that the schedule generated by repeating the hyperperiod infinitely satisfies the temporal validity constraint of the real-time data. The first algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Construction (DESH-SC), searches the DS-FP schedule for a hyperperiod. The second algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Adjustment (DESH-SA), adjusts the DS-FP schedule in an interval to form a hyperperiod. Our experimental results demonstrate that while both DESH-SC and DESH-SA can reduce the scheduling overhead of DS-FP, DESH-SA outperforms DESH-SC by accommodating significantly more update transactions in the system. Moreover, DESH-SA can also achieve near-optimal update workload.     

Distributed algorithms for reaching consensus on general functions

This paper presents analysis and design results for distributed consensus algorithms in multi-agent networks. We consider continuous consensus functions of the initial state of the network agents. Under mild smoothness assumptions, we obtain necessary and sufficient conditions characterizing any algorithm that asymptotically achieves consensus. This characterization is the building block to obtain various design results for networks with weighted, directed interconnection topologies. We first identify a class of smooth functions for which one can synthesize in a systematic way distributed algorithms that achieve consensus. We apply this result to the family of weighted power mean functions, and characterize the exponential convergence properties of the resulting algorithms. We establish the validity of these results for scenarios with switching interconnection topologies. Finally, we conclude with two discontinuous distributed algorithms that achieve, respectively, max and min consensus in finite time.     

A general methodology for direction-based irregular routing algorithms

This paper presents a general methodology for generating deadlock-free routing algorithms for irregular networks. Constructing a spanning tree on the given network, assigning directions to the network channels, creating deadlock-free zones, and specifying a logical sequence of the produced deadlock-free zones are the four fundamental steps that the proposed methodology takes to generate deadlock-free and connected routing algorithms. By applying the proposed methodology with two known labeling methods we have generated six irregular routing algorithms: three of them are novel routing algorithms and three of them (the Up/Down, Left/Right, and L-turn routing algorithms) have already been proposed in the literature. Extensive simulation experiments have been performed considering various network topologies, different network sizes (considering different network nodes and network channels), various message lengths, a variety of spanning tree roots, and a wide range of message (traffic) generation rates. Simulation results show that the six routing algorithms can be divided into three pairs. Routing members of each pair show similar behavior in terms of message latencies and saturation generation rates. However, it is worth noting that for a given topology the performance of the six routing algorithms may be totally different and it mainly depends on the network topology.     

Dimensionality reduction using genetic algorithms

Pattern recognition generally requires that objects be described in terms of a set of measurable features. The selection and quality of the features representing each pattern affect the success of subsequent classification. Feature extraction is the process of deriving new features from original features to reduce the cost of feature measurement, increase classifier efficiency, and allow higher accuracy. Many feature extraction techniques involve linear transformations of the original pattern vectors to new vectors of lower dimensionality. While this is useful for data visualization and classification efficiency, it does not necessarily reduce the number of features to be measured since each new feature may be a linear combination of all of the features in the original pattern vector. Here, we present a new approach to feature extraction in which feature selection and extraction and classifier training are performed simultaneously using a genetic algorithm. The genetic algorithm optimizes a feature weight vector used to scale the individual features in the original pattern vectors. A masking vector is also employed for simultaneous selection of a feature subset. We employ this technique in combination with the k nearest neighbor classification rule, and compare the results with classical feature selection and extraction techniques, including sequential floating forward feature selection, and linear discriminant analysis. We also present results for the identification of favorable water-binding sites on protein surfaces     

Optimal state reconstruction algorithms for linear discrete-time systems

This paper deals with optimal time-invariant reconstruction of the state of a linear time-invariant discrete-time system from output measurements. The problem is analysed in two settings, depending on whether or not the present output measurement is available for the estimation of the present state. The results prove complete separation of observer and controller design for the optimal dynamic output feedback control with respect to a quadratic cost.     

Heuristic algorithms for the general nonlinear separable knapsack problem

We consider the nonlinear knapsack problem with separable nonconvex functions. Depending on the assumption on the integrality of the variables, this problem can be modeled as a nonlinear programming or as a (mixed) integer nonlinear programming problem. In both cases, this class of problems is very difficult to solve, both from a theoretical and a practical viewpoint. We propose a fast heuristic algorithm, and a local search post-optimization procedure. A series of computational comparisons with a heuristic method for general nonconvex mixed integer nonlinear programming and with global optimization methods shows that the proposed algorithms provide high-quality solutions within very short computing times.     

Online algorithms for the general k-search problem

This paper investigates the general k-search problem, in which a player is to sell totally k units of some asset within n periods, aiming at maximizing the total revenue. At each period, the player observes a quoted price which expires before the next period, and decides irrecoverably the amount of the asset to be sold at the price. We present a deterministic online algorithm and prove it optimal for the case where k?n−1. For the other case where k?n, we show by numerical illustration that the gap between the upper and the lower bound of competitive ratio is quite small for many situations.     

Exponential stability of general tracking algorithms

Tracking and adaptation algorithms are, from a formal point of view, nonlinear systems which depend on stochastic variables in a fairly complicated way. The analysis of such algorithms is thus quite complicated. A first step is to establish the exponential stability of these systems. This is of interest in its own right and a prerequisite for the practical use of the algorithm. It is also a necessary starting point to analyze the performance in terms of tracking and adaptation because that is how close the estimated parameters are to the time-varying true ones. In this paper we establish some general conditions for the exponential stability of a wide and common class of tracking algorithms. This includes least mean squares, recursive least squares, and Kalman filter based adaptation algorithms. We show how stability of an averaged (linear and deterministic) equation and stability of the actual algorithm are linked to each other under weak conditions on the involved stochastic processes. We also give explicit conditions for exponential stability of the most common algorithms. The tracking performance of the algorithms is studied in a companion paper     

Performance analysis of general tracking algorithms

A general family of tracking algorithms for linear regression models is studied. It includes the familiar least mean square gradient approach, recursive least squares, and Kalman filter based estimators. The exact expressions for the quality of the obtained estimates are complicated. Approximate, and easy-to-use, expressions for the covariance matrix of the parameter tracking error are developed. These are applicable over the whole time interval, including the transient, and the approximation error can be explicitly calculated     

Slicing communicating automata specifications: polynomial algorithms for model reduction

In the industry, communicating automata specifications are mainly used in fields where the reliability requirements are high, as this formalism allow the use of powerful validation tools. Still, on large scale industrial specifications, formal methods suffer from the combinatorial explosion phenomenon. In our contribution, we suggest to try to bypass this phenomenon, in applying slicing techniques preliminarily to the targeted complex analysis. This analysis can thus be performed a posteriori on a reduced (or sliced) specification, which is potentially less exposed to combinatorial explosion. The slicing method is based on dependence relations, defined on the specification under analysis, and is mainly founded on the literature on compiler construction and program slicing. A theoretical framework is described, for static analyses of communicating automata specifications. This includes formal definitions for the aforementioned dependence relations, and for a slice of a specification with respect to a slicing criterion. Efficient algorithms are also described in detail, for calculating dependence relations and specification slices. Each of these algorithms has been shown to be polynomial, and sound and complete with respect to its respective definition. These algorithms have also been implemented in a slicing tool, named Carver, that has shown to be operational in specification debugging and understanding. The experimental results obtained in model reduction with this tool are promising, notably in the area of formal validation and verification methods, e.g.model checking, test case generation.     

适合近红外光谱数据特征的降维方法对比分析

因近红外光谱具有波长点多、谱带归属困难、光谱重叠严重及光谱分布结构未知等问题,在进行近红外光谱关键特征提取和数据特征空间映射时难以准确获知合适降维方法。为了解决该问题,本文对比分析了典型线性和非线性降维方法 ,并用烟叶近红外光谱数据从数据降维可视化和分类准确性识别率角度分别进行了实验验证。结果表明,线性降维算法,特别是PCA、LDA算法,比较适合应用于烟叶近红外光谱降维分析中,非线性降维算法因其泛化学习能力与推广能力差以及本征维数估计困难不适合应用于近红外光谱降维分析。     

Suslin’s algorithms for reduction of unimodular rows

A well-known lemma of Suslin says that for a commutative ring $A$ if $(v_1\left(X\right),\dots ,v_n\left(X\right))\in {\left(A\left[X\right]\right)}^n$ is unimodular where $v_1$ is monic and $n\ge 3$, then there exist ${\gamma }_1,\dots ,{\gamma }_{\ell }\in E_{n-1}\left(A\left[X\right]\right)$ such that the ideal generated by $\mathrm{Res}(v_1,e_1.{\gamma }_1{}^t(v_2,\dots ,v_n)),\dots ,\mathrm{Res}(v_1,e_1.{\gamma }_{\ell }{}^t(v_2,\dots ,v_n))$ equals $A$. This lemma played a central role in the resolution of Serre’s Conjecture. In the case where $A$ contains a set $E$ of cardinality greater than $deg{v}_1+1$ such that $y-y^{\prime }$ is invertible for each $y\ne y^{\prime }$ in $E$, we prove that the ${\gamma }_i$ can simply correspond to the elementary operations $L_1\to L_1+y_i{\sum }_{j=2}^{n-1}{u}_{j+1}{L}_j$, $1\le i\le \ell =deg{v}_1+1$, where $u_1{v}_1+\cdots +u_n{v}_n=1$. These efficient elementary operations enable us to give new and simple algorithms for reducing unimodular rows with entries in $K[X_1,\dots ,X_k]$ to ${}^t(1,0,\dots ,0)$ using elementary operations in the case where $K$ is an infinite field. Another feature of this paper is that it shows that the concrete local–global principles can produce competitive complexity bounds.     

A general scheme for token- and tree-based distributed mutualexclusion algorithms

In a distributed context, mutual exclusion algorithms can be divided into two families according to their underlying algorithmic principles: those that are permission-based and those that are token-based. Within the latter family, a lot of algorithms use a rooted tree structure to move the requests and the unique token. This paper presents a very general information structure (and the associated generic algorithm) for token- and tree-based mutual exclusion algorithms. This general structure not only covers, as particular cases, several known algorithms, but also allows for the design of new ones that are well suited for various topology requirements     

A general method for maximizing the error-detecting ability ofdistributed algorithms

The bound on component failures and their spatial distribution govern the fault tolerance of any candidate error-detecting algorithm. For distributed memory multiprocessors, the specific algorithm and the topology of the processor interconnection network define these bounds. This paper introduces the maximal fault index, derived from the system topology and local communication patterns, to demonstrate how a maximal number of simultaneous component failures can be tolerated for a particular interconnection network and error-detecting algorithm. The index is used to design a mapping of processes to processor groups such that the error-detecting ability of the algorithm is preserved for certain multiple simultaneous processor failures     

Specific structures for large-scale state estimation algorithms having information exchange

This paper considers the design and evaluation of large-scale state estimation algorithms having specific structures which allow the subsystems to exchange information over noisy channels. The specific structures which are presented are first motivated by considering the relative performance between the surely locally unbiased filter and a global dynamics filter. The role of the surely locally unbiased filter in evaluating the tradeoffs between the cost of information transfer and filter performance is examined and a theorem is presented which forms the basis for an algorithm for calculating channel noise crossover levels. The theoretical results are illustrated via an application to a power system model.     

Policy iteration type algorithms for recurrent state Markov decision processes

We introduce and analyze several new policy iteration type algorithms for average cost Markov decision processes (MDPs). We limit attention to “recurrent state” processes where there exists a state which is recurrent under all stationary policies, and our analysis applies to finite-state problems with compact constraint sets, continuous transition probability functions, and lower-semicontinuous cost functions. The analysis makes use of an underlying relationship between recurrent state MDPs and the so-called stochastic shortest path problems of Bertsekas and Tsitsiklis (Math. Oper. Res. 16(3) (1991) 580). After extending this relationship, we establish the convergence of the new policy iteration type algorithms either to optimality or to within >0 of the optimal average cost.