共查询到20条相似文献,搜索用时 46 毫秒
1.
Given q+1 strings (a text t of length n and q patterns m1,…,mq) and a natural number w, the multiple serial episode matching problem consists in finding the number of size w windows of text t which contain patterns m1,…,mq as subsequences, i.e., for each mi, if mi=p1,…,pk, the letters p1,…,pk occur in the window, in the same order as in mi, but not necessarily consecutively (they may be interleaved with other letters). Our main contribution here is an algorithm solving this problem on-line in time O(nq) with an MP-RAM model (which is a RAM model equipped with extra operations). 相似文献
2.
Fokko J. van de Bult 《Information Processing Letters》2008,108(5):336-337
We analyze a sorting problem where for every element there is a hard upper bound on the overall number of lost comparisons: Given are n elements and n non-negative integers a1,…,an. The goal is to sort these n elements by pairwise comparisons, subject to the condition that the kth element must not be the loser (= smaller element) in more than ak of its comparisons against the other elements.We completely characterize the sequences a1,…,an for which this sorting problem can be solved. 相似文献
3.
Benjamin Doerr 《Information Processing Letters》2004,92(3):113-116
For a given sequence a=(a1,…,an) of numbers, a global rounding is an integer sequence b=(b1,…,bn) such that the rounding error |∑i∈I(ai−bi)| is less than one in all intervals I⊆{1,…,n}. We give a simple characterization of the set of global roundings of a. This allows to compute optimal roundings in time O(nlogn) and generate a global rounding uniformly at random in linear time under a non-degeneracy assumption and in time O(nlogn) in the general case. 相似文献
4.
Let A=〈a1,a2,…,am〉 and B=〈b1,b2,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai1=bj1,ai2=bj2,…,ail=bjl〉, where i1<i2<?<il and j1<j2<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space. 相似文献
5.
Neill Michael Clift 《Computing》2011,91(3):265-284
An addition chain is a finite sequence of positive integers 1 = a
0 ≤ a
1 ≤ · · · ≤ a
r
= n with the property that for all i > 0 there exists a j, k with a
i
= a
j
+ a
k
and r ≥ i > j ≥ k ≥ 0. An optimal addition chain is one of shortest possible length r denoted l(n). A new algorithm for calculating optimal addition chains is described. This algorithm is far faster than the best known
methods when used to calculate ranges of optimal addition chains. When used for single values the algorithm is slower than
the best known methods but does not require the use of tables of pre-computed values. Hence it is suitable for calculating
optimal addition chains for point values above currently calculated chain limits. The lengths of all optimal addition chains
for n ≤ 232 were calculated and the conjecture that l(2n) ≥ l(n) was disproved. Exact equality in the Scholz–Brauer conjecture l(2
n
− 1) = l(n) + n − 1 was confirmed for many new values. 相似文献
6.
Given a continuous function a on the complex unit circle, let T(a) denote the infinite Toeplitz matrix generated by a and let T
n
(a) stand for the (n+1)×(n+1) principal section of T(a). We think of T(a) and T
n
(a) as operators on l
2 spaces. A classical result by Gohberg and Feldman says that if T(a) is invertible, then so is T
n
(a) for all sufficiently large n≥n
0 and . Only in 1994 did we realize that in fact . In this paper, we provide estimates for the speed with which
converges to . We prove that in the “generic case” the convergence speed can be estimated by the smoothness of a, whereas in some “exceptional cases” (e.g., if T(a) is Hermitian or triangular) it is not the smoothness of $a$ but the orders of certain zeros which determine the convergence
speed. Some of the results are extended to operators on l
p
spaces.
Received: September 1998 / Accepted: November 1998 相似文献
7.
We describe a randomized algorithm that, given an integer a, produces a certificate that the integer is not a pure power of an integer in expected (log a)1+o(1) bit operations under the assumption of the Generalized Riemann Hypothesis. The certificate can then be verified in deterministic
(log a)1+o(1) time. The certificate constitutes for each possible prime exponent p a prime number qp, such that a mod qp is a pth non-residue. We use an effective version of the Chebotarev density theorem to estimate the density of such prime numbers
qp. 相似文献
8.
The asymptotic and oscillatory behavior of solutions of some general second-order nonlinear difference equations of the form is studied. Oscillation criteria for their solutions, when “pn” is of constant sign, are established. Results are also presented for the damped-forced equation Examples are inserted in the text for illustrative purposes. 相似文献
δ(anh(yn+1)δyn)+pnδyn+qn+1f(yσ(n+1))=0 nZ,
δ(anh(yn+1)δyn)+pnδyn+qn+1f(yσ(n+1))=en nZ.
9.
In this paper, we study the complexity of deciding readiness and failure equivalences for finite state processes and recursively defined processes specified by normed context-free grammars (CFGs) in Greibach normal form (GNF). The results are as follows: (1) Readiness and failure equivalences for processes specified by normed GNF CFGs are both undecidable. For this class of processes, the regularity problem with respect to failure or readiness equivalence is also undecidable. Moreover, all these undecidability results hold even for locally unary processes. In the unary case, these problems become decidable. In fact, they are Πp2-complete, We also show that with respect to bisimulation equivalence, the regularity for processes specified by normed GNF CFGs is NL-complete. (2) Readiness and failure equivalences for finite state processes are PSPACE-complete. This holds even for locally unary finite state processes. These two equivalences are co-NP-complete for unary finite state processes. Further, for acyclic finite state processes, readiness and failure equivalences are co-NP-complete and they are NL-complete in the unary case. (3) For finite tree processes, we show that finite trace, readiness, and failure equivalences are all L-complete. Further, the results remain true for the unary case. Our results provide a complete characterization of the computational complexity of deciding readiness and failure equivalences for several important classes of processes. 相似文献
10.
11.
The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying
the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood
is empty.
For β≥1, this neighborhood of a pair of points p
i
,p
j
is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p
i
+(β/2)p
j
and (β/2)p
i
+(1−β/2)p
j
, respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p
i
and p
j
.
In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l
1 and l
∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n
5/2logn) [7].
Received April 26, 2000 相似文献
12.
This paper is concerned with the partial difference equation Am+1,n+Am,n+1−Am,n+pm,nAm−k,n−l=0,m,n=0,1,2,…,, where k and l are two positive integers, {pm,n} is a real double sequence. Some new oscillation criteria for this equation are obtained. 相似文献
13.
Giuliano G. La Guardia 《Quantum Information Processing》2012,11(2):591-604
Two new families of asymmetric quantum codes are constructed in this paper. The first one is derived from the Calderbank-Shor-Steane
(CSS) construction applied to classical Reed-Solomon (RS) codes, providing quantum codes with parameters [[N = l(q
l
−1), K = l(q
l
−2d + c + 1), d
z
≥ d/d
x
≥ (d−c)]]
q
, where q is a prime power and d > c + 1, c ≥ 1, l ≥ 1 are integers. The second family is derived from the CSS construction applied to classical generalized RS codes, generating
quantum codes with parameters [[N = mn, K = m(2k−n + c), d
z
≥ d/d
x
≥ (d−c)]]
q
, where q is a prime power, 1 < k < n < 2k + c ≤ q
m
, k = n − d + 1, and n, d > c + 1, c ≥ 1, m ≥ 1 are integers. Although the second proposed construction generalizes the first one, the techniques developed in both constructions
are slightly different. These new codes have parameters better than or comparable to the ones available in the literature.
Additionally, the proposed codes can be utilized in quantum channels having great asymmetry, that is, quantum channels in
which the probability of occurrence of phase-shift errors is large when compared to the probability of occurrence of qudit-flip
errors. 相似文献
14.
Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively, be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest common subsequence of two given strings X and Y in O(kl+min{p1,p2}) time, where p1 and p2 denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. It improves the previously known time bound O(min{nl,km}) and outperforms the time bounds O(kllogkl) or O((k+l+q)log(k+l+q)) for some cases, where q denotes the number of matched blocks. 相似文献
15.
Givenn numbersa
0,a
1,...,a
n
–1, it is required to compute all sums of the forma
0+a
1+...+a
i
, fori=0, 1,...,n–1. This problem arises in many applications and is trivial to solve sequentially in O(n) time. Besides its practical importance, the problem gains an additional theoretical interest in parallel computation. A technique known asrecursive doubling allows all sums to be computed in O(logn) time on a model of computation wheren processors communicate through aninverse perfect suffle interconnection network. In this paper we show how the problem can be solved on a simple network, namely abinary tree of processors. In addition, we show how to extend our solution to obtain an optimal-cost algorithm. The algorithm usesp processors and runs in O((n/p)+logp) time, for a cost of O(n+p logp). This cost is optimal whenp logp=O(n). Finally, two applications of our results are illustrated, namely job scheduling with deadlines and the knapsack problem.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grants A0282 and A3336. 相似文献
16.
B. Steinsky 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2003,7(5):350-356
We use an adaptation of the Prüfer code for trees to encode labeled directed acyclic graphs, which are often abbreviated
to DAGs (or ADGs). In this paper, each DAG is assigned a unique DAG code, which allows an easy handling for several purposes.
The set of all possible DAG codes (and therefore the set of all DAGs) for a fixed number of n vertices can be generated efficiently. Furthermore, we are able to rank DAGs, i.e., we provide an algorithm that assigns
every DAG a unique number in the set {0,…,a
n
−1}, where a
n
is the cardinality of the set of labeled DAGs with n≥1 vertices, and we are able to unrank DAGs, which is the inverse operation. We also gain recurrence relations, which can
be used to calculate a
n
and a
n,q
, i.e., the number of DAGs with n vertices and q edges. Finally, it is possible to generate, enumerate, rank and unrank DAGs with given number of edges and also DAGs with
bounded indegree.
RID="*"
ID="*" This research was supported by the Austrian Science Fund (FWF), P13261-INF.
I want to thank the reviewers, specially the one who suggested to add the algorithm for unranking DAG codes, for reading
the paper very carefully and for the helpful comments. 相似文献
17.
Adam Strzeboński 《Journal of Symbolic Computation》2011,46(11):1284-1290
We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f1(x),…,fm(x),y1,…,yn), where p∈Q[x,t1,…,tm,y1,…,yn] and f1(x),…,fm(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f1(x),…,fm(x)]. In particular, the algorithm applies when f1(x),…,fm(x) are real exp-log functions or tame elementary functions. 相似文献
18.
《Computers & Mathematics with Applications》2002,43(8-9):951-964
We construct an important transform to obtain sufficient conditions for the oscillation of all solutions of delay partial difference equations with positive and negative coefficients of the form Am+1,n + Am,n+1 − Amn + pmnAm−k−1 − qmnAm−k′,n−l′ = 0, where m, n = 0, 1, …, and k, k′, l′, l are nonnegative integers, p, q ϵ (0, ∞), the coefficients {qmn} and {pmn} are sequences of nonnegative real numbers. 相似文献
19.
Jan Krají?ek 《Information Processing Letters》2007,101(4):163-167
We prove that there is a polynomial time substitution (y1,…,yn):=g(x1,…,xk) with k?n such that whenever the substitution instance A(g(x1,…,xk)) of a 3DNF formula A(y1,…,yn) has a short resolution proof it follows that A(y1,…,yn) is a tautology. The qualification “short” depends on the parameters k and n. 相似文献
20.
This work studies consensus strategies for networks of agents with limited memory, computation, and communication capabilities. We assume that agents can process only values from a finite alphabet, and we adopt the framework of finite fields, where the alphabet consists of the integers {0,…,p−1}, for some prime number p, and operations are performed modulo p. Thus, we define a new class of consensus dynamics, which can be exploited in certain applications such as pose estimation in capacity and memory constrained sensor networks. For consensus networks over finite fields, we provide necessary and sufficient conditions on the network topology and weights to ensure convergence. We show that consensus networks over finite fields converge in finite time, a feature that can be hardly achieved over the field of real numbers. For the design of finite-field consensus networks, we propose a general design method, with high computational complexity, and a network composition rule to generate large consensus networks from smaller components. Finally, we discuss the application of finite-field consensus networks to distributed averaging and pose estimation in sensor networks. 相似文献