Search

In this paper, we consider the homogeneous m -machine scheduling problem where unit-time jobs have to be scheduled within their time windows so that, for any subset of machines, the set of the time units at which at least one machine is busy, is an interval. For this problem, a time assignment of the jobs satisfying the time windows constraints is a schedule if it has a pyramidal profile and is a k -schedule if this profile property is satisfied up to level k only. We develop a generic algorithm to solve the problem and show it is correct using a proof that mainly relies on a necessary and sufficient condition for a schedule to exist proved in a previous paper. We finally show that the generic algorithm is polynomial. We conclude by giving the directions of ongoing works and by bringing open questions related to different variants of the basic non-idling m -machine scheduling problem. [ABSTRACT FROM AUTHOR]

Abstract The sensitivity conjecture proposed by Nisan and Szegedy in 1994, which asserts that for any Boolean function, its sensitivity complexity is polynomially related to the block sensitivity complexity, is one of the most important and challenging problems in the study of decision tree complexity. Despite a lot of efforts, the best known upper bound of block sensitivity, as well as the certificate complexity, is still exponential in terms of sensitivity. In this paper, we give a better upper bound for certificate complexity and block sensitivity, b s (f) ≤ C (f) ≤ (8 9 + o (1)) s (f) 2 s (f) − 1 , where b s (f) , C (f) and s (f) are the block sensitivity, certificate complexity and sensitivity, respectively. The proof is based on a deep investigation on the structure of the sensitivity graph. We also provide a tighter relationship between the 0-certificate complexity C 0 (f) and 0-sensitivity s 0 (f) for functions with small 1-sensitivity s 1 (f). [ABSTRACT FROM AUTHOR]

Abstract In the current paper, an error estimate has been proposed to find a second-order finite difference scheme for solving the Riesz space distributed-order diffusion equation. The convergence order of the proposed method is O (τ 2 + h 2). The numerical results show the efficiency of the new technique. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we defined the scattering energy intensity based on the Poynting vector to quantitatively study the cloak effect of electromagnetic waves in the time domain. The influences of the effective working frequency bands of four kinds of electromagnetic cloak materials, incidence angle of electromagnetic waves and the number of approximately cloak layers on the cloak effect are studied. To the best of our knowledge, this is the first time to use the time domain method to quantitatively study the effective working frequency band and the scattering energy intensity of cloak materials. [ABSTRACT FROM AUTHOR]

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ -LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ -LFSRs. The search algorithm first constructs the σ -polynomial and then checks the primitiveness of the σ -polynomial, whereas the construction algorithm for the σ -LFSR, first finds a primitive polynomial f ( x ) and then constructs the primitive σ -LFSR from f ( x ) . In this paper, we present some novel results pertaining to the search algorithm for primitive σ -LFSR along with the exhaustive search space complexity of the search algorithm for σ -LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ -LFSR. Finally, the number of σ -LFSRs similar to the σ -LFSRs generated by the construction algorithm is provided. [ABSTRACT FROM AUTHOR]

In Gordon (1998), Gordon presented alternate proofs of several well known results in elementary real analysis using tagged partitions. In this paper, we provide a set of alternative proofs based on the dyadic partitions. An important difference between tagged and dyadic partitions is that the results based on the dyadic partition can be obtained constructively, i.e. an algorithm is supplied to reach the conclusion of each proof. In addition, the construction involves only concepts and results presented in a first course real analysis, which is the reason why, comparing tagged partition and its theory, the proofs based on dyadic partition are more straightforward and accessible to a wide range of audience. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in general position in the plane which is partitioned into color classes. The set P is said to be color-balanced if the number of points of each color is at most [n/2] . Given a color-balanced point set P, a balanced cut is a line which partitions P into two color-balanced point sets, each of size at most 2n/3+1 . A colored matching of P is a perfect matching in which every edge connects two points of distinct colors by a straight line segment. A plane colored matching is a colored matching which is non-crossing. In this paper, we present an algorithm which computes a balanced cut for P in linear time. Consequently, we present an algorithm which computes a plane colored matching of P optimally in Θ(nlog n) time. [ABSTRACT FROM AUTHOR]

Successful classification of questioned footwear has tremendous evidentiary value; the result can minimize the potential suspect pool and link a suspect to a victim, a crime scene, or even multiple crime scenes to each other. With this in mind, several different automated and semi-automated classification models have been applied to the forensic footwear recognition problem, with superior performance commonly associated with two different approaches: correlation of image power (magnitude) or phase, and the use of local interest points transformed using the Scale Invariant Feature Transform (SIFT) and compared using Random Sample Consensus (RANSAC). Despite the distinction associated with each of these methods, all three have not been cross-compared using a single dataset, of limited quality (i.e., characteristic of crime scene-like imagery), and created using a wide combination of image inputs. To address this question, the research presented here examines the classification performance of the Fourier-Mellin transform (FMT), phase-only correlation (POC), and local interest points (transformed using SIFT and compared using RANSAC), as a function of inputs that include mixed media (blood and dust), transfer mechanisms (gel lifters), enhancement techniques (digital and chemical) and variations in print substrate (ceramic tiles, vinyl tiles and paper). Results indicate that POC outperforms both FMT and SIFT+RANSAC, regardless of image input (type, quality and totality), and that the difference in stochastic dominance detected for POC is significant across all image comparison scenarios evaluated in this study. [ABSTRACT FROM AUTHOR]

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]

Hydraulic fracturing of rocks has various engineering applications. However, there has been limited research into crack propagation prediction by three dimensional analytical techniques. This paper discusses such a technique for predicting the propagation surface of a pressurized circular crack subjected to various loading conditions. The propagation surfaces predicted from the proposed crack front propagation algorithm align well with published results. The suggested method consumes only a fraction of the time needed for a numerical simulation, and therefore it could be useful in assisting the design of hydraulic fracturing operations. [ABSTRACT FROM AUTHOR]

Abstract: With a transformation matrix of B-spline bases (abbreviated to BSBT matrix), a B-spline basis can be represented by another B-spline basis. In this paper, we first give the existence conditions and some useful properties of BSBT matrices. Then we propose a recursive formula for BSBT matrices and an efficient method for the computation of BSBT matrices. Based on these results, we further probe into the applications of BSBT matrices in knot insertion and degree elevation of B-spline curves. Using BSBT matrices, we develop a new uniform algorithm for knot insertion and degree elevation of B-spline curves. This algorithm is efficient, general-purpose, and simple to implement. It can be used to insert one knot or multiple knots, raise one degree or multiple degrees, or to insert knot and raise degree simultaneously. Several examples are given to illustrate the stability of the algorithm. The results in the paper show that BSBT matrices can be applied to establish a uniform mathematical model for knot insertion, degree elevation, knot removal and degree reduction of B-spline curves and surfaces, and to provide a general tool for the conversions between different representations of B-spline curves and surfaces. [Copyright &y& Elsevier]

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]

Radial basis functions are a popular basis for interpolating scattered data during the image reconstruction process in graphic analysis. In this context, the solution of a linear system of equations represents the most time-consuming operation. In this paper an efficient preconditioning technique is proposed to solve these linear systems of equations. This algorithm consists of an iterative method which enforces at each iteration a projection of the residual onto a suitable subspace called coarse space. This constraint is ensured by solving an auxiliary problem at each iteration without regularisation. As increasing the number of the coarse space basis functions increases the computational cost of the algorithm, correct selection of coarse space basis is addressed in the paper. Numerical results illustrate the convergence properties of the proposed method with wavelet-like basis functions and regular distributed radial basis functions for image reconstruction. [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: In this paper we consider the Nonnegative Matrix Factorization (NMF) problem: given an (elementwise) nonnegative matrix find, for assigned k, nonnegative matrices and such that V = WH. Exact, nontrivial, nonnegative factorizations do not always exist, hence it is interesting to pose the approximate NMF problem. The criterion which is commonly employed is I-divergence between nonnegative matrices. The problem becomes that of finding, for assigned k, the factorization WH closest to V in I-divergence. An iterative algorithm, EM like, for the construction of the best pair (W, H) has been proposed in the literature. In this paper we interpret the algorithm as an alternating minimization procedure à la Csiszár–Tusnády and investigate some of its stability properties. NMF is widespreading as a data analysis method in applications for which the positivity constraint is relevant. There are other data analysis methods which impose some form of nonnegativity: we discuss here the connections between NMF and Archetypal Analysis. [Copyright &y& Elsevier]

Abstract: This paper presents results of research into the use of the Bellman-Zadeh approach to decision making in a fuzzy environment for solving multiobjective optimization problems. Its application conforms to the principle of guaranteed result and provides constructive lines in obtaining harmonious solutions on the basis of analyzing associated maxmin problems. The use of the Bellman-Zadeh approach has served as a basis for solving a problem of multiobjective allocation of resources (or their shortages) and developing a corresponding adaptive interactive decision-making system (AIDMS1). Its calculating kernel permits one to solve maxmin problems using an algorithm based on a nonlocal search (modification of the Gelfand''s and Tsetlin''s “long valley” method). The AIDMS1 includes procedures for considering linguistic variables to reflect conditions that are difficult to formalize as well as procedures for constructing and correcting vectors of importance factors for goals. The use of these procedures permits one to realize an adaptive approach to processing information of a decision maker to provide successive improving of the solution quality. C++ windows of the AIDMS1 are presented for input, output, and special possibilities related to considering linguistic variables and constructing and correcting vectors of importance factors. The results of the paper are universally applicable and are already being used to solve power engineering problems. [Copyright &y& Elsevier]

Abstract: In a finite dataset consisting of positive and negative observations represented as real valued -vectors, a positive (negative) pattern is an interval in with the property that it contains sufficiently many positive (negative) observations, and sufficiently few negative (positive) ones. A pattern is spanned if it does not include properly any other interval containing the same set of observations. Although large collections of spanned patterns can provide highly accurate classification models within the framework of the Logical Analysis of Data, no efficient method for their generation is currently known. We propose in this paper, an incrementally polynomial time algorithm for the generation of all spanned patterns in a dataset, which runs in linear time in the output; the algorithm resembles closely the Blake and Quine consensus method for finding the prime implicants of Boolean functions. The efficiency of the proposed algorithm is tested on various publicly available datasets. In the last part of the paper, we present the results of a series of computational experiments which show the high degree of robustness of spanned patterns. [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]

Abstract: The goal of this paper is to prove that the implementation of Taylor models in COSY, based on floating-point arithmetic, computes results satisfying the “containment property”, i.e. guaranteed results. First, Taylor models are defined and their implementation in the COSY software by Makino and Berz is detailed. Afterwards IEEE-754 floating-point arithmetic is introduced. Then the core of this paper is given: the algorithms implemented in COSY for multiplying a Taylor model by a scalar, for adding or multiplying two Taylor models are given and are proven to return Taylor models satisfying the containment property. [Copyright &y& Elsevier]

Abstract: In this paper, we present a comprehensive method consisting of efficient state minimization and a comprehensive method of state assignment techniques to synthesize finite state machines (FSMs) to optimize power, area, and delay for “next-state” logic network design. The goal is to reduce the number of gates and literals relevant to power and area, and simultaneously to shorten the critical-path delay in FSM optimization. In the first step, we try to reduce the complexity of state minimization by applying (i) compatible graph to target one of optimal solutions in efficiency, (ii) conflict graph to determine the lower bound of the number of states and possible optimal solutions, (iii) Boolean expression effects due to alternative ways of minimized states, such that the required number of flip–flops is minimum for completely (or incompletely) specified FSMs. Next, a comprehensive method of state assignment techniques consisting of (i) edge-covering algorithm, (ii) block-reordering algorithm, (iii) cost calculation, (iv) ping-pong Gray-codes assignment, and (iv) design space exploration, is developed to choose the best state assignment. Finally, Espresso is run to determine the Boolean expressions and choose the best state assignment with the minimal sum-of-product (SOP) terms and literals from those optimal solutions. At last, the performance metrics in power, area, and delay are calculated based on the developed cell libraries for those optimal solutions with same minimized terms and literals. Our solutions provide engineers and designers to choose the best state assignment having less power, area, and delay to meet their system specification. Again this paper provides a comprehensive method of FSM synthesis and optimization for large FSMs in terms of power, area, and delay. Our experiments show that the derived optimal state assignment results in less power, area, and delay in FSM MCNC benchmarks. [Copyright &y& Elsevier]

Isometric subgraphs of hypercubes, or partial cubes as they are also called, are a rich class of graphs that include median graphs, subdivision graphs of complete graphs, and classes of graphs arising in mathematical chemistry and biology. In general, one can recognize whether a graph on n vertices and m edges is a partial cube in O(mn) steps, faster recognition algorithms are only known for median graphs. This paper exhibits classes of partial cubes that are not median graphs but can be recognized in O(m log n) steps. On the way relevant decomposition theorems for partial cubes are derived, one of them correcting an error in a previous paper (Eur. J. Combin. 19 (1998) 677). [Copyright &y& Elsevier]

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: A finite Sturmian word is a balanced word over the binary alphabet , that is, for all subwords and of of equal length, , where and denote the number of occurrences of the letter in and , respectively. There are several other characterizations, some leading to efficient algorithms for testing whether a finite word is Sturmian. These algorithms find important applications in areas such as pattern recognition, image processing, and computer graphics. Recently, Blanchet-Sadri and Lensmire considered finite semi-Sturmian words of minimal length and provided an algorithm for generating all of them using techniques from graph theory. In this paper, we exploit their approach in order to count the number of minimal semi-Sturmian words. We also present some other results that come from applying this graph theoretical framework to subword complexity. [Copyright &y& Elsevier]

Abstract: A sigraph is a graph in which each edge carries a value called its sign, denoted specially as . Given a sigraph , a new sigraph , called the common-edge sigraph of is that sigraph whose vertex-set is the set of pairs of adjacent edges in and two vertices of are adjacent if the corresponding pairs of adjacent edges of have exactly one edge in common, and the sign of the edge is the sign of the common edge. If all the edges of the sigraph carry + sign then is actually a graph and the corresponding common-edge sigraph is termed as the common-edge graph. In this paper, we characterize common-edge graph and common-edge sigraph and write an algorithm to obtain a corresponding common-edge root graph and common-edge root sigraph from a given common-edge graph and common-edge sigraph respectively. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the uniqueness of meromorphic functions in the unit disc that share five distinct meromorphic functions of slow growth in an angular domain. [Copyright &y& Elsevier]

Abstract: In this paper an attempt is made to extend some standard results in set theory on the basis of soft set relations. Antisymmetric relation and transitive closure of a soft set relation are introduced and an analogue of Warshall’s algorithm is proposed for calculating the transitive closure of a soft set relation. Ordering on a soft set is defined and some set theoretical results based on this are proved. [Copyright &y& Elsevier]

Abstract: In the past, many algorithms were proposed to mine association rules, most of which were based on item frequency values. Considering a customer may buy many copies of an item and each item may have different profits, mining frequent patterns from a traditional database is not suitable for some real-world applications. Utility mining was thus proposed to consider costs, profits and other measures according to user preference. In this paper, the high utility pattern tree (HUP tree) is designed and the HUP-growth mining algorithm is proposed to derive high utility patterns effectively and efficiently. The proposed approach integrates the previous two-phase procedure for utility mining and the FP-tree concept to utilize the downward-closure property and generate a compressed tree structure. Experimental results also show that the proposed approach has a better performance than Liu et al.’s two-phase algorithm in execution time. At last, the numbers of tree nodes generated from three different item ordering methods are also compared, with results showing that the frequency ordering produces less tree nodes than the other two. [Copyright &y& Elsevier]

Abstract: According to the hierarchical identification principle, a hierarchical gradient based iterative estimation algorithm is derived for multivariable output error moving average systems (i.e., multivariable OEMA-like models) which is different from multivariable CARMA-like models. As there exist unmeasurable noise-free outputs and unknown noise terms in the information vector/matrix of the corresponding identification model, this paper is, by means of the auxiliary model identification idea, to replace the unmeasurable variables in the information vector/matrix with the estimated residuals and the outputs of the auxiliary model. A numerical example is provided. [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: In this paper, we study two interesting variants of the classical bin packing problem, called Lazy Bin Covering (LBC) and Cardinality Constrained Maximum Resource Bin Packing (CCMRBP) problems. For the offline LBC problem, we first prove the approximation ratio of the First-Fit-Decreasing and First-Fit-Increasing algorithms, then present an APTAS. For the online LBC problem, we give a competitive analysis for the algorithms of Next-Fit, Worst-Fit, First-Fit, and a modified HARMONIC algorithm. The CCMRBP problem is a generalization of the Maximum Resource Bin Packing (MRBP) problem Boyar et al. (2006) . For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem. [Copyright &y& Elsevier]

Abstract: This paper concerns learning binary-valued functions defined on , and investigates how a particular type of ‘regularity’ of hypotheses can be used to obtain better generalization error bounds. We derive error bounds that depend on the sample width (a notion analogous to that of sample margin for real-valued functions). This motivates learning algorithms that seek to maximize sample width. [Copyright &y& Elsevier]

Abstract: This paper describes several classes of term rewriting systems (TRS’s), where narrowing has a finite search space and is still (strongly) complete as a mechanism for solving reachability goals. These classes do not assume confluence of the TRS. We also ascertain purely syntactic criteria that suffice to ensure the termination of narrowing, and include several subclasses of popular TRS’s such as right-linear TRS’s, almost orthogonal TRS’s, topmost TRS’s, and left-flat TRS’s. Our results improve and/or generalize previous criteria in the literature regarding narrowing termination. [Copyright &y& Elsevier]

Abstract: In this paper, an inversion algorithm for a banded matrix is presented. The twisted decompositions of a banded matrix are given first; then the inverse of the matrix is obtained, one column at time. The method is about two times faster than the standard method based on the decomposition, as is shown with the analysis of computing complexity and the numerical experiments. [Copyright &y& Elsevier]

Abstract: The generalized Adams–Bashforth–Moulton method, often simply called “the fractional Adams method”, is a useful numerical algorithm for solving a fractional ordinary differential equation: , where is the first integer not less than , and is the th-order fractional derivative of in the Caputo sense. Although error analyses for this fractional Adams method have been given for (a) , , (b) , , (c) , , (d) , , there are still some unsolved problems—(i) the error estimates for , , (ii) the error estimates for , , (iii) the solution having some special forms. In this paper, we mainly study the error analyses of the fractional Adams method for the fractional ordinary differential equations for the three cases (i)–(iii). Numerical simulations are also included which are in line with the theoretical analysis. [Copyright &y& Elsevier]

Abstract: In this paper, we show how to efficiently model check a subset of properties for the Time Petri Net model (TPN model), using the state class method. The verification proceeds by augmenting the TPN model under analysis with a special TPN, called Alarm-clock, to allow the capture of relevant time events. A forward on-the-fly exploration is then applied on the resulting TPN state class space to verify a timed property. A relaxation operation on state classes is also introduced to further improve performances. Alarm-clock is the same for all properties, whereas the exploration technique is not. Three exploration techniques are presented to cover most interesting TCTL properties. We prove the decidability of our verification technique for bounded TPN models and compare it with the reachability algorithm implemented in the tool UPPAAL [G. Behrmann, J. Bengtsson, A. David, K.G. Larsen, P. Pettersson, W. Yi, Uppaal implementation secrets, in: Proc. of the 7th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, 2002]. Finally, we give some experimental results to show the efficiency of our verification technique. [Copyright &y& Elsevier]

Abstract: In the present paper we study the computation of the rank of a block bidiagonal Toeplitz (BBT) sequence of matrices. We propose matrix-based, numerical and symbolical, updating and direct methods, computing the rank of BBT matrices and comparing them with classical procedures. The methods deploy the special form of the BBT sequence, significantly reducing the required flops and leading to fast and efficient algorithms. The numerical implementation of the algorithms computes the numerical rank in contrast with the symbolical implementation, which guarantees the computation of the exact rank of the matrix. The combination of numerical and symbolical operations suggests a new approach in software mathematical computations denoted as hybrid computations. [Copyright &y& Elsevier]

Abstract: It is a well-known result in the theory of simple games that a game is weighted if and only if it is trade robust. In this paper we propose a variant of trade robustness, that we call invariant-trade robustness, which is enough to determine whether a simple game is weighted. To test whether a simple game is invariant-trade robust we do not need to consider all winning coalitions; a reduced subset of minimal winning coalitions is enough. We make a comparison between the two methods (trade robustness and invariant-trade robustness) to check whether a simple game is weighted. We also provide by means of algorithms a full classification using both methods, for simple games with less than 8 voters according to the maximum level of (invariant-)trade robustness they achieve. [Copyright &y& Elsevier]

Abstract: In this work we construct three novel families of approximating subdivision schemes that generate piecewise exponential polynomials and we show how to convert these into interpolating schemes of great interest in curve design for their ability to reproduce important analytical shapes and to provide highly smooth limit curves with a controllable tension. In particular, throughout this paper we will focus on the derivation of 6-point interpolating schemes that turn out to be unique in combining vital ingredients like -continuity, simplicity of definition, ease of implementation, user independency, tension control and ability to reproduce salient trigonometric and transcendental curves. [Copyright &y& Elsevier]

Abstract: This paper presents an impulsive optimal control model for solving the optimal designing problem of the trajectory of horizontal wells. We take fully into account the effect of unknown disturbances in drilling. The optimal control problem can be converted into a nonlinear parametric optimization by integrating the state equation. We discuss here that the locally optimal solution depends in a continuous way on the parameters (disturbances) and utilize this property to propose a revised Hooke–Jeeves algorithm. The uniform design technique is incorporated into the revised Hooke–Jeeves algorithm to handle the multimodal objective function. The numerical simulation is in accordance with theoretical results. The numerical results illustrate the validity of the model and efficiency of the algorithm. [Copyright &y& Elsevier]

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: Systolic arrays for multiplication in of Yeh et al. with LSB (least significant bit) first algorithm have the unfavorable properties such as increased area complexity and bidirectional data flows compared with the arrays of Wang and Lin with MSB (most significant bit) first algorithm. In this paper, by using a polynomial basis with LSB first algorithm, we present new bit parallel and bit serial systolic arrays over . Our bit parallel systolic multiplier has unidirectional data flows with seven latches in each basic cell. Also our bit serial systolic array has only one control signal with eight latches in each basic cell. Thus our new arrays with LSB first algorithm have shorter critical path delay, comparable hardware complexity, and have the same unidirectional data flows compared with the arrays using MSB first algorithm. We also present new linear systolic arrays for multiplication in using irreducible trinomial . It is shown that our linear arrays with trinomial basis have reduced hardware complexity since they require two fewer latches than the linear systolic arrays using general irreducible polynomials. [Copyright &y& Elsevier]

Abstract: We separate the conceptual design and the representation of high quality surfaces by prescribing local shape via guide surfaces and then sampling these guides with a finite number of tensor-product patches. The paper develops a family of algorithms that allow trading polynomial degree for smoothness near the extraordinary points where more or fewer than four tensor-product patches meet. A key contribution are rules for a capping of a multi-sided hole by a small number of polynomial patches. The construction of highest quality creates first a cap of patches of degree and then perturbs it to yield an exact cap of degree . Since this perturbation is so small that its effect is typically not perceptible even in curvature display, the unperturbed surface of degree is an excellent alternative. Reducing the degree of the rings to , respectively , by choice of a different parameterization, increases the number of transition curves within the cap but does not alter the shape appreciably. [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: Given a simple polygon with two vertices and , the three-guard problem asks whether three guards can move from to such that the first and third guards are separately on two boundary chains of from to and the second guard is always kept to be visible from two other guards inside . It is a generalization of the well-known two-guard problem, in which two guards move on the boundary chains from to and are always kept to be mutually visible. In this paper, we introduce the concept of link-2-ray shots, which can be considered as ray shots under the notion of link-2-visibility. Then, we show a one-to-one correspondence between the structure of the restrictions placed on the motion of two guards and the one placed on the motion of three guards, and generalize the solution for the two-guard problem to that for the three-guard problem. We can decide whether there exists a solution for the three-guard problem in time, and if so generate a walk in time, where denotes the number of vertices of and the size of the optimal walk. This improves upon the previous time bounds and , respectively. Moreover, our results can be used to solve other more sophisticated geometric problems. [Copyright &y& Elsevier]

Abstract: The concept of table algebra in the title is a real nonsingular generalized table algebra in the sense of [Z. Arad, E. Fisman, M. Muzychuk, Generalized table algebras, Israel J. Math. 114 (1999) 29–60]. In this paper we first give some definitions and facts about table algebras. It is well known that every association scheme gives a Hecke-algebra which is a table algebra too. This leads to the natural question which properties of association schemes stay valid for table algebras. For instance, we prove the Second Isomorphism Theorem and the Jordan–Holder''s theorem for standard table algebras. [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: In this paper, we study the single-population evolutionary game and construct an algorithm to find evolutionarily stable strategies. Finally, by an example, we illuminate the computing process of algorithm. [Copyright &y& Elsevier]

Abstract: The covering generalized rough sets are an improvement of traditional rough set model to deal with more complex practical problems which the traditional one cannot handle. It is well known that any generalization of traditional rough set theory should first have practical applied background and two important theoretical issues must be addressed. The first one is to present reasonable definitions of set approximations, and the second one is to develop reasonable algorithms for attributes reduct. The existing covering generalized rough sets, however, mainly pay attention to constructing approximation operators. The ideas of constructing lower approximations are similar but the ideas of constructing upper approximations are different and they all seem to be unreasonable. Furthermore, less effort has been put on the discussion of the applied background and the attributes reduct of covering generalized rough sets. In this paper we concentrate our discussion on the above two issues. We first discuss the applied background of covering generalized rough sets by proposing three kinds of datasets which the traditional rough sets cannot handle and improve the definition of upper approximation for covering generalized rough sets to make it more reasonable than the existing ones. Then we study the attributes reduct with covering generalized rough sets and present an algorithm by using discernibility matrix to compute all the attributes reducts with covering generalized rough sets. With these discussions we can set up a basic foundation of the covering generalized rough set theory and broaden its applications. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a new method to efficiently compute a representation of an orthogonal basis of the nullspace of a sparse matrix operator with , . We assume that B has full rank, i.e., rank. It is well-known that the last columns of the orthogonal matrix Q in a QR factorization form such a desired null basis. The orthogonal matrix Q can be represented either explicitly as a matrix, or implicitly as a matrix H of Householder vectors. Typically, the matrix H represents the orthogonal factor much more compactly than Q. We will employ this observation to design an efficient block algorithm that computes a sparse representation of the nullspace basis in almost optimal complexity. This new algorithm may, e.g., be used to construct a null space basis of the discrete divergence operator in the finite element context, and we will provide numerical results for this particular application. [Copyright &y& Elsevier]