Universal traversal sequences with backtracking

In this paper we introduce a new notion of traversal sequences that we call exploration sequences. Exploration sequences share many properties with the traversal sequences defined in Aleliunas et al. (Proceedings on the 20th Annual Symposium of Foundations of Computer Science, 1979, pp. 218–223), but they also exhibit some new properties. In particular, they have an ability to backtrack, and their random properties are robust under choice of the probability distribution on labels.Further, we present simple constructions of polynomial-length universal exploration sequences for some previously studied classes of graphs (e.g., 2-regular graphs, cliques, expanders), and we also present universal exploration sequences for trees. These constructions do not obey previously known lower bounds on the length of universal traversal sequences; thus, they highlight another difference between exploration and traversal sequences.     

How strong is Nisan?s pseudo-random generator?

We study the resilience of the classical pseudo-random generator (PRG) of Nisan (1992) [6] against space-bounded machines that make multiple passes over the input. Nisan?s PRG is known to fool log-space machines that read the input once. We ask what are the limits of this PRG regarding log-space machines that make multiple passes over the input. We show that for every constant k Nisan?s PRG fools log-space machines that make passes over the input, using a seed of length , for some k^′>k. We complement this result by showing that in general Nisan?s PRG cannot fool log-space machines that make nO(1) passes even for a seed of length . The observations made in this note outline a more general approach in understanding the difficulty of derandomizing BPNC¹.     

On the sequential nature of unification

The problem of unification of terms is log-space complete for P. In deriving this lower bound no use is made of the potentially concise representation of terms by directed acyclic graphs. In addition, the problem remains complete even if infinite substitutions are allowed. A consequence of this result is that parallelism cannot significantly improve on the best sequential solutions for unification. However, we show that for the problem of term matching, an important subcase of unification, there is a good parallel algorithm using O(log²n) time and n^O(1) processors on a PRAM. For the O(log²n) parallel time upper bound we assume that the terms are represented by directed acyclic graphs; if the longer string representation is used we obtain an O(log n) parallel time bound.     

Bridging across the log(n) Space Frontier

This paper establishes the importance of even the lowest possible level of space bounded computations. We show that DLOG does not coincide with NLOG if and only if there exists a tally set in NSPACE(log log n)\DSPACE(log log n). This result stands in perfect analogy to the related results concerning linear space or exponential time. Moreover, the above problem is equivalent to the existence of a functions(n), with arbitrarily slow or rapid growth rate, that is nondeterministically fully space constructible but cannot be constructed deterministically. We also present a “hardest” fully space constructibles(n)∈O(log log n), a functional counterpart of log-space complete languages. These nonrelativized results are obtained by the use of oracle machines consuming much larger amount of space, in range betweennand 2^d·n.     

对数空间可构造的无向图遍历序列

研究了为无向连通子图设计环状遍历序列（TSC）的空间复杂性问题。通过定义对数空间的Cook归约,分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系,证明了TSC问题以及无向图遍历问题是对数空间可解的,并给出了一个TSC一般性构造方法。最后还提出了一个更有效的针对树状图的TSC构造算法。     

On computing absolutely irreducible components of algebraic varieties with parameters

This paper presents a new algorithm for computing absolutely irreducible components of n-dimensional algebraic varieties defined implicitly by parametric homogeneous polynomial equations over ${\mathbb{Q}}$ , the field of rational numbers. The algorithm computes a finite partition of the parameters space into constructible sets such that the absolutely irreducible components are given uniformly in each constructible set. Each component will be represented by two items: first by a parametric representative system, i.e., the equations that define the component and second by a parametric effective generic point which gives a parametric rational univariate representation of the elements of the component. The number of absolutely irreducible components is constant in each constructible set. The complexity bound of this algorithm is ${\delta^{O(r^4)}d^{r^4d^{O(n^3)}}}$ , being double exponential in n, where d (resp. δ) is an upper bound on the degrees of the input parametric polynomials w.r.t. the main n variables (resp. w.r.t. r parameters).     

On a simple randomized algorithm for finding a 2-factor in sparse graphs

We analyze the performance of a simple randomized algorithm for finding 2-factors in directed Hamiltonian graphs of out-degree at most two and in undirected Hamiltonian graphs of degree at most three. For the directed case, the algorithm finds a 2-factor in O(n²) expected time. The analysis of our algorithm is based on random walks on the line and interestingly resembles the analysis of a randomized algorithm for the 2-SAT problem given by Papadimitriou [On selecting a satisfying truth assignment, in: Proc. 32nd Annual IEEE Symp. on the Foundations of Computer Science (FOCS), 1991, p. 163]. For the undirected case, the algorithm finds a 2-factor in O(n³) expected time. We also analyze random versions of these graphs and show that cycles of length Ω(n/logn) can be found with high probability in polynomial time. This partially answers an open question of Broder et al. [Finding hidden Hamilton cycles, Random Structures Algorithms 5 (1994) 395] on finding hidden Hamiltonian cycles in sparse random graphs and improves on a result of Karger et al. [On approximating the longest path in a graph, Algorithmica 18 (1997) 82].     

A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs

The Arc-Preserving Subsequence (APS) problem appears in the comparison of RNA structures in computational biology. Given two arc-annotated sequences of length n and m<n, APS asks if the shorter sequence can be obtained from the longer one by deleting certain elements along with their incident arcs. It is known that APS with pairwise nested arcs can be solved in O(mn) time. We give an algorithm running in O(m²+n) time in the worst case, actually it is even faster in particular if the shorter sequence has many arcs. The result may serve as a building block for improved APS algorithms in the general case.     

Efficient algorithms for regular expression constrained sequence alignment

Imposing constraints is an effective means to incorporate biological knowledge into alignment procedures. As in the PROSITE database, functional sites of proteins can be effectively described as regular expressions. In an alignment of protein sequences it is natural to expect that functional motifs should be aligned together. Due to this motivation, Arslan introduced the regular expression constrained sequence alignment problem and proposed an algorithm which, if implemented naïvely, can take time and space up to O(²|Σ|⁴|V|n²) and O(²|Σ|⁴|V|n), respectively, where Σ is the alphabet, n is the sequence length, and V is the set of states in an automaton equivalent to the input regular expression. In this paper we propose a more efficient algorithm solving this problem which takes O(³|V|n²) time and O(²|V|n) space in the worst case. If |V|=O(logn) we propose another algorithm with time complexity O(²|V|log|V|n²). The time complexity of our algorithms is independent of Σ, which is desirable in protein applications where the formulation of this problem originates; a factor of ²|Σ|=400 in the time complexity of the previously proposed algorithm would significantly affect the efficiency in practice.     

Computing the λ-covers of a string

Given a string x of length n and an integer constant λ, the λ-Cover Problem is defined to be the identification of all the sets of λ substrings each of equal length that cover x. This problem can be solved by a general algorithm in O(n²) time for constant alphabet size. We also generalize the λ-Cover Problem, whereby a set of λ substrings of different lengths are considered, which can be computed using the general algorithm in O(n²) time.     

An efficient reconstruction approach for improving Bluetree scatternet formation in personal area networks

Bluetooth is a communication technology for personal area networks (PANs). To support communication with more than eight bluetooth-enabled devices, a scatternet must be formed in the PAN. Bluetree is one commonly used topology for scatternet formation. To reduce traffic load of the Bluetree scatternet, we use the piconet transfer concept to move piconets on a well-formed Bluetree scatternet. The piconet movements are performed based on a distributed manner using two well-known tree traversal procedures: post-order traversal and level-order traversal. These two procedures do not take much computation time, where time complexities are O(n_p) and n_p is the number of piconets on a Bluetree scatternet (not the number of nodes on a Bluetree). Compared with previous approaches, the proposed approach can greatly reduce the traffic load and computational costs. Finally, simulation experiments show the effectiveness of the proposed approach in improving the formation of Bluetree scatternet.     

Parallel algorithms for rounding exact evaluation of sums of products

We propose two parallel algorithms for the rounding exact evaluation of sums of products. The first method transforms products to sums and applies one of the known methods for rounding exact summation in time complexity O(n²) with n processors (n denoting the “length” of the expression). The second method approximates the products as well as the sum and has average time complexity O(ld(n)) for n/2 processors and has average time complexity O(n) viewed as a sequential algorithm.     

Detecting Holes and Antiholes in Graphs

In this paper we study the problems of detecting holes and antiholes in general undirected graphs, and we present algorithms for these problems. For an input graph G on n vertices and m edges, our algorithms run in O(n + m²) time and require O(n m) space; we thus provide a solution to the open problem posed by Hayward et al. asking for an O(n⁴)-time algorithm for finding holes in arbitrary graphs. The key element of the algorithms is the use of the depth-first-search traversal on appropriate auxiliary graphs in which moving between any two adjacent vertices is equivalent to walking along a P₄ (i.e., a chordless path on four vertices) of the input graph or on its complement, respectively. The approach can be generalized so that for a fixed constant k ≥ 5 we obtain an O(n^k-1)-time algorithm for the detection of a hole (antihole resp.) on at least k vertices. Additionally, we describe a different approach which allows us to detect antiholes in graphs that do not contain chordless cycles on five vertices in O(n + m²) time requiring O(n + m) space. Again, for a fixed constant k ≥ 6, the approach can be extended to yield O(n^k-2)-time and O(n²)-space algorithms for detecting holes (antiholes resp.) on at least k vertices in graphs which do not contain holes (antiholes resp.) on k - 1 vertices. Our algorithms are simple and can be easily used in practice. Finally, we also show how our detection algorithms can be augmented so that they return a hole or an antihole whenever such a structure is detected in the input graph; the augmentation takes O(n + m) time and space.     

Two simple and efficient algorithms for Jordan sorting and polygon cutting and clipping

This paper deals with the Jordan sorting problem: Given n intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve, sort these points into the order in which they occur along the x-axis. The worst-case time complexity of this problem is θ(n). Unfortunately, the known O(n) time algorithms are too complicated, which causes that they are difficult to implement and slow for the inputs of sizes that are of practical interest. In this paper, two algorithms for Jordan sorting are presented. The first algorithm is extremely simple. Although its worst-case time complexity is O(nlogn), it is shown that the worst time is achieved only for special inputs. For most inputs, a better performance can be expected. Furthermore, an improved O(nlog logn) worst-case time algorithm is presented. For the input sequences of size from 4 to 10⁵, the algorithms are compared with Quicksort, with the algorithm based on splay trees and with the O(n) time algorithm proposed by Fung et al. The results show that our algorithms are faster. The relevant implementation details are given.     

Time-space trade-offs for compressed suffix arrays

Given a binary string of length n, we give a representation of its suffix array that takes O(nt(lgn)^1/t) bits of space such that given i,1?i?n, the ith entry in the suffix array of the string can be retrieved in O(t) time, for any parameter 1?t?lglgn. For t=lglgn, this gives a compressed suffix array representation of Grossi and Vitter [Proc. Symp. on Theory Comput., 2000, pp. 397-406]. For t=O(1/ε), this gives the best known (in terms of space) compressed suffix array representation with constant query time. From this representation one can construct a suffix tree structure for a text of length n, that uses o(nlgn) bits of space which can be used to find all the k occurrences of a given pattern of length m in O(m/lgn+k) time. No such structure was known earlier.     

Reconstructing a Binary Tree from Its Traversals in Doubly Logarithmic CREW Time

We consider the following problem. For a binary tree T = (V, E) where V = {1, 2, ..., n}, given its inorder traversal and either its preorder or its postorder traversal, reconstruct the binary tree. We present a new parallel algorithm for this problem. Our algorithm requires O(n) space. The main idea of our algorithm is to reduce the reconstruction process to merging two sorted sequences. With the best parallel merging algorithms, our algorithm can be implemented in O(log log n) time using O(n/log log n) processors on the CREW PRAM (or in O(log n) time using O(n/log n) processors on the EREW PRAM). Our result provides one more example of a fundamental problem which can be solved by optimal parallel algorithms in O(log log n)time on the CREW PRAM.     

Studies on the distribution of the shortest linear recurring sequences

The distribution of the shortest linear recurrence (SLR) sequences in the Z/(p) field and over the Z/(p^e) ring is studied. It is found that the length of the shortest linear recurrent (SLRL) is always equal to n/2, if n is even and n/2 + 1 if n is odd in the Z/(p) field, respectively. On the other hand, over the Z/(p^e) ring, the number of sequences with length n can also be calculated. The recurring distribution regulation of the shortest linear recurring sequences is also found. To solve the problem of calculating the SLRL, a new simple representation of the Berlekamp-Massey algorithm is developed as well.     

Efficient algorithms for finding interleaving relationship between sequences

The longest common subsequence and sequence alignment problems have been studied extensively and they can be regarded as the relationship measurement between sequences. However, most of them treat sequences evenly or consider only two sequences. Recently, with the rise of whole-genome duplication research, the doubly conserved synteny relationship among three sequences should be considered. It is a brand new model to find a merging way for understanding the interleaving relationship of sequences. Here, we define the merged LCS problem for measuring the interleaving relationship among three sequences. An O(n³) algorithm is first proposed for solving the problem, where n is the sequence length. We further discuss the variant version of this problem with the block information. For the blocked merged LCS problem, we propose an algorithm with time complexity O(n²m), where m is the number of blocks. An improved O(n²+nm²) algorithm is further proposed for the same blocked problem.     

An algebraic attack on the improved summation generator with 2-bit memory

Recently algebraic attacks on stream ciphers have received much attention. In this paper we apply an algebraic attack to the improved summation generator with 2-bit memory, which was presented by Lee and Moon in order to give the original summation generator correlation immunity. We show that the initial state of the generator can be recovered within O(n^5.6) bit operations from O(n²) regular output bits, where n is the total length of LFSRs. We could recover the initial key bits in practice within 3 minutes on a PC even for the case n=256. Our result is a good example that shows how powerful algebraic attacks are in the analysis of stream ciphers.     

An efficient decision procedure for the theory of rational order

In this paper we present a decision procedure for the theory of the rational numbers with the relation < (less than) which uses space at most n log n to decide sentences of length n. Our procedure cycles through a finite number of efficient encodings of order relations between rationals, rather than the rational numbers themselves. This result closely fits the result of Stockmeyer [8] of a nondeterministic space n⁵ lower bound on this theory.