Multiple serial episodes matching

Given q+1 strings (a text t of length n and q patterns m₁,…,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 m₁,…,mq as subsequences, i.e., for each mi, if mi=p₁,…,pk, the letters p₁,…,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).     

The problem of the moody chess players

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 a₁,…,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 a₁,…,an for which this sorting problem can be solved.     

Global roundings of sequences

For a given sequence a=(a₁,…,an) of numbers, a global rounding is an integer sequence b=(b₁,…,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.     

A fast algorithm for computing a longest common increasing subsequence

Let A=〈a₁,a₂,…,am〉 and B=〈b₁,b₂,…,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 〈ai₁=bj₁,ai₂=bj₂,…,ail=bjl〉, where i₁<i₂<?<il and j₁<j₂<?<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.     

Calculating optimal addition chains

An addition chain is a finite sequence of positive integers 1 = a ₀ ≤ a ₁ ≤ · · · ≤ 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 ≤ 2³² were calculated and the conjecture that l(2n) ≥ l(n) was disproved. Exact equality in the Scholz–Brauer conjecture l(2 ⁿ − 1) = l(n) + n − 1 was confirmed for many new values.     

Convergence speed estimates for the norms of the inverses of large truncated Toeplitz matrices

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 ² 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 ₀ 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     

Efficiently Certifying Non-Integer Powers

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 q_p, such that a mod q_p is a p^th non-residue. We use an effective version of the Chebotarev density theorem to estimate the density of such prime numbers q_p.     

Asymptotic and oscillatory behavior of solutions of general nonlinear difference equations of second order

The asymptotic and oscillatory behavior of solutions of some general second-order nonlinear difference equations of the form

δ(a_nh(y_n+1)δy_n)+p_nδy_n+q_n+1f(y_σ(n+1))=0 nZ,

is studied. Oscillation criteria for their solutions, when “p_n” is of constant sign, are established. Results are also presented for the damped-forced equation

δ(a_nh(y_n+1)δy_n)+p_nδy_n+q_n+1f(y_σ(n+1))=e_n nZ.

Examples are inserted in the text for illustrative purposes.     

On Deciding Readiness and Failure Equivalences for Processes

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 Π^p₂-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.     

Output-Sensitive Algorithm for Computing β-Skeletons

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 ₁ 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     

Further oscillation criteria for delay partial difference equations

This paper is concerned with the partial difference equation A_m+1,n+A_m,n+1−A_m,n+p_m,nA_m−k,n−l=0,m,n=0,1,2,…,, where k and l are two positive integers, {p_m,n} is a real double sequence. Some new oscillation criteria for this equation are obtained.     

Asymmetric quantum Reed-Solomon and generalized Reed-Solomon codes

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.     

A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

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{p₁,p₂}) time, where p₁ and p₂ 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.     

Optimal computation of prefix sums on a binary tree of processors

Givenn numbersa ₀,a ₁,...,a _n –1, it is required to compute all sums of the forma ₀+a ₁+...+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.     

Efficient coding of labeled directed acyclic graphs

 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.     

Cylindrical decomposition for systems transcendental in the first variable

We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f₁(x),…,f_m(x),y₁,…,y_n), where p∈Q[x,t₁,…,t_m,y₁,…,y_n] and f₁(x),…,f_m(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f₁(x),…,f_m(x)]. In particular, the algorithm applies when f₁(x),…,f_m(x) are real exp-log functions or tame elementary functions.     

Oscillatory behavior of delay partial difference equations with positive and negative coefficients

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 A_m+1,n + A_m,n+1 − A_mn + p_mnA_m−k−1 − q_mnA_{m−k′,n−l′} = 0, where m, n = 0, 1, …, and k, k′, l′, l are nonnegative integers, p, q ϵ (0, ∞), the coefficients {q_mn} and {p_mn} are sequences of nonnegative real numbers.     

Substitutions into propositional tautologies

We prove that there is a polynomial time substitution (y₁,…,yn):=g(x₁,…,xk) with k?n such that whenever the substitution instance A(g(x₁,…,xk)) of a 3DNF formula A(y₁,…,yn) has a short resolution proof it follows that A(y₁,…,yn) is a tautology. The qualification “short” depends on the parameters k and n.     

Consensus networks over finite fields

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}$\{0,\dots ,p-1\}$, for some prime number p$p$, and operations are performed modulo p$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.