Search

Abstract The paper discusses a niche area problem — the design of reduced-order multiple observers which can achieve the finite-time state reconstruction for Takagi–Sugeno multiple models with unknown inputs. The new reduced-order multiple observer obtained in this paper is only the second ever designed, the author of this paper continuing his work started one year ago with the introduction of the reduced-order multiple observer concept. The obtaining of the new reduced-order multiple observer is achieved by combining two classical reduced-order observers for linear time-invariant multivariable systems with unknown inputs and a full-order multiple observer for Takagi–Sugeno systems. The main innovative idea behind the design of the reduced-order multiple observer for Takagi–Sugeno systems described by the multiple models is the split of the multiple model into two subsystems: an unknown-input-free subsystem and an unknown-input-depending subsystem. The unknown-input-free subsystem is brought to the form of a standard multiple model and, in this situation, any algorithm to design full-order multiple observers can be used in the design of reduced-order multiple observers. The steps of the design procedure have been summarized and software implemented; then, the validation of the suggested algorithm has been done for two concrete cases associated to the motion of an aircraft during its landing Highlights • Paper discusses a niche area problem-design of reduced-order multiple observers. • The reduced-order observer designed is only the second one ever obtained. • The steps of the design procedure have been summarized and software implemented. • The observer's performances are compared with the ones of other observers. [ABSTRACT FROM AUTHOR]

Abstract: Neighborhoods and neighborhood sequences play important roles in several branches of pattern analysis. In earlier papers in only certain special (e.g. periodic or octagonal) sequences were investigated. In this paper we study neighborhood sequences which are either ultimately periodic or allow at every neighborhood to do nothing at no cost. We give finite procedures and descriptive theoretical criteria for certain important (e.g. metrical) properties of the sequences. Our results are valid for several types of classical neighborhood sequences and for generated distance functions (e.g. octagonal and chamfer distances) which are widely applied in digital image processing. We conclude the paper by showing how our results contribute to the theory of distance transformations. [Copyright &y& Elsevier]

Abstract: This paper describes a generic software designed to implement meshing algorithms based on the Delaunay refinement paradigm. Such a meshing algorithm is generally described through a set of rules guiding the refinement of mesh elements. The central item of the software design is a generic class, called a mesher level, that is able to handle one of the rules guiding the refinement process. Several instantiations of the mesher level class can be stacked and tied together to implement the whole refinement process. As shown in this paper, the design is flexible enough to implement all currently known mesh generation algorithms based on Delaunay refinement. In particular it can be used to generate meshes approximating smooth or piecewise smooth surfaces, as well as to mesh three dimensional domains bounded by such surfaces. It also adapts to algorithms handling small input angles and various refinement criteria. This design highly simplifies the task of implementing Delaunay refinement meshing algorithms. It has been used to implemented several meshing algorithms in the Cgal library. [Copyright &y& Elsevier]

Abstract: In this paper, we consider completely generalized nonlinear quasi-variational-like inclusions in Banach spaces and propose an Ishikawa type iterative algorithm for computing their approximate solutions by applying the new notion of -proximal mapping given in [R. Ahmad, A.H. Siddiqi, Z. Khan, Proximal point algorithm for generalized multi-valued nonlinear quasi-variational-like inclusions in Banach spaces, Appl. Math. Comput. 163 (2005) 295–308]. We prove that the approximate solutions obtained by the proposed algorithm converge to the exact solution of our quasi-variational-like inclusions. The results presented in this paper extend and improve the corresponding results of [R. Ahmad, A.H. Siddiqi, Z. Khan, Proximal point algorithm for generalized multi-valued nonlinear quasi-variational-like inclusions in Banach spaces, Appl. Math. Comput. 163 (2005) 295–308; X.P. Ding, F.Q. Xia, A new class of completely generalized quasi-variational inclusions in Banach spaces, J. Comput. Appl. Math. 147 (2002) 369–383; N.J. Huang, Generalized nonlinear variational inclusions with non-compact valued mappings, Appl. Math. Lett. 9(3) (1996) 25–29; A. Hassouni, A. Moudafi, A perturbed algorithm for variational inclusions, J. Math. Anal. Appl. 185(3) (1994) 706–712]. Some special cases are also discussed. [Copyright &y& Elsevier]

Abstract: The present paper describes an efficient algorithm to integrate the equations of motion implicitly in the frequency domain. The standard FEM displacement model (Galerkin formulation) is employed to perform space discretization, and the time-marching process is carried out through an algorithm based on the Green’s function of the mechanical system in nodal coordinates. In the present formulation, mechanical system Green’s functions are implicitly calculated in the frequency domain. Once the Green’s functions related matrices are computed, a time integration procedure, which demands low computational effort when applied to non-linear mechanical systems, becomes available. At the end of the paper numerical examples are presented in order to illustrate the accuracy of the present approach. [Copyright &y& Elsevier]

The Small Exponent Test (SET) for exponentiation is an essential batch-verification technique that is widely applied. In this paper, we propose a simplified SET that can securely batch-verify n instances with only n − 1 randomizing exponents. We show that the structure of the proposed batch test is compact in the sense that it works with a minimal number of randomizing exponents for the SET. Thus, our test offers various advantages. Overall, compared to the original SET, the proposed simplified SET is more efficient for any sized batch instance. In particular, unlike the SET, our proposal performs well even when the size of a batch instance is small, e.g., n = 1 , 2 , 3 , and 4. This feature can be also used to significantly reduce pairing computations in a signature scheme where several pairing equations are verified. In addition, our test can be combined easily and generically with existing batch techniques such as the use of sparse exponents, the bucket test for large batch sizes, or an automated tool to generate a batch algorithm. Finally, with our simplified test, an efficient identification algorithm can be constructed to discover incorrect instances in a batch. [ABSTRACT FROM AUTHOR]

We can define the adjacency algebra of an association scheme over an arbitrary field. It is not always semisimple over a field of positive characteristic. The structures of adjacency algebras over a field of positive characteristic have not been sufficiently studied. In this paper, we consider the structures of adjacency algebras of dual polar schemes over a field of positive characteristic and determine them when their algebras are local algebras. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a scheduling problem for automated guided vehicles in container terminals is defined and formulated as a Minimum Cost Flow model. This problem is then solved by a novel algorithm, NSA+, which extended the standard Network Simplex Algorithm (NSA). Like NSA, NSA+ is a complete algorithm, which means that it guarantees optimality of the solution if it finds one within the time available. To complement NSA+, an incomplete algorithm Greedy Vehicle Search (GVS) is designed and implemented. The NSA+ and GVS are compared and contrasted to evaluate their relative strength and weakness. With polynomial time complexity, NSA+ can be used to solve very large problems, as verified in our experiments. Should the problem be too large for NSA+, or the time available for computation is too short (as it would be in dynamic scheduling), GVS complements NSA+. [ABSTRACT FROM AUTHOR]

Abstract: The distributed daemon model introduced by Burns in 1987 is a natural generalization of the central daemon model introduced by Dijkstra in 1974. In this paper, we show that a well-known shortest path algorithm is self-stabilizing under the distributed daemon model. Although this result has been proven only recently, the correctness proof provided here is from a different point of view and is much more concise. We also show that Bruell et al.’s center-finding algorithm is actually self-stabilizing under the distributed daemon model. Finally, we compute the worst-case stabilization times of the two algorithms under the distributed daemon model. [Copyright &y& Elsevier]

Abstract: In this paper, a subspace limited memory BFGS algorithm for solving large-scale bound constrained optimization problems is developed. It is modifications of the subspace limited memory quasi-Newton method proposed by Ni and Yuan [Q. Ni, Y.X. Yuan, A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Math. Comput. 66 (1997) 1509–1520]. An important property of our proposed method is that more limited memory BFGS update is used. Under appropriate conditions, the global convergence of the method is established. The implementations of the method on CUTE test problems are presented, which indicate the modifications are beneficial to the performance of the algorithm. [Copyright &y& Elsevier]

Abstract: Tarski’s fixed point theorem guarantees the existence of a fixed point of an order-preserving function defined on a nonempty complete lattice [B. Knaster, Un théorème sur les fonctions d’ensembles, Annales de la Société Polonaise de Mathématique 6 (1928) 133–134; A. Tarski, A lattice theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics 5 (1955) 285–309]. In this paper, we investigate several algorithmic and complexity-theoretic topics regarding Tarski’s fixed point theorem. In particular, we design an algorithm that finds a fixed point of when it is given as input and as an oracle. Our algorithm makes queries to when is a total order on . We also prove that when both and are given as oracles, any deterministic or randomized algorithm for finding a fixed point of makes an expected queries for some and . [Copyright &y& Elsevier]

Abstract: The aim of this paper is to show how geometric and algebraic approaches lead us to a new symplectic elementary transformations: the 2-D symplectic Householder transformations. Their features are studied in details. Their interesting properties allow us to construct a new algorithm for computing a SR factorization. This algorithm is based only on these 2-D symplectic Householder transformations. Its new features are highlighted. The study shows that, in the symplectic case, the new algorithm is the corresponding one to the classical QR factorization algorithm, via the Householder transformations. Some numerical experiments are given. [Copyright &y& Elsevier]

Abstract: Let be a hereditary abelian -category with tilting object and denote the bounded derived category of . This paper is devoted to a study of suspended subcategories of by means of their Ext-projectives. [Copyright &y& Elsevier]

Abstract: Imposing constraints is a way to incorporate information into the sequence alignment procedure. In this paper, a general model for constrained alignment is proposed so that analyses admitted are more flexible and that different pattern definitions can be treated in a simple unified way. We give a polynomial time algorithm for pairwise constrained alignment for the generalized formulation, and prove the inapproximability of the problem when the number of sequences can be arbitrary. In addition, previous works deal only with the case that the patterns in the constraint have to occur in the output alignment in the same order as that specified by the input. It is of both theoretical and practical interest to investigate the case when the order is no longer limited. We show that the problem is not approximable even when the number of sequences is two. We also give the NPO-completeness results for the problems with bounds imposed on the objective function value. [Copyright &y& Elsevier]

Abstract: Constructing symmetric drawings of graphs is NP-hard. In this paper, we present a new method for drawing graphs symmetrically based on group theory. More formally, we define an -geometric automorphism group as a subgroup of the automorphism group of a graph that can be displayed as symmetries of a drawing of the graph in dimensions. Then we present an algorithm to find all 2- and 3-geometric automorphism groups of a given graph. We implement the algorithm using Magma [http://magma.maths.usyd.edu.au] and the experimental results show that our approach is very efficient in practice. We also present a drawing algorithm to display 2- and 3-geometric automorphism groups. [Copyright &y& Elsevier]

Abstract: The 2-factor index of a graph G, denoted by is the smallest integer m such that the m-iterated line graph of G contains a 2-factor. In this paper, we provide a formula for , and point out that there is a polynomial time algorithm to determine . [Copyright &y& Elsevier]

Abstract: For the earliest arrival flow problem one is given a network with capacities and transit times on its arcs , together with a source and a sink vertex . The objective is to send flow from s to t that moves through the network over time, such that for each time the maximum possible amount of flow up to this time reaches t. If, for each , this flow is a maximum flow for time horizon , then it is called earliest arrival flow. In practical applications a higher congestion of an arc in the network often implies a considerable increase in transit time. Therefore, in this paper we study the earliest arrival problem for the case that the transit time of each arc in the network at each time depends on the flow on this particular arc at that time . For constant transit times it has been shown by Gale that earliest arrival flows exist for any network. We give examples, showing that this is no longer true for flow-dependent transit times. For that reason we define a relaxed version of this problem where the objective is to find flows that are almost earliest arrival flows. In particular, we are interested in flows that, for each , need only -times longer to send the maximum flow to the sink. We give both constant lower and upper bounds on ; furthermore, we present a constant factor approximation algorithm for this problem. [Copyright &y& Elsevier]

Abstract: This work is a continuation of [7]. In that paper, a sufficient condition was given on a real analytic fmlction g defined near 0 in C so that the algebra generated by z 2 and g 2 is dense in the space of continuous functions on D for all disks D close enough to the origin in C. By using the same methods and some ideas taken from the first named author''s thesis we deal with the case where g is only of class C 1 near 0. [Copyright &y& Elsevier]

Abstract: This paper investigates a variant of the general problem of assigning channels to the stations of a wireless network when the graph representing the possible interferences is a matrogenic graph. In our problem, channels assigned to adjacent vertices must be at least 2 apart, while channels assigned to vertices at distance 2 must be different. An exact linear time algorithm is provided for the class of threshold graphs. For matrogenic and matroidal graphs approximate algorithms are given. Consequently, previously known results concerning subclasses of cographs, split graphs and graphs with diameter 2 are improved. [Copyright &y& Elsevier]

Abstract: In this paper we develop a new mathematical approach to the pattern formation problem in biology. This problem was first posed mathematically by A.M. Turing, however some principal questions were left open (for example, whether there exists a “universal” mathematical model that allows one to obtain any spatio-temporal patterns). Here we consider the pattern formation ability of some class of genetic circuits. First, we show that the genetic circuits are capable of generating arbitrary spatio-temporal patterns. Second, we give upper and lower bounds on the number of genes in a circuit generating a given pattern. A connection between the complexity of gene interaction and the pattern complexity is found. We investigate the stochastic stability of patterning algorithms. Results are consistent with experimental data. [Copyright &y& Elsevier]

Abstract: We consider a variant of the classical two median facility location problem on a tree in which vertices are allowed to have positive or negative weights. This problem was proposed by Burkard et al. in 2000 (R.E. Burkard, E. Çela, H. Dollani, 2-medians in trees with pos/neg-weights, Discrete Appl. Math. 105 (2000) 51–71). who looked at two objectives, finding the total minimum weighted distance (MWD) and the total weighted minimum distance (WMD). Their approach finds an optimal solution in time and time, respectively, with better performance for special trees such as paths and stars. We propose here an algorithm for the MWD problem on trees of arbitrary shape. We also briefly discuss the WMD case and argue that it can be solved in time. However, a systematic exposition of the later case cannot be contained in this paper. [Copyright &y& Elsevier]

Abstract: Replication is a key technology of distributed storage systems. In this paper, an indirect replication algorithm is proposed following the intrinsic characteristic of distributed storage systems and the peer-to-peer model. In the indirect replication algorithm, the data object is partitioned into several data blocks. These data blocks are encoded in order that there is data redundancy between data blocks. Comparing with the traditional replication algorithm, the indirect replication algorithm has less granularity of replication, less bandwidth and storage costs, and provides higher availability, durability, and security. The performance evaluation shows that the encoding and decoding times are proportional to the data size, and that the irregular cascade bipartite graphs are of great advantage in improving the success ratio of data recovery. Finally, if the number of data blocks used to recover the data object is larger than a certain value, the success ratio of data recovery approaches 100%. [Copyright &y& Elsevier]

Abstract: The dual Phase-1 algorithm using the most-obtuse-angle row pivot rule is very efficient for providing a dual feasible basis, in either the classical or the basis-deficiency-allowing context. In this paper, we establish a basis-deficiency-allowing Phase-I algorithm using the so-called most-obtuse-angle column pivot rule to produce a primal (deficient or full) basis. Our computational experiments with the smallest test problems from the standard NETLIB set show that a dense projected-gradient implementation largely outperforms that of the variation of the primal simplex method from the commercial code MATLAB LINPROG v1.17, and that a sparse projected-gradient implementation of a normalized revised version of the proposed algorithm runs 34% faster than the sparse implementation of the primal simplex method included in the commercial code TOMLAB LPSOLVE v3.0. [Copyright &y& Elsevier]

Abstract: This paper deals with the prediction of the overall behavior of a class of two-phase elasto-viscoplastic composites, based on mean-field homogenization. For this, important improvements are made to the recently-proposed affine formulation. The latter theory linearizes the rate-dependent inelastic constitutive equations of each phase’s material and transforms them into fictitious linear thermo-elastic relations in the Laplace–Carson domain. The main contributions of the present work are threefold. Firstly, complete mathematical developments including a full treatment of internal variables are carried out, enabling the modeling of the response under unloading and cyclic histories. Secondly, robust and accurate computational algorithms are proposed. Thirdly, an extensive validation of the predictions against reference unit cell finite element results is conducted for a variety of materials and loadings. A good agreement between predictions and reference results is observed. [Copyright &y& Elsevier]

Abstract: Given a set of positive numbers, the max–min partition problem asks for a k-partition such that the minimum part is maximized. The min–ratio partition problem has the similar definition but the objective is to minimize the ratio of the maximum to the minimum parts. In this paper, we analyze the performances of the longest processing time (LPT) algorithm for the two problems. We show that the tight bounds of the LPT are, respectively and . [Copyright &y& Elsevier]

Abstract: In the paper a generalization of the known construction of trivial extension algebras is introduced. For the new constructed algebras one can indicate a construction of their Galois coverings. As an application of these constructions one can obtain a nice Galois coverings for the enveloping algebras of trivial extension algebras of triangular algebras. [Copyright &y& Elsevier]

Abstract: Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. In particular, we consider the class , where for each graph G in , the removal of a set of at most k vertices from G results in a graph in the base graph class . (If is the class of edgeless graphs, is the class of graphs with bounded vertex cover.) When is a minor-closed class such that each graph in has bounded maximum degree, and all obstructions of (minor-minimal graphs outside ) are connected, we obtain an recognition algorithm for , where g and f are constants (modest and quantified) depending on the class . If is the class of graphs with maximum degree bounded by (not closed under minors), we can still obtain a running time of for recognition of graphs in . Our results are obtained by considering bounded-degree minor-closed classes for which all obstructions are connected graphs, and showing that the size of any obstruction for is , where t is a bound on the size of obstructions for . A trivial corollary of this result is an upper bound of on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest. [Copyright &y& Elsevier]

Abstract: We propose a “fast” algorithm for the construction of a data-sparse inverse of a generalToeplitz matrix. The computational cost for inverting an N × N Toeplitz matrix equals the cost of four length-N FFTs plus an O(N)-term. This cost should be compared to the O(N log2 N) cost of previously published methods. Moreover, while those earlier methods are based on algebraic considerations, the procedure of this paper is analysis-based; as a result, its stability does not depend on the symmetry and positive-definiteness of the matrix being inverted. The performance of the scheme is illustrated with numerical examples. [Copyright &y& Elsevier]

Abstract: In a recent paper [Discrete Appl. Math. 130 (2003) 449–467], Yang, Ye, and Zhang investigate the problem of scheduling independent jobs on two identical machines, with a limit on the number of jobs that can be assigned to each single machine, so as to minimize the total weighted completion time of the jobs. They provide a semidefinite programming based, polynomial time approximation algorithm with a worst case ratio of . In this short technical note, we establish the existence of an FPTAS for this problem, and for the corresponding makespan minimization problem. [Copyright &y& Elsevier]

Abstract: In many applications of temporal reasoning we are interested in processing temporal information incrementally. In particular, given a set of temporal constraints (a temporal CSP) and a new constraint, we want to maintain certain properties of the extended temporal CSP (e.g., a solution), rather than recomputing them from scratch. The Point Algebra (PA) and the Interval Algebra (IA) are two well-known frameworks for qualitative temporal reasoning. The reasoning algorithms for PA and the tractable fragments of IA, such as Nebel and Bürckert''s maximal tractable class of relations (ORD-Horn), have originally been designed for “static” reasoning. In this paper, we study the incremental version of the fundamental reasoning problems in the context of these tractable classes. We propose a collection of new polynomial algorithms that can amortize their complexity when processing a sequence of input constraints to incrementally decide satisfiability, to maintain a solution, or to update the minimal representation of the CSP. Our incremental algorithms improve the total time complexity of using existing static techniques by a factor of or , where n is the number of the variables involved by the temporal CSP. An experimental analysis focused on constraints over PA confirms the computational advantage of our incremental approach. [Copyright &y& Elsevier]

Abstract: Let A be an integral k-algebra of finite type over a field k of characteristic zero. Let be a family of k-derivations on A and the A-module spanned by . In this paper, we generalise a result due to Nowicki and construct an element of such that . Such a derivation is called -minimal. Then we establish a density theorem for -minimal derivations in . [Copyright &y& Elsevier]

Abstract: In this paper, we focus our discussion on the parameterization reduction of soft sets and its applications. First we point out that the results of soft set reductions offered in [1] are incorrect. We also observe that the algorithms used to first compute the reduct-soft-set and then to compute the choice value to select the optimal objects for the decision problems in [1] are not reasonable and we illustrate this with an example. Finally, we propose a reasonable definition of parameterization reduction of soft sets and compare it with the concept of attributes reduction in rough sets theory. By using this new definition of parameterization reduction, we improve the application of a soft set in a decision making problem found in [1]. [Copyright &y& Elsevier]

Abstract: We consider the problem of numerical representations of PQI interval orders. A preference structure on a finite set A with three relations standing for “strict preference”, “weak preference” and “indifference”, respectively, is defined as a PQI interval order iff there exists a representation of each element of A by an interval in such a way that, P holds when one interval is completely to the right of the other, I holds when one interval is included to the other and Q holds when one interval is to the right of the other, but they do have a non-empty intersection (Q modelling the hesitation between P and I). Only recently, necessary and sufficient conditions for a PQI preference structure to be identified as a PQI interval order have been established. In this paper, we are interested in the problem of constructing a numerical representation of a PQI interval order and possibly a minimal one. We present two algorithms, the first one in aimed to determine a general numerical representation, and the second one, in , aimed to minimise such a representation. [Copyright &y& Elsevier]

Abstract: In the past, the fuzzy shortest path problem in a network has attracted attention from many researchers for its importance to various applications. In this paper, we propose a new algorithm to deal with the fuzzy shortest path problem. It is composed of fuzzy shortest path length procedure and similarity measure. The former is presented to determine the fuzzy shortest path length from source node to the destination node in the network, and the latter is used to measure the similarity degree between fuzzy length sets. This algorithm not only can yield shortest length but also can offer the actual shortest path to decision makers. An illustrative example is also included to demonstrate our proposed algorithm. [Copyright &y& Elsevier]

Let G=(V,E,w) be an undirected graph with positive edge lengths and S⊂V a set of k specified sources. The k-source maximum eccentricity spanning tree is a spanning tree T minimizing the maximum distance from a source to a vertex, i.e., maxs∈S {maxv∈V{dT(s,v)}}, where dT(s,v) is the length of the path between s and v in T. In this paper, we propose an O(|V|2 log |V|+|V| |E|) time algorithm, which improves the previous result on the problem. [Copyright &y& Elsevier]

In this paper, we present a repair-based linear-time algorithm to solve a version of the Sports League Scheduling Problem (SLSP) where the number T of teams is such that (T-1) mod 3≠0. Starting with a conflicting schedule with particular properties, the algorithm removes iteratively the conflicts by exchanging matches. The properties of the initial schedule make it possible to take the optimal exchange at each iteration, leading to a linear-time algorithm. This algorithm can find thus valid schedules for several thousands of teams in less than 1 min. It is still an open question whether the SLSP can be solved efficiently when (T-1) mod 3=0. [Copyright &y& Elsevier]

We study the following Constrained Bipartite Edge Coloring problem: We are given a bipartite graph G=(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard even for bipartite graphs of maximum degree three. Two special cases of the problem have been previously considered and tight upper and ower bounds on the optimal number of colors were proved. The upper bounds led to 3/2-approximation algorithms for both problems. In this paper we present a randomized (1.37+o(1))-approximation algorithm for the general problem in the case where max{l,c}=ω(ln n). Our techniques are motivated by recent works on the Circular Arc Coloring problem and are essentially different and simpler than the existing ones. [Copyright &y& Elsevier]

In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the maximum number of clauses in time O(1.3247m|F|), where m is the number of clauses in F, and |F| is the sum of the number of literals appearing in each clause in F. Moreover, given a parameter k, we give an O(1.3695k+|F|) parameterized algorithm that decides whether a truth assignment for F satisfying at least k clauses exists. Both algorithms improve the previous best algorithms by Bansal and Raman for the problem. [Copyright &y& Elsevier]

Covering arrays are combinatorial structures which extend the notion of orthogonal arrays and have applications in the realm of software testing. In this paper we raise several new problems motivated by these applications and discuss algorithms for their solution. [Copyright &y& Elsevier]

Abstract: In this paper, some new oscillation criteria are obtained for the first-order delay difference equation , where k,l1,l2,, ls are positive integer numbers, f is a function. Our results improve the known results in the literature. And some examples are given to demonstrate the advantage of our results. [Copyright &y& Elsevier]

Abstract: The scheduling problems studied in this paper concern the two-stage no-wait flowshops with parallel machines under the objective function of the minimization of the maximum completion time. A new heuristic algorithm, i.e., the minimum deviation algorithm, is developed to solve the problems. In order to evaluate the average case performance of the algorithm, we design numerical experiments to compare the effectiveness of the algorithm with that of the other approximation algorithms. Extensive simulations are conducted under different shop conditions, and the results statistically show that the minimum deviation algorithm performs well under most of the situations. [Copyright &y& Elsevier]

Abstract: In [l] and [2], two algorithms have been proposed to calculate the output probability of Boolean functions represented by OBDDs, assuming that the input variables are equiprobable and each variable is statistically independent from others. In this paper, we point out that under these assumptions, the output probability calculation is equivalent to counting the number of minterms of the corresponding Boolean functions. An algorithm is proposed to compute the output probability using simple integer arithmetic as opposed to floating point arithmetic involved in [1,2]. To compute output probability of Boolean functions represented by shared OBDI)s and OBDDs with edge negation, we further propose a generalized algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, we establish some oscillation criteria for the neutral difference equation with positive and negative coefficients without the limitation of condition cn + Σn−1i=n−π + α qi ≤ 1, where cn, pn, and qn are nonnegative integers with τ − 1 ≥ maxσ,γ, γ ≥ 1, σ ≥ 0. [Copyright &y& Elsevier]

Abstract: In this paper, we address the problem of the guaranteed cost stabilization for a class of neutral delay-differential systems with a given quadratic cost function. Based on the Lyapunov method, delay-dependent criteria, which are expressed in terms of matrix inequalities, are proposed to guarantee the asymptotic stability of the system. The matrix inequalities can be easily solved by various efficient optimization algorithms. [Copyright &y& Elsevier]

In the paper, we show a law of the iterated logarithm for rescaled R/S statistics without second moment. [Copyright &y& Elsevier]

Most collision detection algorithms are ones of a discrete type which utilize convexity and local coherence to verify the closest points. However, the incremental algorithms have such critical drawbacks like failure to detect high-speed collisions and dependence on the time complexity on the time step size of animation. In this paper, in order to find a new method which can resolve the drawbacks, we are concerned with a more restricted but nontrivial version of the problem: given a fixed infinite plane H and a moving convex polyhedron P, compute their collision time. Our algorithm utilizes the spherical extreme vertex diagram that is the embedding of the dual graph P onto the Gauss sphere. Exploiting the diagram, we are able to efficiently compute the sequence of the extreme vertices vis, i = 1, …, m and find the time interval [ti, ti+1] during which vi is the extreme vertex of P. With the sequences of the consecutive time intervals and extreme vertices, we construct a distance function between P and H. Hence, we can compute their collision time within a given tolerance by applying the interval Newton method to the distance function. Moreover, the total time complexity is independent of the time step size of animation. [Copyright &y& Elsevier]

Problems associated with finding strings that are within a specified Hamming distance of a given set of strings occur in several disciplines. In this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the COMMON APPROXIMATE SUBSTRING (CAS) problem. Our analyses indicate under which parameter restrictions useful algorithms are possible, and include both class membership and parameterized reductions to prove class hardness. In order to achieve fixed-parameter tractability, either a fixed string length or both a fixed size alphabet and fixed substring length are sufficient. Fixing either the string length or the alphabet size and Hamming distance is shown to be necessary, unless W[1]=FPT. An assortment of parameterized class membership and hardness results cover all other parameterized variants, showing in particular the effect of fixing the number of strings. [Copyright &y& Elsevier]

In this paper, we analyse the stability of parallel algorithms for the evaluation of polynomials written as a finite series of orthogonal polynomials. The basic part of the computation is the solution of a triangular tridiagonal linear system. This fact allows us to present a more detailed analysis. The theoretical results show that the parallel algorithms are almost as stable as their sequential counterparts for practical applications. Extensive numerical experiments confirm the theoretical conclusions. [Copyright &y& Elsevier]