waashk/dblp huggingface dataset:
on maximal instances for the original syntenic distance. the syntenic distance between two genomes has been introduced by ferretti, nadeau and sankoff as an approximation of the evolutionary distance between genomes for which the gene order is not known. this distance is the minimum number of fusions, fissions and translocations required to transform a genome into another. kleinberg and liben-nowell, as well as pisanti and sagot, proved independently that for genomes with n chromosomes the diameter for this distance is 2n - 4. pisanti and sagot also generalized this result, showing that the maximal distance between a genome with m chromosomes and a genome with n chromosomes is n + m - 4. kleinberg and liben-nowell asked for a characterization of maximal instances for the syntenic distance (pairs of n-chromosome genomes at a distance of 2n - 4). in this paper, we give such a characterization, and show that we can extend it to pairs of genomes with, respectively, n and m chromosomes that are at maximal distance.
graph encoding of 2-gon tilings. 2d-gon tilings with parallelograms are a model used in physics to study quasicrystals, and they are also important in combinatorics for the study of aperiodic structures. in this paper, we study the graph induced by the adjacency relation between tiles. this relation can been used to encode simply and efficiently 2d-gon tilings for algorithmic manipulation. we show for example how it can be used to sample random 2d-gon tilings.
pattern matching as cut elimination. we present a typed pattern calculus with explicit pattern matching and explicit substitutions, where both the typing rules and the reduction rules are modeled on the same logical proof system, namely gentzen sequent calculus for intuitionistic minimal logic. our calculus is inspired by the curry-howard isomorphism, in the sense that types, both for patterns and terms, correspond to propositions, terms correspond to proofs, and term reduction corresponds to sequences of sequent proof normalization steps performed by cut elimination. the calculus enjoys subject reduction, confluence, preservation of strong normalization w.r.t a system with meta-level substitutions and strong normalization for well-typed terms. as a consequence, it can be seen as an implementation calculus for functional formalisms defined with meta-level operations for pattern matching and substitutions. this work is a revised and extended version of cerrito and kesner (14th annual ieee symposium on logic in computer science (lics), ieee computer society press, silver spring, md, 1999, pp. 98-108).
tilings: recursivity and regularity. we establish a first step towards a "rice theorem" for tilings: for non-trivial sets, it is undecidable to know whether two different tile sets produce the same tilings of the plane. then, we study quasiperiodicity functions associated with tilings. this function is a way to measure the regularity of tilings. we prove that, not only almost all recursive functions can be obtained as quasiperiodicity functions, but also, a function which overgrows any recursive function.
derivatives of rational expressions and related theorems. our aim is to study the set of k-rational expressions describing rational series. more precisely we are concerned with the definition of quotients of this set by coarser and coarser congruences which lead to an extension--in the case of multiplicities--of some classical results stated in the boolean case. in particular, multiplicity analogues of the well known theorems of brzozowski and antimirov are provided.
synchronization of musical words. we study the synchronization of musical sequences by means of an operation defined on finite or infinite words called superimposition. this operation can formalize basic musical structures such as melodic canons and serial counterpoint. in the case of circular canons, we introduce the superimposition of infinite words, and we present an enumeration algorithm involving lyndon words, which appear to be a useful tool for enumerating periodic musical structures. we also define the superimposition of finite words, the superimposition of languages, and the iterated superimposition of a language, which is applied to the study of basic aspects of serial music. this leads to the study of closure properties of rational languages of finite words under superimposition and iterated superimposition. the rationality of the transduction associated with the superimposition appears to be a powerful argument in the proof of these properties. since the superimposition of finite words is the max operation of a sup-semilattice, the last section addresses the link between the rationality of a sup-semilattice operation and the rationality of the order relation associated with it.
the structure of a linear chip firing game and related models. in this paper, we study the dynamics of sand grains falling in sand piles. usually sand piles are characterized by a decreasing integer partition and grain moves are described in terms of transitions between such partitions. we study here four main transition rules. the worst classical one, introduced by brylawski (discrete math. 6 (1973) 201) induces a lattice structure lb(n) (called dominance ordering) between decreasing partitions of a given integer n. we prove that a more restrictive transition rule, called spm rule, induces a natural partition of lb(n) in suborders, each one is associated to a fixed point for the spm rule. in the second part, we extend the spm rule in a natural way and obtain a model called linear chip firing game (theoret. comput. sci. 115 (1993) 321). we prove that this new model has interesting properties: the induced order is a lattice, a natural greedoid can be associated to the model and it also defines a strongly convergent game. in the last section, we generalize the spm rule in another way and obtain other lattice structure parametrized by some , denoted by l(n,), which form a decreasing sequence of lattices when varies in [n+2,n]. for each , we characterize the fixed point of l(n,) and give the value of its maximal sized chain's length. we also note that l(n,n+2) is the lattice of all compositions of n.
modeling and querying biomolecular interaction networks. we introduce a formalism to represent and analyze protein-protein and protein-dna interaction networks. we illustrate the expressivity of this language, by proposing a formal counterpart of kohn's compilation on the mammalian cell-cycle control. this effectively turns an otherwise static knowledge into a discrete transition system incorporating a qualitative description of the dynamics. we then propose to use the computation tree logic (ctl) as a query language for querying the possible behaviors of the system. we provide examples of biologically relevant queries expressed in ctl about the mammalian cell-cycle control and show the effectiveness of symbolic model checking tools to evaluate ctl queries in this context.
optimizing stable in-place merging. in 2000, geffert et al. (theoret. comput. sci. 237 (2000) 159) presented an asymptotically efficient algorithm for stable merging in constant extra space. the algorithm requires at most m1(t + 1) + m2/2t + o(m1) comparisons (t = ⌊log2(m2/m1)⌋) and 5m2 + 12m1 + o(m1) moves, where m1 and m2 are the sizes of two ordered sublists to be merged, and m1 ≤ m2. this paper optimizes the algorithm. the optimized algorithm is simpler than their algorithm, and makes at most m1(t + 1) + m2/2t + o(m1 + m2) comparisons and 6m2 + 7m1 + o(m1 + m2) moves.
a fixpoint theory for non-monotonic parallelism. this paper studies parallel recursion. the trace specification language used in this paper incorporates sequentially, nondeterminism, reactiveness (including infinite traces), three forms of parallelism (including conjunctive, fair-interleaving and synchronous parallelism) and general recursion. in order to use tarski's theorem to determine the fixpoints of recursions, we need to identify a well-founded partial order. several orders are considered, including a new order called the lexical order, which tends to simulate the execution of a recursion in a similar manner as the egli-milner order. a theorem of this paper shows that no appropriate order exists for the language. tarski's theorem alone is not enough to determine the fixpoints of parallel recursions. instead of using tarski's theorem directly, we reason about the fixpoints of terminating and nonterminating behaviours separately. such reasoning is supported by the laws of a new composition called partition. we propose a fixpoint technique called the partitioned fixpoint, which is the least fixpoint of the nonterminating behaviours after the terminating behaviours reach their greatest fixpoint. the surprising result is that although a recursion may not be lexical-order monotonic, it must have the partitioned fixpoint, which is equal to the least lexical-order fixpoint. since the partitioned fixpoint is well defined in any complete lattice, the results are applicable to various semantic models. existing fixpoint techniques simply become special cases of the partitioned fixpoint. for example, an egli-milner-monotonic recursion has its least egli-milner fixpoint, which can be shown to be the same as the partitioned fixpoint. the new technique is more general than the least egli-milner fixpoint in that the partitioned fixpoint can be determined even when a recursion is not egli-milner monotonic. examples of non-monotonic recursions are studied. their partitioned fixpoints are shown to be consistent with our intuition.
divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures. an elementary approach is given to studying the recurrence relations associated with generalized heaps (or d-heaps), cost of optimal merge, and generalized divide-and-conquer minimization problems. we derive exact formulae for the solutions of all such recurrences and give some applications. in particular, we present a precise probabilistic analysis of floyd's algorithm for constructing d-heaps when the input is randomly given. a variant of d-heap having some interesting combinatorial properties is also introduced.
the best expert versus the smartest algorithm. in this paper, we consider the problem of online prediction using expert advice. under different assumptions, we give tight lower bounds on the gap between the best expert and any online algorithm that solves the problem.
approximations for steiner trees with minimum number of steiner points. given n terminals in the euclidean plane and a positive constant, find a steiner tree interconnecting all terminals with the minimum number of steiner points such that the euclidean length of each edge is no more than the given positive constant. this problem is np-hard with applications in vlsi design, wdm optical networks and wireless communications. in this paper, we show that (a) the steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions.
on miniaturized problems in parameterized complexity theory. we introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. we develop parts of the basic theory of miniaturizations. using the appropriate logical formalism, we show that the miniaturization of a definable problem in w[t] lies in w[t], too. in particular, the miniaturization of the dominating set problem is in w[2]. furthermore, we investigate the relation between f(k)ċno(k) time and subexponential time algorithms for the dominating set problem and for the clique problem.
machine-based methods in parameterized complexity theory. we give machine characterizations of most parameterized complexity classes, in particular, of w[p], of the classes of the w-hierarchy, and of the a-hierarchy. for example, we characterize w[p] as the class of all parameterized problems decidable by a nondeterministic fixed-parameter tractable algorithm whose number of nondeterministic steps is bounded in terms of the parameter. the machine characterizations suggest the introduction of a hierarchy wfunc between the w- and the a-hierarchy. we study the basic properties of this hierarchy.
a space-efficient algorithm for sequence alignment with inversions and reversals. a dynamic programming algorithm to find an optimal alignment for a pair of dna sequences has been described by schöniger and waterman. the alignments use not only substitutions, insertions, and deletions of single nucleotides, but also inversions, which are the reversed complements, of substrings of the sequences. with the restriction that the inversions are pairwise non-intersecting, their proposed algorithm runs in o(n2m2) time and consumes o(n2m2) space, where n and m are the lengths of the input sequences, respectively. we develop a space-efficient algorithm to compute such an optimal alignment which consumes only o(nm) space within the same amount of time. our algorithm enables the computation for a pair of dna sequences of length up to 10,000 to be carried out on an ordinary desktop computer. simulation study is conducted to verify some biological facts about gene shuffling across species.
approximation algorithms for nmr spectral peak assignment. we study a constrained bipartite matching problem where the input is a weighted bipartite graph g = (u, v, e), u is a set of vertices following a sequential order, v is another set of vertices partitioned into a collection of disjoint subsets, each following a sequential order, and e is a set of edges between u and v with non-negative weights. the objective is to find a matching in g with the maximum weight that satisfies the given sequential orders on both u and v, i.e. if ui+1 follows ui in u and if vj+1 follows vj in v, then ui is matched with vj if and only if ui+1 is matched with vj+1. the problem has recently been formulated as a crucial step in an algorithmic approach for interpreting nmr spectral data (ieee comput sci. eng. 4 (2002) 50-62). the interpretation of nmr spectral data is known as a key problem in protein structure determination via nmr spectroscopy. unfortunately, the constrained bipartite matching problem is np-hard (ieee comput. sci. eng. 4 (2002) 50-62). we first propose a 2-approximation algorithm for the problem, which follows directly from the recent result of bar-noy et al. (proc. 32nd acm symp. on theory of computing (stoc'00), 2000, pp. 735 -744) on interval scheduling. however, our extensive experimental results on real nmr spectral data illustrate that the algorithm perform poorly in terms of recovering target-matching edges. we then propose another approximation algorithm that tries to take advantage of the "density" of the sequential order information in v. although we are only able to prove an approximation ratio of 3 log2d for this algorithm, where d is the length of a longest string in v, the experimental results demonstrate that this new algorithm performs much better on real data, i.e. it is able to recover a large fraction of target-matching edges and the weight of its output matching is often in fact close to the maximum. we also prove that the problem is max snp-hard, even if the input bipartite graph is unweighted. we further present an approximation algorithm for a nontrivial special case that breaks the ratio 2 barrier.
on approximating minimum vertex cover for graphs with perfect matching. it has been a challenging open problem whether there is a polynomial time approximation algorithm for the vertex cover problem whose approximation ratio is bounded by a constant less than 2. in this paper, we study the vertex cover problem on graphs with perfect matching (shortly, vc-pm). we show that if the vc-pm problem has a polynomial time approximation algorithm with approximation ratio bounded by a constant less than 2, then so does the vertex cover problem on general graphs. approximation algorithms for vc-pm are developed, which induce improvements over previously known algorithms on sparse graphs. for example, for graphs of average degree 5, the approximation ratio of our algorithm is 1.414, compared with the previously best ratio 1.615 by halldórsson and radhakrishnan.
an efficient algorithm to find a double-loop network that realizes a given l-shape. double-loop networks have been widely studied as an architecture for local area networks. it is well known that the minimum distance diagram of a double-loop network yields an l-shape. given a positive integer n, it is desirable to find a double-loop network with its diameter being the minimum among all double-loop networks with n nodes. since the diameter of a double-loop network can be easily computed from its l-shape, one method is to start with a desirable l-shape and then find a double-loop network to realize it. this is a problem discussed by many authors [f. aguiló, m.a. fiol, an efficient algorithm to find optimal double loop networks, discrete math. 138 (1995) 15-29, r.c. chan, c.y. chen, z.x. hong, a simple algorithm to find the steps of double-loop networks, discrete appl. math. 121 (2002) 61-72, c.y. chen, f.k. hwang, the minimum distance diagram of double-loop networks, ieee trans. comput. 49 (2000) 977-979, p. esqué, f. aguiló, m.a. fiol, double commutative-step diagraphs with minimum diameters, discrete math. 114 (1993) 147-157] and it has been open for a long time whether this problem can be solved in o(log n) time. in this paper, we will provide a simple and efficient o(log n)-time algorithm for solving this problem.
a coalgebraic approach to kleene algebra with tests. kleene algebra with tests is an extension of kleene algebra, the algebra of regular expressions, which can be used to reason about programs. we develop a coalgebraic theory of kleene algebra with tests, along the lines of the coalgebraic theory of regular expressions based on deterministic automata. since the known automata-theoretic presentation of kleene algebra with tests does not lend itself to a coalgebraic theory, we define a new interpretation of kleene algebra with tests expressions and a corresponding automata-theoretic presentation. one outcome of the theory is a coinductive proof principle, that can be used to establish equivalence of our kleene algebra with tests expressions.
robust algorithms for constructing strongly convex hulls in parallel. given a set s of n points in the plane, an ε-strongly convex δ-hull of s is defined as a convex polygon p with the vertices taken from s such that no point of s lies farther than δ outside p and such that even if the vertices of p are perturbed by as much as ε, p remains convex. this paper presents the first parallel robust method for this generalized convex hull problem (note that the convex hull of s is the 0-strongly convex 0-hull of s). we show that an ε-strongly convex o(ε + β)-hull of s can be constructed in o(log3n) time using n processors with imprecise computations, where β is the error unit of primitive operations. this result also implies an improved sequential algorithm. our algorithm consists of two parts: (1) computing a convex o(ε + β) -hull of n points, in o(log3n) time using n processors, and (2) constructing an ε-strongly convex o(ε + β)-hull of a convex polygon with n vertices, in o(log2n) time with n processors. we also find an approximate bridge of two sets with n points each, in o(log2n) time using n processors, which we use as a subroutine. all these algorithms are fundamental and have their own applications. the parallel computational model in this paper is the erew pram.
a ptas for weight constrained steiner trees in series-parallel graphs. in this paper, we study the problem of computing a minimum cost steiner tree subject to weight constraint in a series-parallel graph where each edge has a nonnegative integer cost and a nonnegative integer weight. we present a strongly polynomial time approximation scheme for this np-complete problem.
on product covering in 3-tier supply chain models: natural complete problems for [3] and [4]. the field of supply chain management has been growing at a rapid pace in recent years, both as a research area and as a practical discipline. in this paper, we study the computational complexity of product covering problems in 3-tier supply chain models, and present natural complete problems for the classes w[3] and w[4] in parameterized complexity theory. this seems the first group of natural complete problems for higher levels in the parameterized intractability hierarchy (i.e., the w-hierarchy), and the first precise complexity characterizations of certain optimization problems in the research of supply chain management. our results also derive strong computational lower bounds and inapproximability for these optimization problems.
on the ultimate complexity of factorials. it has long been observed that certain factorization algorithms provide a way to write the product of many different integers succinctly. in this paper, we study the problem of representing the product of all integers from 1 to n (i.e. n!) by straight-line programs. formally, we say that a sequence of integers an is ultimately f(n)-computable, if there exists a nonzero integer sequence mn such that for any n, anmn can be computed by a straight-line program (using only additions, subtractions and multiplications) of length at most f(n). shub and smale [12] showed that if n! is ultimately hard to compute, then the algebraic version of np ≠ p is true. assuming a widely believed number theory conjecture concerning smooth numbers in a short interval, a subexponential upper bound (exp(c√log n log log n)) for the ultimate complexity of n! is proved in this paper, and a randomized subexponential algorithm constructing such a short straight-line program is presented as well.
semi-on-line multiprocessor scheduling with given total processing time. we are given a set of identical machines and a sequence of jobs, the sum of whose weights is known in advance. the jobs are to be assigned on-line to one of the machines and the objective is to minimize the makespan. an algorithm with performance ratio 1.6 and a lower bound of 1.5 is presented. these results improve on the recent results by azar and regev, who proposed an algorithm with performance ratio 1.625 for the less general problem that the optimal makespan is known in advance.
an improvement on a spernerity proof of horrocks. in horrocks' proof (horrocks, european journal of combinatorics 20 (1999) 131-148) of lih's conjecture about the spernerity of filters in a boolean algebra generated by 2-subsets, there are 116 exceptional graphs to be checked case by case. the details of the analysis could not be published in its entirety. in this paper we carry horrocks' method much further to reduce the exceptional cases to a manageable number. a complete examination can thus be exhibited.
multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. we consider the feasibility model of multi-agent scheduling on a single machine, where each agent's objective function is to minimize the total weighted number of tardy jobs. we show that the problem is strongly np-complete in general. when the number of agents is fixed, we first show that the problem can be solved in pseudo-polynomial time for integral weights, and can be solved in polynomial time for unit weights; then we present a fully polynomial-time approximation scheme for the problem.