9 citations · 16 across the 4 of their papers we have counts for
4 papers
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…