15 citations · 66 across the 26 of their papers we have counts for
6 papers · 1 filter
Morphic and Automatic Words: Maximal Blocks and Diophantine Approximation
Yann Bugeaud, Dalia Krieger, Jeffrey Shallit
Let $\mb w$ be a morphic word over a finite alphabet , and let be a nonempty subset of . We study the behavior of maximal blocks consisting only of letters from in $\…
On NFAs Where All States are Final, Initial, or Both
Jui-Yi Kao, Narad Rampersad, Jeffrey Shallit
We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversa…
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…
Periodicity, repetitions, and orbits of an automatic sequence
Jean-Paul Allouche, Narad Rampersad, Jeffrey Shallit
We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidab…
Counting Abelian Squares
L. B. Richmond, J. Shallit
An abelian square is a string of length 2n where the last n symbols form a permutation of the first n symbols. In this note we count the number of abelian squares and give an asymp…
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.