Search

Abstract: The paper describes and analyzes a method for computing border bases of a zero-dimensional ideal . The criterion used in the computation involves specific commutation polynomials, and leads to an algorithm and an implementation extending the ones in [B. Mourrain, Ph. Trébuchet, Generalised normal forms and polynomial system solving, in: M. Kauers (Ed.), Proc. Intern. Symp. on Symbolic and Algebraic Computation, ACM Press, New-York, 2005, pp. 253–260]. This general border basis algorithm weakens the monomial ordering requirement for Gröbner bases computations. It is currently the most general setting for representing quotient algebras, embedding into a single formalism Gröbner bases, Macaulay bases and a new representation that does not fit into the previous categories. With this formalism, we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This feature has a huge impact on practical efficiency, as illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper. [Copyright &y& Elsevier]

Abstract: In this paper we introduce an algorithm which solves the membership problem of Petri net controlled grammars without -rules and cyclic rules. We define a conditional tree which is a modified derivation tree of a context-free grammar with information about control by a Petri net. It is shown that a conditional tree is cancelled to a derivation tree without conditions if and only if there is a derivation under the control of the Petri net from the start symbol to a word which is the yielding of the conditional tree. Then the Earley’s algorithm is extended to make a conditional tree in addition to parse a word. Thus the word is generated by a given Petri net controlled grammar if and only if the resulting conditional tree is cancelled to a tree of no condition. The time complexity of the algorithm is nondeterministic polynomial of the length of an input word. Therefore the class of languages generated by Petri net controlled grammars without -rules and cyclic rules is included in the class of context-sensitive languages. [Copyright &y& Elsevier]

Abstract: This paper presents a new polynomial-time algorithm to solve the minimum cost tension problem. It runs in -time, where denote the number of nodes, number of arcs, and maximum arc capacity value of an arc cost, respectively. The algorithm improves the -time algorithm of Maurras (1994) . Also our algorithm, under the similarity assumption (Gabow, 1985) , runs in -time, which improves the -time algorithm of Hadjiat and Maurras (1997) . [Copyright &y& Elsevier]

Abstract: The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. [Copyright &y& Elsevier]

Abstract: A numerical elimination method is presented in this paper for floating-point computation in polynomial algebra. The method is designed to calculate one or more polynomials in an elimination ideal by a sequence of matrix rank/kernel computation. The method is reliable in numerical computation with verifiable stability and a sensitivity measurement. Computational experiment shows that the method possesses significant advantages over classical resultant computation in numerical stability and in producing eliminant polynomials with lower degrees and fewer extraneous factors. The elimination algorithm combined with an approximate GCD finder appears to be effective in solving polynomial systems for positive dimensional solutions. [Copyright &y& Elsevier]

Abstract: Evolutionary algorithms (EAs) find numerous applications, and practical knowledge on EAs is immense. In practice, sophisticated population-based EAs employing selection, mutation and crossover are applied. In contrast, theoretical analysis of EAs often concentrates on very simple algorithms such as the (1+1) EA, where the population size equals 1. In this paper, the question is addressed whether the use of a population by itself can be advantageous. A population-based EA that neither makes use of crossover nor any diversity-maintaining operator is investigated on an example function. It is shown that an increase of the population size by a constant factor decreases the expected runtime from exponential to polynomial. Thereby, the best gap known so far is improved from superpolynomial vs. polynomial to exponential vs. polynomial. Moreover, it is proved that the exponential and polynomial runtime bounds occur with a probability exponentially close to one if the population size is a constant (resp., a small polynomial). Finally, a second example function, where only a small population leads to a polynomial runtime, and a hierarchy result on the appropriate population size are presented. The analyses show formally how the population size can lead to different attractors in the search space. [Copyright &y& Elsevier]