Partial-order reduction for parity games and parameterised Boolean equation systems

In model checking, reduction techniques can be helpful tools to fight the state-space explosion problem. Partial-order reduction (POR) is a well-known example, and many POR variants have been developed over the years. However, none of these can be used in the context of model checking stutter-sensitive temporal properties. We propose POR techniques for parity games, a well-established formalism for solving a variety of decision problems, including model checking. As a result, we obtain the first POR method that is sound for the full modal \(\upmu \)-calculus. We show how our technique can be applied to the fixed point logic called parameterised Boolean equation systems, which provides a high-level representation of parity games. Experiments with our implementation indicate that substantial reductions can be achieved.

     

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.     

关系决策系统的分布约简

基于分辨矩阵和最近已提出的快速算法,对关系系统的约简算法和关系决策系统的分布约简算法进行了研究。证明当决策属性具有自反性时,关系决策系统的分布约简实际上就是关系系统的约简,与决策属性无关。此外,区间值模糊序关系决策系统可视为关系决策系统的一个特例,用提出的关系决策系统的分布约简算法即可获得区间值模糊序关系决策系统的全部约简结果,从而简化了原来的约简算法。     

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.     

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.     

一种决策表增量属性约简算法

为了对动态变化的决策表进行属性约简处理,在改进的分辨矩阵的基础上,提出一种增量式属性约简算法,当决策表添加新的记录后．能快速得到新决策表的所有约简和最小约筒．此外,通过对不相容决策表的正区域的决策值和边界域对原决策表进行分解．得到了一种分布式增量属性约简模型．仿真研究表明了算法的正确性和高效性．     

Parallel algorithms for model reduction of discrete-time systems

Computing reduced-order models of controlled dynamical systems is of fundamental importance in many analysis and synthesis problems in systems and control theory. Algorithmic aspects of model reduction methods based on state-space truncation for linear discrete-time systems are addressed here. In contrast to the often-used approach of applying methods for continuous-time systems to discrete-time models employing a bilinear transformation, we devise special algorithms for discrete-time systems. Usually, this is more reliable and efficient. All methods discussed require in an initial stage the computation of the Gramians of the system. Using an accelerated fixed-point iteration for computing the full-rank factors of the Gramians yields some favorable computational aspects, particularly for non-minimal systems. The computations only require efficient implementations of basic linear algebra operations readily available on modern computer architectures. We discuss aspects of the parallel implementation of these methods and show the performance and scalability on distributed memory computers. Our approach enables users to deal with very complex systems using relatively cheap infrastructure, as, for example, a local PC or workstation network.     

基于分辨矩阵和约简树的增量式属性约简算法

为了对动态变化的决策表进行高效属性约简处理,在改进的分辨矩阵的基础上提出一种基于约简树的增量式属性约简算法IRART,该算法首先根据序贯属性约简算法对原决策表构造约简树,然后求出新增对象的分辨向量,并利用此向量对约简树进行修整,从而快速得到新决策表的所有约简,最后通过示例证明了这种算法的有效性。与传统增量式属性约简算法相比,该算法避免了复杂的逻辑演算,提高了属性约简的更新效率,理论分析表明该算法是有效可行的。     

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.     

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.     

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.     

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     

通用进化算法的收敛性分析

传统进化算法的收敛性专注于具体算法,对应的研究成果也仅仅适用于具体算法。为了研究所有进化算法的收敛性问题,提出了一种包含所有操作类型算子的通用进化算法,建立了一套概率空间用于研究算法的收敛性,所有有关算法的术语都用严格的数学语言加以定义。在概率空间中,有七个算法收敛性定理被完整地证明,其中之一找到了算法依概率收敛的充分必要条件。更为重要的是,这些定理适用所有进化算法。它建立了一个体系,用来指导进化算法的设计,从理论上判断进化算法的收敛性。     

Parallel vector reduction algorithms and architectures

Vector operations are important in many computer applications. They often represent the main part of operations of the entire problem and consume a great amount of computing time. So, it is natural to apply parallel computation to vector operations in order to increase the speed of solving a problem. Among vector operations, vector reduction is a known and common type of operation (e.g., vector summation, inner product evaluation). In this paper vector reduction techniques for parallel pipelined processing are discussed. The computation and communication properties and constraints of both single and multiple vector reductions in a multipipeline environment are considered. From this a simple, yet efficient “partitioned linear pipeline array” (PLPA) architecture is proposed and the performance of a number of scheduling algorithms related to this architecture is determined. The performance comparison between the proposed approach and the well-known tree-structured reduction processor is given. From the results of performance analysis, it is shown that the PLPA approach has approximately the same performance as a pipelined binary reduction tree. However, the PLPA approach is much simpler and easier to implement, and is also more flexible than a tree-structured reduction processor. Finally, as an example, the matrix multiplication operation on a PLPA is considered. It is shown that with the PLPA architecture a very good performance can be obtained.