Generating all instances of a regular language up to a certain length Given a fixed regular language R, what is the complexity of generating all members of R with length at most $n$?  Suppose some reasonable model (RAM with $n$-bit words?) and a write-only output tape.  The list should be in length-lexicographical order.

I'm interested in the answer in terms of the output as well as the input.  (If R = Σ* then you can't improve on $O(|\Sigma|^n)$ but it only takes time linear in the output.)
There are several recent papers that address your question, e.g.:

Margareta Ackerman and Jeffrey Shallit. Efficient Enumeration of Regular Languages. Conference on Implementation and Application of Automata (CIAA) , Lecture Notes in Computer Science, 4783, Springer-Verlag, Berlin Heidelberg, pp. 226-241, 2007.

Margareta Ackerman and Erkki Makinen. Three New Algorithms for Regular Language Enumeration, Computing and Combinatorics: 15th Annual International Conference (COCOON) , Lecture Notes in Computer Science 5609, Springer-Verlag, Berlin Heidelberg, pp. 178-191, 2009.

You can get these two papers from here.