Rampersad, N., Shallit, J., Xu, Z.
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 all prefixes (resp.,...
Closures in Formal Languages and Kuratowski's Theorem (2009)
Brzozowski, J., Grant, E., Shallit, J.
A famous theorem of Kuratowski states that in a topological space, at most 14 distinct sets can be produced by repeatedly applying the operations of closure and complement to a given set. We...
Closures in Formal Languages: Concatenation, Separation, and Algorithms (2009)
Brzozowski, J., Grant, E., Shallit, J.
We continue our study of open and closed languages. We investigate how the properties of being open and closed are preserved under concatenation. We investigate analogues, in formal languages, of the...
Grant, E., Shallit, J., Stoll, T.
Motivated by the known autocorrelation properties of the Rudin-Shapiro sequence, we study the discrete correlation among infinite sequences over a finite alphabet, where we just take into account...
Counting Abelian Squares (2008)
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 asymptotic estimate of...
An NP-hardness Result on the Monoid Frobenius Problem (2008)
The following problem is NP-hard: given a regular expression $E$, decide if $E^*$ is not co-finite.
A Study on Unique Rational Operations (2008)
N. Rampersad, B. Ravikumar, N. Santean, J. Shallit
Abstract. For each basic language operation we define its “unique ” counterpart as being the operation which results in a language whose words can be obtain uniquely through the given operation....
The 2-adic valuation of the coefficients of a polynomial (2003)
Boros, G., Moll, V., Shallit, J.
In this paper we compute the 2-adic valuations of some polynomials associated with the definite integral $\int_{0}^{\infty} \frac{dx}{(x^4+2*a*x^2+1)^(m+1)}$