Decidability and Shortest Strings in Formal Languages
Levent Alpöge, Thomas Ang, Luke Schaeffer, Jeffrey O. Shallit · arXiv (Cornell University) · 2011
Given a formal language L specified in various ways, we consider the problem of determining if L is nonempty. If L is indeed nonempty, we find upper and lower bounds on the length of the shortest string in L.