this paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the othe...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
this paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in polynomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop combinatorial algorithms that solve these problems in O(n(4) log n) time with O(n(3)) space, and in O(n(4)) time with O(n(2)) space, respectively, where n is the size of the input SLP-compressed strings.
this book constitutes the refereed proceedings of the 24th Seminar on currenttrends in theory and practice of Informatics, SOFSEM'97, held in Milovy, Czech Republic, in November 1997. SOFSEM is special in being a...
详细信息
ISBN:
(数字)9783540696452
ISBN:
(纸本)9783540637745
this book constitutes the refereed proceedings of the 24th Seminar on currenttrends in theory and practice of Informatics, SOFSEM'97, held in Milovy, Czech Republic, in November 1997. SOFSEM is special in being a mix of a winter school, an international conference, and an advanced workshop meeting the demand for ongoing education in the area of computerscience. the volume presents 22 invited contributions by leading experts together with 24 revised contributed papers selected from 63 submissions. the invited presentations are organized in topical sections on foundations, distributed and parallel computing, software engineering and methodology, and databases and information systems.
In [2], Backofen et al. propose the MRSO problem, that is to compute an mRNA sequence of maximal similarity to a given rnRNA and a given protein, that additionally satisfies some secondary structure constraints. the s...
详细信息
ISBN:
(纸本)3540207791
In [2], Backofen et al. propose the MRSO problem, that is to compute an mRNA sequence of maximal similarity to a given rnRNA and a given protein, that additionally satisfies some secondary structure constraints. the study of this problem is motivated by an application in the area of protein engineering. Modeled in a mathematical framework, we would like to compute a string s is an element of {a, b, (a) over bar, (b) over bar}(3n) which maximizes the sum of the values of n functions, which are blockwise applied to triples of s, and additionally satisfies some complementary constraints on the characters of s given in terms of position pairs. While the decision version of this problem is known to be NP-complete (see [2]), we prove here the APX-hardness of the general as well as of a restricted version of the problem. Moreover, we attack the problem by proposing a 4-approximation algorithm.
Boosting algorithms are procedures that "boost" low accuracy weak learning algorithms to achieve arbitrarily high accuracy. Over the past decade boosting has been widely used in practice and has become a maj...
详细信息
Boosting algorithms are procedures that "boost" low accuracy weak learning algorithms to achieve arbitrarily high accuracy. Over the past decade boosting has been widely used in practice and has become a major research topic in computational learning theory. In this paper we study boosting in the presence of random classification noise, giving both positive and negative results. We show that a modified version of a boosting algorithm due to Mansour and McAllester can achieve accuracy arbitrarily close to the noise rate. We also give a matching lower bound by showing that no efficient black-box boosting algorithm can boost accuracy beyond the noise rate (assuming that one-way functions exist). Finally, we consider a variant of the standard scenario for boosting in which the "weak learner" satisfies a slightly stronger condition than the usual weak learning guarantee. We give an efficient algorithm in this framework which can boost to arbitrarily high accuracy in the presence of classification noise.
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressi...
详细信息
ISBN:
(纸本)9783031521126;9783031521133
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressions, called COVER BY ARIthMETIC PROGRESSIONS (CAP) and EXACT COVER BY ARIthMETIC PROGRESSIONS (XCAP). In both problems, we are given a set X consisting of n integers along with an integer k, and our goal is to find k arithmetic progressions whose union is X. In XCAP we additionally require the arithmetic progressions to be disjoint. Both problems were shown to be NP-complete by Heath [IPL'90]. We present a 2(O(k2)) poly(n) time algorithm for CAP and a 2(O(k3)) poly(n) time algorithm for XCAP. We also give a fixed parameter tractable algorithm for CAP parameterized below some guaranteed solution size. We complement these findings by proving that CAP is Strongly NP-complete in the field Z(p), if p is a prime number part of the input.
this paper presents a complete account of positive and negative results on the finite axiomatizability of weak complete simulation semantics over the language BCCSP. We offer finite (un)conditional ground-complete axi...
详细信息
ISBN:
(纸本)9783642276590;9783642276606
this paper presents a complete account of positive and negative results on the finite axiomatizability of weak complete simulation semantics over the language BCCSP. We offer finite (un)conditional ground-complete axiomatizations for the weak complete simulation pre-congruence. In sharp contrast to this positive result, we prove that, in the presence of at least one observable action, the (in)equational theory of the weak complete simulation precongruence over BCCSP does not have a finite (in)equational basis. In fact, the set of (in)equations in at most one variable that hold in weak complete simulation semantics over BCCSP does not have an (in)equational basis of 'bounded depth', let alone a finite one.
the well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
the well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. this problem is known to NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP subset of coNP/poly. We prove that Disjoint Paths remains NP-complete on split graphs, and show that the problem admits a kernel with O(k(2)) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k(3)) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.
It has been recently discussed in linguistics that the notion of identity in the task of coreference resolution is of continuous nature, ranging from "complete" identity to non-identity. the current paper co...
详细信息
Fast and accurate tracking of reference trajectories is highly desirable in many nanopositioning systems,such as piezoelectric tube scanner(PTS),atomic force microscopes(AFMs) and so *** this paper,notch filter is des...
详细信息
ISBN:
(纸本)9781509009107
Fast and accurate tracking of reference trajectories is highly desirable in many nanopositioning systems,such as piezoelectric tube scanner(PTS),atomic force microscopes(AFMs) and so *** this paper,notch filter is designed to attenuate the gain at resonant *** with damping controller,notch filter is designed easier and has better ***'s more,a fast control algorithm is proposed to promote response *** attain fast and accurate control,the approach that contains notch filter and fast control algorithm is used in the practice *** results have been verified in our experimental platform and show that this method has better tracking effect compared with PID control or notch filter PID control.
We show that the interactive knapsack heuristic optimization problem is APX-hard. Moreover, we discuss the relationship between the interactive knapsack heuristic optimization problem and some other knapsack problems....
详细信息
暂无评论