Zhi Xu

Zhi Xu

Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    De Bruijn Sequences Revisited
    Lila Kari
    International Journal of Foundations of Computer Science, 23(2012), pp. 1307-1322
    Preview abstract A (non-circular) de Bruijn sequence w of order n is a word such that every word of length n appears exactly once in w as a factor. In this paper, we generalize the concept to different settings: the multi-shift de Bruijn sequence and the pseudo de Bruijn sequence. An m-shift de Bruijn sequence of order n is a word such that every word of length n appears exactly once in w as a factor that starts at a position im + 1 for some integer i ≥ 0. A pseudo de Bruijn sequence of order n with respect to an antimorphic involution θ is a word such that for every word u of length n the total number of appearances of u and θ(u) as a factor is one. We show that the number of m-shift de Bruijn sequences of order n is an!a(m-n)(an-1) for 1 ≤ n ≤ m and is (am!)an-m for 1 ≤ m ≤ n, where a is the size of the alphabet. We provide two algorithms for generating a multi-shift de Bruijn sequence. The multi-shift de Bruijn sequence is important for solving the Frobenius problem in a free monoid. We show that the existence of pseudo de Bruijn sequences depends on the given alphabet and antimorphic involution, and obtain formulas for the number of such sequences in some particular settings. View details
    The Computational Complexity of Universality Problems for Prefixes, Suffixes, Factors, and Subwords of Regular Languages
    Narad Rampersad
    Jeffrey Shallit
    Fundamenta Informaticae, 116(2012), pp. 223-236
    Preview abstract In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal to Σ*? In the case of testing universality for factors of languages, there is a connection to two classic problems: the synchronizing words problem of Černý, and Restivo's conjecture on the minimal uncompletable word. View details
    Triangular and Hexagonal Tile Self-assembly Systems
    Lila Kari
    Shinnosuke Seki
    WTCS 2012, Computation, Physics and Beyond - International Workshop on Theoretical Computer Science, Springer, Berlin Heidelberg, pp. 357-375
    Preview abstract We discuss theoretical aspects of the self-assembly of triangular tiles, in particular, right triangular tiles and equilateral triangular tiles, and the self-assembly of hexagonal tiles. We show that triangular tile assembly systems and square tile assembly systems cannot be simulated by each other in a non-trivial way. More precisely, there exists a deterministic square (hexagonal) tile assembly system S such that no deterministic triangular tile assembly system that is a division of S produces an equivalent supertile (of the same shape and same border glues). There also exists a deterministic triangular tile assembly system T such that no deterministic square (hexagonal) tile assembly system produces the same final supertile while preserving border glues. View details
    Pseudopower Avoidance
    Ehsan Chiniforooshan
    Lila Kari
    Fundamenta Informaticae, 114(2012), pp. 55-72
    Preview abstract Repetition avoidance has been intensely studied since Thue's work in the early 1900's. In this paper, we consider another type of repetition, called pseudopower, inspired by the Watson-Crick complementarity property of DNA sequences. A DNA single strand can be viewed as a string over the four-letter alphabet {A,C,G, T}, wherein A is the complement of T, while C is the complement of G. Such a DNA single strand will bind to a reverse complement DNA single strand, called its Watson-Crick complement, to form a helical double-stranded DNA molecule. The Watson-Crick complement of a DNA strand is deducible from, and thus informationally equivalent to, the original strand. We use this fact to generalize the notion of the power of a word by relaxing the meaning of “sameness” to include the image through an antimorphic involution, the model of DNA Watson-Crick complementarity. Given a finite alphabet Σ, an antimorphic involution is a function θ : Σ* → Σ* which is an involution, i.e., θ2 equals the identity, and an antimorphism, i.e., θ(uv) = θ(v)θ(u), for all u ∈ Σ*. For a positive integer k, we call a word w a pseudo-kth-power with respect to θ if it can be written as w = u1 ... uk, where for 1 ≤ i, j ≤ k we have either ui = uj or ui = θ(uj). The classical kth-power of a word is a special case of a pseudo-kth-power, where all the repeating units are identical. We first classify the alphabets Σ and the antimorphic involutions θ for which there exist arbitrarily long pseudo-kth-power-free words. Then we present efficient algorithms to test whether a finite word w is pseudo-kth-power-free. View details
    Decision problems for convex languages
    Janusz Brzozowski
    Jeffrey Shallit
    Information and Computation, 209(2011), pp. 353-367
    De Bruijn Sequences Revisited
    Lila Kari
    AFL 2011, 13th International Conference Automata and Formal Languages, pp. 241-254
    Preview abstract A (non-circular) de Bruijn sequence w of order n is a word such that every word of length n appears exactly once in w as a factor. In this paper, we generalize the concept to different settings: the multi-shift de Bruijn sequence and the pseudo de Bruijn sequence. An m-shift de Bruijn sequence of order n is a word such that every word of length n appears exactly once in w as a factor that starts at a position im + 1 for some integer i ≥ 0. A pseudo de Bruijn sequence of order n with respect to an antimorphic involution θ is a word such that for every word u of length n the total number of appearances of u and θ(u) as a factor is one. We show that the number of m-shift de Bruijn sequences of order n is an!a(m-n)(an-1) for 1 ≤ n ≤ m and is (am!)an-m for 1 ≤ m ≤ n, where a is the size of the alphabet. We provide two algorithms for generating a multi-shift de Bruijn sequence. The multi-shift de Bruijn sequence is important for solving the Frobenius problem in a free monoid. We show that the existence of pseudo de Bruijn sequences depends on the given alphabet and antimorphic involution, and obtain formulas for the number of such sequences in some particular settings. View details
    A Minimal Periods Algorithm with Applications
    CPM 2010, 21st Annual Symposium Combinatorial Pattern Matching, Springer, Berlin Heidelberg, pp. 51-62
    Preview abstract Kosaraju in “Computation of squares in a string” briefly described a linear-time algorithm for computing the minimal squares starting at each position in a word. Using the same construction of suffix trees, we generalize his result and describe in detail how to compute the minimal α power, with a period of length longer than s, starting at each position in a word w for arbitrary exponent α> 1 and integer s ≥ 0. The algorithm runs in O(α|w|)-time for s = 0 and in O(|w|2)-time otherwise. We provide a complete proof of the correctness and computational complexity of the algorithm. The algorithm can be used to detect certain types of pseudo-patterns in words, which was our original goal in studying this generalization. View details
    Triangular Tile Self-assembly Systems
    Lila Kari
    Shinnosuke Seki
    DNA 16, 16th International Conference DNA Computing and Molecular Programming, Springer, Berlin Heidelberg(2010), pp. 89-99
    Preview abstract We discuss theoretical aspects of the self-assembly of triangular tiles; in particular, right triangular tiles and equilateral triangular tiles. Contrary to intuition, we show that triangular tile assembly systems and square tile assembly systems are not comparable in general. More precisely, there exists a square tile assembly system S such that no triangular tile assembly system that is a division of S produces the same final supertile. There also exists a deterministic triangular tile assembly system T such that no square tile assembly system produces the same final supertiles while preserving border glues. We discuss the assembly of triangles by triangular tiles and show triangular systems with Θ(logN/loglogN) tiles that can self-assemble into a triangular supertile of size Θ(N 2). Lastly, we show that triangular tile assembly systems, either right-triangular or equilateral, are Turing universal. View details
    Pseudo-power Avoidance
    Ehsan Chiniforooshan
    Lila Kari
    DLT 2010, 14th International Conference Developments in Language Theory, Springer, Berlin Heidelberg, pp. 432-433
    Preview abstract Since Thue’s work [10] in the early 1900’s, repetition avoidance has been intensely studied [9,8,7,4]. From the point of view of DNA computing [5], we study another type of repetition, called a pseudo-power, inspired by the property of the Watson- Crick complementarity in molecular biology. View details
    Decision Problems for Convex Languages
    Janusz Brzozowski
    Jeffrey Shallit
    LATA 2009, Third International Conference Language and Automata Theory and Applications, Springer, Berlin Heidelberg, pp. 247-258
    Preview abstract We examine decision problems for various classes of convex languages, previously studied by Ang and Brzozowski under the name “continuous languages”. We can decide whether a language L is prefix-, suffix-, factor-, or subword-convex in polynomial time if L is represented by a DFA, but the problem is PSPACE-hard if L is represented by an NFA. If a regular language is not convex, we prove tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages. View details
    The Frobenius Problem in a Free Monoid
    Jui-Yi Kao
    Jeffrey Shallit
    STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 421-432
    Preview abstract The classical Frobenius problem over ${mathbb N}$ is to compute the largest integer $g$ not representable as a non-negative integer linear combination of non-negative integers $x_1, x_2, ldots, x_k$, where $gcd(x_1, x_2, ldots, x_k) = 1$. In this paper we consider novel generalizations of the Frobenius problem to the noncommutative setting of a free monoid. Unlike the commutative case, where the bound on $g$ is quadratic, we are able to show exponential or subexponential behavior for several analogues of $g$, with the precise bound depending on the particular measure chosen. View details