Efficient insertion of deterministic acyclic finite state automaton (DAFSA) into a full-text search index? I have a problem where I can easily construct a set of deterministic acyclic finite state automata (DAFSA) and I need a full-text search index, e.g. a suffix tree/array, over all the words encoded by these automata.
Is there an efficient algorithm for this? By efficient I mean that the complexity must not depend on the on the total number of words encoded in the DAFSA which may get very large. Consider the following example:
(all edges are directed from left to right)

  a1 --- a2 ... a{n-1} --- an
 /   \ /               \ /   \
S     X                 X     T
 \   / \               / \   /
  b1 --- b2 ... b{n-1} --- bn

In this example there are $2^n$ distinct paths from S to T, e.i. if the nodes were labelled with characters it would be an DAFSA encoding $2^n$ words. Still, the number of vertices is just $2(n+1)$ and the number of edges $4n$.
There is (probably) no such algorithm. At least, for suffix tries it is not possible:
For every word encoded by the DAFSA there must be at least an end-of-word marker in the suffix tree. Thus, the construction takes at least $\Omega(N)$ where $N$ is the number of words encoded by the DAFSA.
This argument cannot be extended to any kind of search index because it may employ some kind of compression – like the DAFSA does.