Substring Range Reporting

We revisit various string indexing problems with range reporting features, namely, position-restricted substring searching, indexing substrings with gaps, and indexing substrings with intervals. We obtain the following main results.

• We give efficient reductions for each of the above problems to a new problem, which we call substring range reporting. Hence, we unify the previous work by showing that we may restrict our attention to a single problem rather than studying each of the above problems individually.
• We show how to solve substring range reporting with optimal query time and little space. Combined with our reductions this leads to significantly improved time-space trade-offs for the above problems. In particular, for each problem we obtain the first solutions with optimal time query and O(nlog ^O(1) n) space, where n is the length of the indexed string.
• We show that our techniques for substring range reporting generalize to substring range counting and substring range emptiness variants. We also obtain non-trivial time-space trade-offs for these problems.

Our bounds for substring range reporting are based on a novel combination of suffix trees and range reporting data structures. The reductions are simple and general and may apply to other combinations of string indexing with range reporting.     

Sparse LCS Common Substring Alignment

The “Common Substring Alignment” problem is defined as follows. The input consists of a set of strings S₁,S₂…,S_c, with a common substring appearing at least once in each of them, and a target string T. The goal is to compute similarity of all strings S_i with T, without computing the part of the common substring over and over again.In this paper we consider the Common Substring Alignment problem for the LCS (Longest Common Subsequence) similarity metric. Our algorithm gains its efficiency by exploiting the sparsity inherent to the LCS problem. Let Y be the common substring, n be the size of the compared sequences, L_y be the length of the LCS of T and Y, denoted |LCS[T,Y]|, and L be max{|LCS[T,S_i]|}. Our algorithm consists of an O(nL_y) time encoding stage that is executed once per common substring, and an O(L) time alignment stage that is executed once for each appearance of the common substring in each source string. The additional running time depends only on the length of the parts of the strings that are not in any common substring.     

Intractability results in predicate detection

It has been shown that global predicate detection in a distributed computation is an NP-complete problem in general. However, efficient predicate detection algorithms exist for some subclasses of predicates, such as stable predicates, observer-independent predicates, conjunctions of local predicates, channel predicates, etc. We show here that the problem of deciding whether a given predicate is a member of any of these tractable subclasses is NP-hard in general.We also explore the tractability of linear and regular predicates. In particular, we show that, unless RP=NP, there is no polynomial-time algorithm to detect for linear and regular predicates B.     

The Noisy Substring Matching Problem

Let T(U) be the set of words in the dictionary H which contains U as a substring. The problem considered here is the estimation of the set T(U) when U is not known, but Y, a noisy version of U is available. The suggested set estimate S*(Y) of T(U) is a proper subset of H such that its every element contains at least one substring which resembles Y most according to the Levenshtein metric. The proposed algorithm for-the computation of S*(Y) requires cubic time. The algorithm uses the recursively computable dissimilarity measure Dk(X, Y), termed as the kth distance between two strings X and Y which is a dissimilarity measure between Y and a certain subset of the set of contiguous substrings of X. Another estimate of T(U), namely SM(Y) is also suggested. The accuracy of SM(Y) is only slightly less than that of S*(Y), but the computation time of SM(Y) is substantially less than that of S*(Y). Experimental results involving 1900 noisy substrings and dictionaries which are subsets of 1023 most common English words [11] indicate that the accuracy of the estimate S*(Y) is around 99 percent and that of SM(Y) is about 98 percent.     

求最长公共子串问题的算法分析

高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键.文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多.最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间.     

Intractability of min- and max-cut in streaming graphs

We show that the exact computation of a minimum or a maximum cut of a given graph G is out of reach for any one-pass streaming algorithm, that is, for any algorithm that runs over the input stream of G's edges only once and has a working memory of o(n²) bits. This holds even if randomization is allowed.     

具有子串检索功能的可扩展分布式数据结构

EH*S是可扩展分布式数据结构EH*的一个改进，增加了子串检索功能。通过对子串和关键字计算描述符向量，为EH*文件中的每个桶添加一个桶描述符向量，然后把子串描述符向量分别与关键字和桶的描述符向量进行比较，得到包含子串的关键字集。     

Substring search and repeat search using factor oracles

We present some simple but useful properties of factor oracles, and propose fast algorithms for indexed full-text search and finding repeated substrings. Some experiments are given to demonstrate the performance of our algorithms.     

Practical Intractability: A Critique of the Hypercomputation Movement

For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical realizability of specific models in order to demonstrate this, these arguments lack the generality to be a satisfactory justification against the construction of any information-processing machine that computes beyond the universal Turing machine. To this end, I present a more mathematically concrete challenge to hypercomputability, and will show that one is immediately led into physical impossibilities, thereby demonstrating the infeasibility of hypercomputers more generally. This gives impetus to propose and justify a more plausible starting point for an extension to the classical paradigm that is physically possible, at least in principle. Instead of attempting to rely on infinities such as idealized limits of infinite time or numerical precision, or some other physically unattainable source, one should focus on extending the classical paradigm to better encapsulate modern computational problems that are not well-expressed/modeled by the closed-system paradigm of the Turing machine. I present the first steps toward this goal by considering contemporary computational problems dealing with intractability and issues surrounding cyber-physical systems, and argue that a reasonable extension to the classical paradigm should focus on these issues in order to be practically viable.     

Parameterized Programming

Parameterized programming is a powerful technique for the reliable reuse of software. In this technique, modules are parameterized over very general interfaces that describe what properties of an environment are required for the module to work correctly. Reusability is enhanced by the flexibility of the parameterization mechanism proposed here. Reliability is further enhanced by permitting interface requirements to include more than purely syntactic information. This paper introduces three new ideas that seem especially useful in supporting parameterized programming: 1) theories, which declare global properties of program modules and interfaces; 2) views, which connect theories with program modules in an elegant way; and 3) module expressions, a kind of general structured program transformation which produces new modules by modifying and combining existing modules. Although these ideas are illustrated with some simple examples in the OBJ programming language, they should also be taken as proposals for an Ada¹ library system, for adding modules to Prolog, and as considerations for future language design efforts. OBJ is an ultra-high level programming language, based upon rewrite rules, that incorporates these ideas, and many others from modern programming methodology.     

Parameterized Random Complexity

The classes W[P] and W[1] are parameterized analogues of NP in that they can be characterized by machines with restricted existential nondeterminism. These machine characterizations give rise to two natural notions of parameterized randomized algorithms that we call W[P]-randomization and W[1]-randomization. This paper develops the corresponding theory.     

Parameterized Proof Complexity

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter (we call such a formula a parameterized contradiction). One could separate the parameterized complexity classes FPT and W[SAT] by showing that there is no fpt-bounded parameterized proof system for parameterized contradictions, i.e., that there is no proof system that admits proofs of size f(k)n ^O(1) where f is a computable function and n represents the size of the propositional formula. By way of a first step, we introduce the system of parameterized tree-like resolution and show that this system is not fpt-bounded. Indeed, we give a general result on the size of shortest tree-like resolution proofs of parameterized contradictions that uniformly encode first-order principles over a universe of size n. We establish a dichotomy theorem that splits the exponential case of Riis’s complexity gap theorem into two subcases, one that admits proofs of size f(k)n ^O(1) and one that does not. We also discuss how the set of parameterized contradictions may be embedded into the set of (ordinary) contradictions by the addition of new axioms. When embedded into general (DAG-like) resolution, we demonstrate that the pigeonhole principle has a proof of size 2 ^k n ². This contrasts with the case of tree-like resolution where the embedded pigeonhole principle falls into the “non-FPT” category of our dichotomy.     

Parameterized gait synthesis

This article presents a method of producing gaits by using control mechanisms analogous to windup toys. The synthesis technique is based on optimization. One of the primary characteristics of “virtual windup toys” is that they are oblivious to their environment. This means that these creatures or simulated toys have no active control over balance. Nevertheless, “blind” parameterized control mechanisms can produce many common periodic gaits as well as aperiodic motions such as turns and leaps. The possibilities and limitations of this technique are presented in the context of example creatures having one, two, four, and six legs. An important attribute of the proposed synthesis method is that the motions produced can be parameterized. Thus, you can synthesize a family of motions instead of just a single fixed instance of a motion. The examples used here are: a hopping gait parameterized with respect to speed; a turning walk parameterized with respect to the turning rate, and a leap parameterized with respect to the size of the leap. The animator can thus interactively specify the hopping speed, turning rate, and leap size, respectively, for these physics-based motions     

Parameterized pursuit-evasion games

We study the parameterized complexity of four variants of pursuit-evasion on graphs: Seeded Pursuit Evasion, Short Seeded Pursuit Evasion, Directed Pursuit Evasion and Short Directed Pursuit Evasion. Both Seeded Pursuit Evasion and Short Seeded Pursuit Evasion are played on undirected graphs with given starting positions for both the cops and the robber. Directed Pursuit Evasion and its short variant are played on directed graphs, with the players free to choose their starting positions. We show for Seeded Pursuit Evasion and Directed Pursuit Evasion that finding a winning strategy for the cops is AW[*]-hard when we parameterize by the number of cops. Further, we show that the short (k-move) variants of these problems (Short Seeded Pursuit Evasion and Short Directed Pursuit Evasion) are AW[*]-complete when we parameterize by both the number of cops and turns.     

Parameterized Modal Satisfiability

We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the problem??s combinatorial explosion, beyond the number of propositional variables v. To this end we study the modality depth, a natural measure which has appeared in the literature, and show that, even though modal satisfiability parameterized by v and the modality depth is FPT, the running time??s dependence on the parameters is a tower of exponentials (unless P = NP). To overcome this limitation we propose possible alternative parameters, namely diamond dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder (doubly and singly exponential respectively) than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times. We also give lower bound arguments which prove that our algorithms cannot be improved significantly unless the Exponential Time Hypothesis fails.     

Parameterized complexity of firefighting

The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be placed on an unburned vertex, permanently protecting it, and the fire spreads to all neighboring unprotected vertices of burning vertices. The goal is to let as few vertices burn as possible. In this paper, we consider a generalization of this problem, where at each time step b?1$b?1$ firefighters can be deployed. Our results answer several open questions raised by Cai et al. [8]. We show that this problem is W[1]-hard when parameterized by the number of saved vertices, protected vertices, and burned vertices. We also investigate several combined parameterizations for which the problem is fixed-parameter tractable. Some of our algorithms improve on previously known algorithms. We also establish lower bounds to polynomial kernelization.