Fast computation of Grbner basis of homogenous ideals of F[x,y]

This paper provides a fast algorithm for Grobner bases of homogenous ideals of F[x, y] over a finite field F. We show that only the S-polynomials of neighbor pairs of a strictly ordered finite homogenours generating set are needed in the computing of a Grobner base of the homogenous ideal. It reduces dramatically the number of unnecessary S-polynomials that are processed. We also show that the computational complexity of our new algorithm is O(N2), where N is the maximum degree of the input generating polynomials. The new algorithm can be used to solve a problem of blind recognition of convolutional codes. This problem is a new generalization of the important problem of synthesis of a linear recurring sequence.     

Automatic Construction of Finite Algebras

This paper deals with model generation for equational theories,i.e.,automatically generating (finite)models of a given set of (logical) equations.Our method of finite model generation and a tool for automatic construction of finite algebras is described.Some examples are given to show the applications of our program.We argue that,the combination of model generators and theorem provers enables us to get a better understanding of logical theories.A brief comparison betwween our tool and other similar tools is also presented.     

Design and Performance Evaluation of Sequence Partition Algorithms

Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of n distinct numbers into minimum number of monotone （increasing or decreasing） subsequences. This problem is NP-hard and the number of monotone subsequences can reach [√2n＋1/1-1/2]in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than [√2n＋1/1-1/2]monotone subsequences in O（n^1.5） time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity O（n^3）, a known greedy algorithm of time complexity O（n^1.5 log n）, and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.     

利用位置测量的单点和两点差分跟踪起始算法的比较研究

We consider the problem of initializing the tracking filter of a target moving with nearly constant velocity when position-only (1D, 2D, or 3D) measurements are available. It is known that the Kalman filter is optimal for such a problem, provided it is correctly initialized. We compare a single-point and the well-known two-point difference track initialization algorithms. We analytically show that if the process noise approaches zero and the maximum speed of a target used to initialize the velocity variance approaches infinity, then the single-point algorithm reduces to the two-point difference algorithm. We present numerical results that show that the single-point algorithm performs consistently better than the two-point difference algorithm in the mean square error sense. We also present analytical results that support the conjecture that this is true in general.     

A new approximation algorithm for sorting of signed permutations

Sequence comparison leads to a combinatorial optimization problem of sorting permutations by reversals and transpositions.Namely,given any two permutations,find the shortest distance between them.This problem is related with genome rearrangement,genes are oriented in DNA sequences.The transpositions which have been studied in the liteature can be viewed as operations working on two consecutive segments of the genome.In this paper,a new kind of transposition which can work on two arbitrary segments of the genome is proposed,and the sorting of signed permutations by reversals and this new kind of transpostitions are studied.After establishing a lower bound on the number of operations needed,a 2-approximation algorithm is presented for this problem and an example is given to show that the performance ratio of the algorithm cannot be improved.     

An Improvement of Herbrands Theorem and Its Application to Model Generation Theorem Proving

This paper presents an improvement of Herbrand's theorem.We propose a method for specifying a sub- universe of the Herbrand universe of a clause set S for each argument of predicate symbols and function symbols in S. We prove that a clause set S is unsatisfiable if and only if there is a finite unsatisfiable set of ground instances of clauses of S that are derived by only instantiating each variable,which appears as an argument of predicate symbols or function symbols,in S over its corresponding argument's sub-universe of the Herbrand universe of S.Because such sub-universes are usually smaller(sometimes considerably)than the Herbrand universe of S,the number of ground instances may decrease considerably in many cases.We present an algorithm for automatically deriving the sub-universes for arguments in a given clause set,and show the correctness of our improvement.Moreover,we introduce an application of our approach to model generation theorem proving for non-range-restricted problems,show the range-restriction transformation algorithm based on our improvement and provide examples on benchmark problems to demonstrate the power of our approach.     

An Improvement of Herbrand＇s Theorem and Its Application to Model Generation Theorem Proving

This paper presents an improvement of Herbrand＇s theorem. We propose a method for specifying a subuniverse of the Herbrand universe of a clause set S for each argument of predicate symbols and function symbols in S. We prove that a clause set S is unsatisfiable if and only if there is a finite unsatisfiable set of ground instances of clauses of S that are derived by only instantiating each variable, which appears as an argument of predicate symbols or function symbols, in S over its corresponding argument＇s sub-universe of the Herbrand universe of S. Because such sub-universes are usually smaller （sometimes considerably） than the Herbrand universe of S, the number of ground instances may decrease considerably in many cases. We present an algorithm for automatically deriving the sub-universes for arguments in a given clause set, and show the correctness of our improvement. Moreover, we introduce an application of our approach to model generation theorem proving for non-range-restricted problems, show the range-restriction transformation algorithm based on our improvement and provide examples on benchmark problems to demonstrate the power of our approach.     

求解圆形packing问题的拟人退火算法

Circles packing problem is an NP-hard problem and is difficult to solve. In this paper, a hybrid search strategy for circles packing problem is discussed. A way of generating new configuration is presented by simulating the moving of elastic objects, which can avoid the blindness of simulated annealing search and make iteration process converge fast. Inspired by the life experiences of people, an effective personified strategy to jump out of local minima is given. Based on the simulated annealing idea and personification strategy, an effective personified annealing algorithm for circles packing problem is developed. Numerical experiments on benchmark problem instances show that the proposed algorithm outperforms the best algorithm in the literature.     

Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

This paper investigates the transition function and the reachability conditions of finite automata by using a semitensor product of matrices, which is a new powerful matrix analysis tool. The states and input symbols are first expressed in vector forms, then the transition function is described in an algebraic form. Using this algebraic representation, a sufficient and necessary condition of the reachability of any two states is proposed, based on which an algorithm is developed for discovering all the paths from one state to another. Furthermore, a mechanism is established to recognize the language acceptable by a finite automaton. Finally, illustrative examples show that the results/algorithms presented in this paper are suitable for both deterministic finite automata （DFA） and nondeterministic finite automata （NFA）.     

The Generation of a Sort of Fractal Graphs

We present an approach for generating a sort of fractal graphs by a simple probabilistic logic neuron network and show that the graphs can be represented by a set of compressed codings.An algorithm for quickly finding the codings,i.e.,recognizing the corresponding graphs,is given.The codings are shown to be optimal.The results above possibly give us the clue for studying image compression and pattern recognition.     

Price-based interference avoidance game in the Gaussian interference channel

This paper considers a distributed interference avoidance problem employing frequency assignment in the Gaussian interference channel(IC).We divide the common channel into several sub-channels and each user chooses one sub-channel for transmission in such a way that the total interference in the IC is minimum.This mechanism named interference avoidance in this paper can be modeled as a competitive game model.And a completely autonomous distributed iterative algorithm called distributed interference avoidance algorithm(DIA)is adopted to achieve the Nash equilibrium(NE)of the game.Due to the self-optimum,the DIA is a sub-optimal algorithm.Therefore,through introducing an optimal compensation(or price)into the competitive game model,we successfully develop a compensation-based game model to approximate the optimal interference avoidance problem.Moreover,an optimal algorithm called iterative optimal interference avoidance algorithm(IOIA)is proposed to reach the optimality of the interference avoidance scheme.We analyze the implementation complexity of the proposed algorithm which is only O(N),with N standing for the number of users in the IC.We also give the proof on the convergence of the proposed algorithm.The performance upper bound and lower bound are derived for the IOIA algorithm.The simulation results show that the IOIA does reach the optimality under the condition of interference avoidance mechanism.     

An improved fireworks algorithm for the capacitated vehicle routing problem

The capacitated vehicle routing problem (CVRP), which aims at minimizing travel costs, is a wellknown NP-hard combinatorial optimization. Owing to its hardness, many heuristic search algorithms have been proposed to tackle this problem. This paper explores a recently proposed heuristic algorithm named the fireworks algorithm (FWA), which is a swarm intelligence algorithm. We adopt FWA for the combinatorial CVRP problem with several modifications of the original FWA: it employs a new method to generate "sparks" according to the selection rule, and it uses a new method to determine the explosion amplitude for each firework. The proposed algorithm is compared with several heuristic search methods on some classical benchmark CVRP instances. The experimental results show a promising performance of the proposed method. We also discuss the strengths and weaknesses of our algorithm in contrast to traditional algorithms.     

Distributed regularized online optimization using forward–backward splitting

This paper considers the problem of distributed online regularized optimization over a network that consists of multiple interacting nodes. Each node is endowed with a sequence of loss functions that are time-varying and a regularization function that is fixed over time. A distributed forward–backward splitting algorithm is proposed for solving this problem and both fixed and adaptive learning rates are adopted. For both cases, we show that the regret upper bounds scale as O( √T ), where T is the time horizon. In particular, those rates match the centralized counterpart. Finally, we show the effectiveness of the proposed algorithms over an online distributed regularized linear regression problem.     

Improving the Reliability of Computer Communication Networks

For networks that are directed or can be represented by a directed network,reversing one or more of the uni-directional links may provide the ability to reconnect a network that has been disconnected by link failure.In this paper,a new approach to reconfigure such networks is proposed.We develop a linear time algorithm which,when reachability has been destroyed by the removal of a single link,optimally restores reachability through the reversal of selected links.Multi-link failure reconnectability is discussed and an algorithm with polynomial complexity is given which provides a nearly optimum solution to reconnect the network.We show that the reliability of a network that allows reversals is at least twice more than that in which reversals are not permitted.Unfortunately,the reconnection of some networks cannot be established.Therefore,we discuss the maximization of reachability of such networks so that each node can reach maximum number of the other nodes.     

Stochastic Distribution Control of Singular Systems: Output PDF Shaping

This paper presents a new algorithm designed to control the shape of the output probability density function (PDF) of singular systems subjected to non-Gaussian input. The aim is to select a control input uk such that the output PDF is made as close as possible to a given PDF. Based on the B-spline neural network approximation of the output PDF, the control algorithm is formulated by extending the developed PDF control strategies of non-singular systems to singular systems. It has been shown that under certain conditions the stability of the closed-loop system can be guaranteed. Simulation examples are given to show the effectiveness of the proposed control algorithm.     

Developing a multi-objective,multi-item inventory model and three algorithms for its solution

We develop a multi-objective model in a multi-product inventory system.The proposed model is a joint replenishment problem(JRP) that has two objective functions.The first one is minimization of total ordering and inventory holding costs,which is the same objective function as the classic JRP.To increase the applicability of the proposed model,we suppose that transportation cost is independent of time,is not a part of holding cost,and is calculated based on the maximum of stored inventory,as is the case in many real inventory problems.Thus,the second objective function is minimization of total transportation cost.To solve this problem three efficient algorithms are proposed.First,the RAND algorithm,called the best heuristic algorithm for solving the JRP,is modified to be applicable for the proposed problem.A multi-objective genetic algorithm(MOGA) is developed as the second algorithm to solve the problem.Finally,the model is solved by a new algorithm that is a combination of the RAND algorithm and MOGA.The performances of these algorithms are then compared with those of the previous approaches and with each other,and the findings imply their ability in finding Pareto optimal solutions to 3200 randomly produced problems.     

Shadow geometry maps for alias-free shadows

Shadow maps sample scene visibility in the light source space and offer an efficient solution to generate hard shadows.However,they suffer from aliasing artifacts because of discretization errors,inadequate resolution and projection distortion.In this paper,we propose the shadow geometry map method,where a shadow depth map is augmented by storing geometry information about scenes.This leads to a new shadowrendering algorithm that combines a supersampling filter,a geometry-aware reconstruction kernel and an irregular sampling filter.Our method produces high quality alias-free and subpixel supersampling shadow rendering and retains the simplicity and the efficiency of shadow maps.We show that the algorithm pipeline is efficiently parallelized using current programmable graphics hardware and that our method is capable of generating high quality hard shadows.     

A New Classification Rule Inducing Algorithm Based on Difference Degree （CRID）

A difference measure of a condition attribute value is defined and a new classification rule inducing algorithm based on it is presented. The first key feature of the new algorithm, in comparison with standard rough set method, is not the attributes reduction step in advance; the second feature is generating a rule for each example; and the third feature is that rules in its rule set have intersection cover or they may cover some same examples and vote for them. Experimental results on 70 datasets show that the new algorithm has a competitive classification performance.     

Variable partial-update NLMS algorithms with data-selective updating

We note that some existing algorithms are based on the normalized least-mean square （NLMS） algorithm and aim to reduce the computational complexity of NLMS all inherited from the solution of the same optimization problem, but with different constraints. A new constraint is analyzed to substitute an extra searching technique in the set-membership partial-update NLMS algorithm （SM-PU-NLMS） which aims to get a variable number of updating coefficients for a further reduction of computational complexity. We get a closed form expression of the new constraint without extra searching technique to generate a novel set-membership variable-partial-update NLMS （SM-VPU-NLMS） algorithm. Note that tile SM-VPU-NLMS algorithm obtains a faster convergence and a smaller mean-squared error （MSE） than the existing SM-PU-NLMS. It is pointed out that the closed form expression can also be applied to the conventional variable-step-size partial-update NLMS （VSS-PU-NLMS） algorithm. The novel variable-step-size variable-partial-update NLMS （VSS-VPU-NLMS） algorithm is also verified to get a further computational complexity reduction. Simulation results verify that our analysis is reasonable and effective.     

Linearly and Quadratically Separable Classifiers Using Adaptive Approach

This paper presents a fast adaptive iterative algorithm to solve linearly separable classification problems in R n.In each iteration,a subset of the sampling data (n-points,where n is the number of features) is adaptively chosen and a hyperplane is constructed such that it separates the chosen n-points at a margin and best classifies the remaining points.The classification problem is formulated and the details of the algorithm are presented.Further,the algorithm is extended to solving quadratically separable classification problems.The basic idea is based on mapping the physical space to another larger one where the problem becomes linearly separable.Numerical illustrations show that few iteration steps are sufficient for convergence when classes are linearly separable.For nonlinearly separable data,given a specified maximum number of iteration steps,the algorithm returns the best hyperplane that minimizes the number of misclassified points occurring through these steps.Comparisons with other machine learning algorithms on practical and benchmark datasets are also presented,showing the performance of the proposed algorithm.