9 citations · 21 across the 6 of their papers we have counts for
6 papers
Multi-Shift de Bruijn Sequence
Zhi Xu
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 a mul…
A Minimal Periods Algorithm with Applications
Zhi Xu
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 c…
The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
N. Rampersad, J. Shallit, Z. Xu
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 Sigma is the set of al…
Decision Problems For Convex Languages
Janusz Brzozowski, Jeffrey Shallit, Zhi Xu
In this paper we examine decision problems associated with various classes of convex languages, studied by Ang and Brzozowski (under the name "continuous languages"). We show that…
An NP-hardness Result on the Monoid Frobenius Problem
Zhi Xu, J. Shallit
The following problem is NP-hard: given a regular expression , decide if is not co-finite.
The Frobenius Problem in a Free Monoid
Jui-Yi Kao, Jeffrey Shallit, Zhi Xu
The classical Frobenius problem is to compute the largest number g not representable as a non-negative integer linear combination of non-negative integers x_1, x_2, ..., x_k, where…