Search

Combinatorics of biopolymer structures, especially enumeration of various RNA secondary structures and protein contact maps, is of significant interest for communities of both combinatorics and computational biology. However, most of the previous combinatorial enumeration results for these structures are presented in terms of generating functions, and few are explicit formulas. This paper is mainly concerned with finding explicit enumeration formulas for a particular class of biologically relevant structures, say, saturated 2-regular simple stacks, whose configuration is related to protein folds in the 2D honeycomb lattice. We establish a semi-bijective algorithm that converts saturated 2-regular simple stacks into forests of small trees, which produces a uniform formula for saturated extended 2-regular simple stacks with any of the six primary component types. Summarizing the six different primary component types, we obtain a bivariate explicit formula for saturated extended 2-regular simple stacks with n vertices and k arcs. As consequences, the uniform formula can be reduced to Clote's results on k -saturated 2-regular simple stacks and the optimal 2-regular simple stacks, and Guo et al.'s result on the optimal extended 2-regular simple stacks. [ABSTRACT FROM AUTHOR]

In this paper, we study the desingularization problem in the first q -Weyl algebra. We give an order bound for desingularized operators, and thus derive an algorithm for computing desingularized operators in the first q -Weyl algebra. Moreover, an algorithm is presented for computing a generating set of the first q -Weyl closure of a given q -difference operator. As an application, we certify that several instances of the colored Jones polynomial are Laurent polynomial sequences by computing the corresponding desingularized operator. [ABSTRACT FROM AUTHOR]

Abstract: In an earlier paper with Whittle, we showed that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid M. The purpose of this paper is to give a polynomial-time algorithm for constructing such a tree for M. [Copyright &y& Elsevier]

In this paper, we derive uniqueness and stability results for surface tensors. Further, we develop two algorithms that reconstruct shape of n -dimensional convex bodies. One algorithm requires knowledge of a finite number of surface tensors, whereas the other algorithm is based on noisy measurements of a finite number of harmonic intrinsic volumes. The derived stability results ensure consistency of the two algorithms. Examples that illustrate the feasibility of the algorithms are presented. [ABSTRACT FROM AUTHOR]

Abstract: In a recent paper (Cucker et al., 2008 ) we analyzed a numerical algorithm for computing the number of real zeros of a polynomial system. The analysis relied on a condition number for the input system f. In this paper we look at as a random variable derived from imposing a probability measure on the space of polynomial systems and give bounds for both the tail and the expected value . [Copyright &y& Elsevier]

Abstract: In this paper we enumerate k-noncrossing RNA pseudoknot structures with given minimum stack-length, σ. One main result of the paper is the asymptotic formula for their number: , where is explicitly known. Our results show that the number of k-noncrossing structures without isolated base pairs is significantly smaller than the number of all k-noncrossing structures. In particular we prove that, for large n, the number of 3- and 4-noncrossing RNA structures with stack-length ⩾2 is given by and , respectively. Our results are of importance for prediction algorithms and provide evidence for the existence of neutral networks of RNA pseudoknot structures. [Copyright &y& Elsevier]

Abstract: Multivariate polynomial dynamical systems over finite fields have been studied in several contexts, including engineering and mathematical biology. An important problem is to construct models of such systems from a partial specification of dynamic properties, e.g., from a collection of state transition measurements. Here, we consider static models, which are directed graphs that represent the causal relationships between system variables, so-called wiring diagrams. This paper contains an algorithm which computes all possible minimal wiring diagrams for a given set of state transition measurements. The paper also contains several statistical measures for model selection. The algorithm uses primary decomposition of monomial ideals as the principal tool. An application to the reverse-engineering of a gene regulatory network is included. The algorithm and the statistical measures are implemented in Macaulay 2, and are available from the authors. [Copyright &y& Elsevier]

Abstract: The algebraic theory of variable-length codes was initiated by Schützenberger in the 1950s. Almost all the subsequently stated results in this theory are constructive and therefore lead to algorithms. However, there are some basic problems that are still open. For instance, we still do not know how to decide whether a finite code can be embedded in a finite maximal one. We answer this question under additional hypotheses. Precisely, let A be a finite alphabet with , let . Let , let be the number of factors in the prime factorization of n. We give an algorithm to decide whether there exists n, with , and a finite maximal code C which is also factorizing such that . We recall that a factorizing code is a finite maximal code which satisfies the factorization conjecture, proposed by Schützenberger. The above-mentioned statement is a consequence of another result proved in this paper. Namely, given a factorizing code C, it is known that the words in satisfy a property defined by using factorizations of cyclic groups. In this paper we give an algorithm to decide whether a set can be embedded in a set satisfying . Furthermore, we prove that, conversely, for each set satisfying , under additional hypotheses, there exists a factorizing code C such that and, as a consequence, is a code. In this case, C can be constructed starting with prefix/suffix codes and by using two types of operations on codes (composition and substitution). The additional required hypotheses concern the structure of the factorizations involved and are always satisfied when, for each , we have , with . In addition, we prove that there exist sets which satisfy and which are not codes. [Copyright &y& Elsevier]

In this paper, we propose algorithms for computing differential Chow forms for ordinary prime differential ideals which are given by characteristic sets. The algorithms are based on an optimal bound for the order of a prime differential ideal in terms of a characteristic set under an arbitrary ranking, which shows the Jacobi bound conjecture holds in this case. Apart from the order bound, we also give a degree bound for the differential Chow form. In addition, for a prime differential ideal given by a characteristic set under an orderly ranking, a much simpler algorithm is given to compute its differential Chow form. The computational complexity of the algorithms is single exponential in terms of the Jacobi number, the maximal degree of the differential polynomials in a characteristic set, and the number of variables. [ABSTRACT FROM AUTHOR]

Grey-scale local algorithms have been suggested as a fast way of estimating surface area from grey-scale digital images. Their asymptotic mean has already been described. In this paper, the asymptotic behavior of the variance is studied in isotropic and sufficiently smooth settings, resulting in a general asymptotic bound. For compact convex sets with nowhere vanishing Gaussian curvature, the asymptotics can be described more explicitly. As in the case of volume estimators, the variance is decomposed into a lattice sum and an oscillating term of at most the same magnitude. [ABSTRACT FROM AUTHOR]

Abstract: A plane partition is a matrix , where and , with non-negative integer entries, and whose rows and columns are weakly decreasing. From a geometric point of view plane partitions are equivalent to pyramids, subsets of the integer lattice which play an important role in Discrete Tomography. As a consequence, some typical problems concerning the tomography of discrete lattice sets can be rephrased and considered via plane partitions. In this paper we focus on some of them. In particular, we get a necessary and sufficient condition for additivity, a canonical procedure for checking the existence of (weakly) bad configurations, and an algorithm which constructs minimal pyramids (with respect to the number of levels) with assigned projection of a bad configurations. [Copyright &y& Elsevier]

Abstract: Bouvel and Pergola introduced the notion of minimal permutations in the study of the whole genome duplication-random loss model for genome rearrangements. Let denote the set of minimal permutations of length n with d descents, and let . They showed that and , where is the n-th Catalan number. Mansour and Yan proved that . In this paper, we consider the problem of counting minimal permutations in with a prescribed set of ascents, and we show that they are in one-to-one correspondence with a class of skew Young tableaux, which we call 2-regular skew tableaux. Using the determinantal formula for the number of skew Young tableaux of a given shape, we find an explicit formula for . Furthermore, by using the Knuth equivalence, we give a combinatorial interpretation of a formula for a refinement of the number . [Copyright &y& Elsevier]

Abstract: The paper focuses on deterministic and unambiguous finite automata (DFAʼs and UNFAʼs respectively for short) in the case of a one-letter alphabet. We present a structural characterization of unary UNFAʼs and some considerations relating minimal UNFAʼs with minimum DFAʼs recognizing a given unary language. We also present an algorithm for the construction of a minimal UNFA for a unary regular language. Then we establish a correspondence between pairs of UNFAʼs recognizing a unary language and its complement respectively, and the disjoint covering systems of number theory. It allows us to provide some conditions relating the number of successful simple paths and the lengths of cycles in an UNFA recognizing a unary language with the same parameters in an UNFA recognizing its complement. [Copyright &y& Elsevier]

Abstract: This paper presents a new algorithm for the absolute factorization of parametric multivariate polynomials over the field of rational numbers. This algorithm decomposes the parameters space into a finite number of constructible sets. The absolutely irreducible factors of the input parametric polynomial are given uniformly in each constructible set. The algorithm is based on a parametric version of Hensel''s lemma and an algorithm for quantifier elimination in the theory of algebraically closed field in order to reduce the problem of finding absolute irreducible factors to that of representing solutions of zero-dimensional parametric polynomial systems. The complexity of this algorithm is single exponential in the number n of the variables of the input polynomial, its degree d w.r.t. these variables and the number r of the parameters. [Copyright &y& Elsevier]

Abstract: In this paper we analyze O''Hara''s partition bijection. We present three type of results. First, we show that O''Hara''s bijection can be viewed geometrically as a certain scissor congruence type result. Second, we obtain a number of new complexity bounds, proving that O''Hara''s bijection is efficient in several special cases and mildly exponential in general. Finally, we prove that for identities with finite support, the map of the O''Hara''s bijection can be computed in polynomial time, i.e. much more efficiently than by O''Hara''s construction. [Copyright &y& Elsevier]

Abstract: In this paper, we show that there are initial value problems defined with polynomial ordinary differential equations that can simulate universal Turing machines in the presence of bounded noise. The polynomial ODE defining the IVP is explicitly obtained and the simulation is performed in real time. [Copyright &y& Elsevier]

Abstract: The gap function of an infinite word over the binary alphabet gives the distances between consecutive 1''s in this word. In this paper we study infinite binary words whose gap function is injective or “almost injective.” A method for computing the subword complexity of such words is given. A necessary and sufficient condition for a function to be the subword complexity function of a binary word whose gap function is increasing is obtained. [Copyright &y& Elsevier]

Abstract: Two kinds of decompositions of a -module are introduced in this article, a Loewy-decomposition and a primary decomposition. Algorithms are described which allow to construct decompositions for finite-dimensional -modules. Both decompositions rely on the concept of the -module of relative syzygies introduced in the paper. Furthermore an algorithm is described which tests whether two given -modules are isomorphic under the relevant type of transformations. [Copyright &y& Elsevier]

Abstract: In applications, choices of orthonormal bases in Hilbert space may come about from the simultaneous diagonalization of some specific abelian algebra of operators. This is the approach of quantum theory as suggested by John von Neumann; but as it turns out, much more recent constructions of bases in wavelet theory, and in dynamical systems, also fit into this scheme. However, in these modern applications, the basis typically comes first, and the abelian algebra might not even be made explicit. It was noticed recently that there is a certain finite set of non-commuting operators , first introduced by engineers in signal processing, which helps to clarify this connection, and at the same time throws light on decomposition possibilities for wavelet packets used in pyramid algorithms. There are three interrelated components to this: an orthonormal basis, an abelian algebra, and a projection-valued measure. While the operators were originally intended for quadrature mirror filters of signals, recent papers have shown that they are ubiquitous in a variety of modern wavelet constructions, and in particular in the selection of wavelet packets from libraries of bases. These are constructions which make a selection of a basis with the best frequency concentration in signal or data-compression problems. While the algebra generated by the -system is non-abelian, and goes under the name “Cuntz algebra” in -algebra theory, each of its representations contains a canonical maximal abelian subalgebra, i.e., the subalgebra is some for a Gelfand space X. A given representation of , restricted to , naturally induces a projection-valued measure on X, and each vector in induces a scalar-valued measure on X. We develop this construction in the general context with a view to wavelet applications, and we show that the measures that had been studied earlier for a very restrictive class of -systems (i.e., the Lemarié–Meyer quadrature mirror filters) in the theory of wavelet packets are special cases of this. Moreover, we prove a structure theorem for certain classes of induced scalar measures. In the applications, X may be the unit interval, or a Cantor set; or it may be an affine fractal, or even one of the more general iteration limits involving iterated function systems consisting of conformal maps. [Copyright &y& Elsevier]

Abstract: We study a fundamental family of root-finding iteration functions in the context of symmetric functions. This family, which we refer to as the Basic Family, goes back to Schröder''s 1870 paper, and admits numerous different representations. In one representation, it is known as König''s family. A purely algebraic derivation by Kalantari et al. leads to the discovery of many minimality and uniqueness properties of this family. Our new perspective reveals a symmetric algebraic structure of the Basic Family, which gives rise to simple combinatorial proofs of many important properties of this family and two of its variants. The first variant maintains high order of convergence for multiple roots. The second variant, called the Truncated Basic Family, is an infinite family of mth order methods for every , using only the first derivatives. Our result extends Kalantari''s analysis of Halley''s family, the special case of the Truncated Basic Family where . Finally, we give a recipe for constructing new high order root-finding algorithms, and use it to derive an interesting family of iteration functions that have higher orders of convergence for multiple roots than for simple roots. [Copyright &y& Elsevier]

Reconstructing phylogenetic trees is a fundamental task in evolutionary biology. Various algorithms exist for this purpose, many of which come under the heading of ‘supertree methods.’ These methods amalgamate a collection P of phylogenetic trees into a single parent tree. In this paper, we show that, in both the rooted and unrooted settings, counting the number of parent trees that preserve all of the ancestral relationships displayed by the phylogenetic trees in P is #P-complete. [Copyright &y& Elsevier]

In this paper, we set up a geometric framework for solving sparse matrix problems. We introduce geometric sparseness, a notion which applies to several well-known families of sparse matrix. Two algorithms are presented for solving geometrically-sparse matrix problems. These algorithms are inspired by techniques in classical algebraic topology, and involve the construction of a simplicial complex from certain data on the matrix. In both cases, large parts of the computation can be parallelised. [Copyright &y& Elsevier]

A word w over the alphabet A is called uniform if for any two words u and v of the same length, the numbers of occurrences of u and v in w differ at most by 1. In particular, a uniform word contains as factors all the words of length ⩽Gw, where Gw is the maximal length of a repeated factor of w. Some characterizations of uniform words are given. A lower bound for the number of uniform words of length N is determined in some special cases. The main result of the paper is the proof that on each alphabet A there exist uniform words of any length. Moreover, an efficient algorithm to construct for any N a uniform word of length N is given. Finally, we give a characterization of a uniform word of length N as a minimum of two different quasi-order relations defined in AN and as a maximum of suitable entropy functionals. [Copyright &y& Elsevier]

A weighted composite digraph is obtained from some weighted digraph by replacing each vertex with a weighted digraph. In this paper, we give a beautiful combinatorial proof of the formula for forest volumes of composite digraphs obtained by Kelmans et al. [DIMACS Technical Report 2000-03, 2000]. Moreover, a generalization of this formula is present. [Copyright &y& Elsevier]

In this paper we consider five conjectured harmonic number identities similar to those arising in the context of supercongruences for Ape´ry numbers. The general object of this article is to discuss the possibility of automating not only the proof but also the discovery of such formulas. As a specific application we consider two different algorithmic methods to derive and to prove the five conjectured identities. One is based on an extension of Karr's summation algorithm in difference fields. The other method combines an old idea of Newton (which has been extended by Andrews) with Zeilberger's algorithm for definite hypergeometric sums. [Copyright &y& Elsevier]

In this paper, we present a direct algorithm to construct the minimal Z-pairs for rational functions. We describe a Maple implementation of the algorithm and show timing comparisons between this algorithm and other related algorithms. We also summarize an analogous algorithm for the q-difference case. [Copyright &y& Elsevier]

The Kazhdan-Lusztig polynomial of a matroid was introduced by Elias et al. (2016) [4]. Let U m , d denote the uniform matroid of rank d on a set of m + d elements. Gedeon et al. (2017) [7] pointed out that they can derive an explicit formula of the Kazhdan-Lusztig polynomials of U m , d using equivariant Kazhdan-Lusztig polynomials. In this paper we give an alternative explicit formula, which allows us to prove the real-rootedness of the Kazhdan-Lusztig polynomials of U m , d for 2 ≤ m ≤ 15 and all d 's. The case m = 1 was previously proved by Gedeon et al. (2017) [8]. We further determine the Z -polynomials of all U m , d 's and prove the real-rootedness of the Z -polynomials of U m , d for 2 ≤ m ≤ 15 and all d 's. Our formula also enables us to give an alternative proof of Gedeon, Proudfoot, and Young's formula for the Kazhdan-Lusztig polynomials of U m , d 's without using the equivariant Kazhdan-Lusztig polynomials. [ABSTRACT FROM AUTHOR]

D-finite (or holonomic) functions satisfy linear differential equations with polynomial coefficients. They form a large class of functions that appear in many applications in Mathematics or Physics. It is well-known that these functions are closed under certain operations and these closure properties can be executed algorithmically. Recently, the notion of D-finite functions has been generalized to differentially definable or D n -finite functions. Also these functions are closed under operations such as forming (anti)derivative, addition or multiplication and, again, these can be implemented. In this paper we investigate how D n -finite functions behave under composition and how they are related to algebraic and differentially algebraic functions. [ABSTRACT FROM AUTHOR]