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.
Well, you just need to consider the finite automaton corresponding to the language as a directed graph and output the BFS tree of length $n$ starting from the initial state. This algorithm should take linear time in the output length.
