In this talk I will present work-in-progress of a combinatorial problem motivated from the operational aspects of the Smyth powerdomain in domain theory, and the fixed-point semantics of disjunctive programs in logic programming. The problem illustrates the fundamental order-theoretic and completeness property of the generalized resolution principle.
The minimum cardinality of the set of chains that are partitions of the powerset lattice of n elements is an interesting problem. Two proofs will be presented to show that the minimum cardinality is Cnn/2. The first proof is a constructive one, and the second proof takes advantage of the so-called Matching Theorem.
The maximum cardinality of anti-chains of the complete lattice has a close relation to the problem above. The same result can be derived easily given the result for minimum cardinality. But I will give a different proof using the pigeonhole principle.
While there is a rich collection of results in sequence comparison on the problem of aligning two strings under various objective functions, there is surprisingly little work on the seemingly similar problem of aligning two alignments. The problem becomes computationally challenging when the alignment objective function counts gaps (as is necessary to obtain good alignments of biological sequences) and has the form of the sum-of-pairs objective. We initiate a thorough study of this problem when either of the the two input alignments is presented as (1) a single sequence (a degenerate form of an alignment), (2) a multiple alignment of two or more sequences, or (3) a so-called profile, which is a representation of an alignment often used in computational biology in which the columns of the alignment are reduced to distributions over the sequence alphabet. This gives rise to five new problem variations, some of which arise as subproblems in heuristics for multiple sequence alignment, or when determining the relatedness of an individual sequence to a family of sequences. In the talk we will focus only on the sequence versus alignment variation with exact gap counts, for which we have developed the first provably efficient algorithm. Given a sequence A of length m and a multiple alignment B of length of n, the algorithm finds an optimal alignment of A with B in O(m n log n) time. The algorithm contains an interesting application of the candidate-list technique originally developed for sequence versus sequence alignment with convex gap costs.
This is joint work with Weiqing Zhang. The full paper will be presented at the 9th Symposium on Combinatorial Pattern Matching at DIMACS in July.
A sequence of integers which is P-recursive satisfies a linear homogeneous recurrence relation with polynomial coefficients. Consequently the first n terms of such a sequence can be computed in space O(1) and time O(n). Parts I and II of this series concentrated on algebraic aspects of P-recursive sequences. In Part III methods of deriving P-recurrences based on structural reduction will be introduced. In some cases, such as counting labled triangle-free cubic graphs, reduction can be applied when the more algebraic methods don't seem to work.
P-recursive sequences are strongly restricted; for instance, the numbers of labeled r-regular graphs form a P-recursive sequence, but the numbers of those that are connected do not seem to be P-recursive when r > 2. In this situation there are efficient solution methods based on newtonian iterations of power series, which will be introduced and illustrated by the connectedness example.
What is the longest path in a randomly chosen graph? We will introduce the notion of ``randomly chosen'' by describing the model Gn,p. In this model, one begins with n isolated points, and then for each pair of vertices i,j independently decides, with probability p, whether to place an edge between i and j.
The ultimate goal is to understand the work of Ajtai, Komlos, and Szemeredi, and the work of de la Vega on this problem, but I'll assume no background initially.
First, as an appendix to my colloquium talk, I will describe the separation of cycle inequalities for the weighted consecutive problem by shortest path computations.
Next, I will describe some algorithmic ideas for solving the facet enumeration problem for getting insight into the facial structure of polytopes associated with combinatorial optimization problems.
Finally, by means of a branch-and-cut algorithm for solving the linear ordering problem I will show how small instance relaxations can be used effectively in practical branch-and-cut algorithms.
A matching of an undirected graph G = (V,E) is a subset M of the edges E such that no two edges in M share a common vertex. A maximal weighted matching is a matching with maximum total weight. Edmonds gave the first polynomial time algorithm to this problem, whose time bound is O(n4), for a graph of n vertices. There are several improvements to this basic idea, and the current best-known time bound is O(n (m + n log n)), where m is the number of edges, achieved by Gabow. I will give the outline of the basic algorithm.
Kleene algebras are algebraic structures with operators +, . , *, 0, 1, satisfying certain axioms. We discuss a Kleene algebra proposed by Kozen (Kozen's axioms), and use these axioms to prove a*a*=a*, (a+b)*=a*(ba*)*, etc. We show that matrices over a Kleene algebra form a Kleene algebra, and we also introduce definitions such as finite automata over a Kleene algebra and simple, epsilon-free, deterministic automata.
In Part II of the talk on June 2, Jun Yu will present a proof of completeness of this axiomatization. As a consequence of this, two regular expressions r, s represent the same language if and only if r=s is a theorem of Kozen's system.
|
| CATS |