<p>Here is the first part of the answer (without swapping).  I restated some of the definitions to make them clearer (I think), as I was somewhat confused by the statement of the question.</p>

<h2>Introduction to the problem and its practical importance</h2>

<p>I do not know the motivation for the question, as it was not given.
However this is a known problem of natural language processing (NLP),
and specifically of speech processing. The problem is that phonems are
not always clearly identifiable, nor are the boundaries between
lexical elements (words), which is a little bit more general than the
question. As a consequence, there can be several ways to cut the
spoken sentence into words of the language. In order to account for
that, the single linear stream of phonems is actually transformed into
what is called a "<a href="http://www.statmt.org/moses/?n=Moses.WordLattices" rel="nofollow noreferrer">word lattice</a>" which may be seen as a
directed acyclic graph or as an acyclic DFA (though even the
acyclicity is also a topic for discussion in some cases - see my
remark on whether the empty word can be in $W$). This word
lattice corresponds to all the ways the sentence can be cut into
recognizable words. This is often based on probabilities and Markov
models.</p>

<p>Well known examples of the need for word lattices are holorime
verses. See for example "<a href="https://linguistics.stackexchange.com/questions/3514">Phonological ambiguity that changes the syntactic structure</a>".</p>

<p>The word lattices are then used in various way for further linguistic
processing. One use is to do syntax analysis with respect to a
syntactic definition of the language, the identified lexical elements
(or their lexical category, called "part of speech") being used as
alphabet symbols at that syntactic level. In the question asked, the
collection $S$ or sentences plays the role of the language syntax that
defines allowed sentences. The set $W$ is the collection of acceptable
spoken language words that can be built from the phonems in $\Sigma$.
It is a bit simplified from the real speech processing situation. For
example, the set $W$ is finite, while in speech processing it is
considered open (actually finite, but so large ...). This is dealt with
by replacing all the words of a given category by that category
considered as a whole (I skip many details).</p>

<p>Many modern parsing techniques can be readily extended to the parsing
of word lattices, as most syntactic formalisms are closed under
intersection with regular sets. See for example "<a href="http://bat8.inria.fr/~lang/papers/harder/harder.pdf" rel="nofollow noreferrer">Recognition can be
Harder than Parsing</a>".</p>

<p>The problem addressed by word lattices (and by this question) is <strong>lexical
ambiguity</strong>: the ambiguity resulting from the fact that the sequence of
lexical elements that can correspond to the analyzed string is not
unique. This can be opposed to <strong>syntactic ambiguity</strong> du to the fact that the
lexical sequence can be generated syntactically in two different ways,
as in ambiguous context-free grammars.</p>

<p>The issue of character swapping, here supposedly to detect
"spoonerisms", is part of various techniques to deal with input
ill-formedness that can be modeled by finite state tranducers.
Here again, closure properties are more than helpful.</p>

<h2>A solution without swap, linear in each parameter</h2>

<p>The set $W$ may be considered finite, as only a finite number of words
in $W$ can be used to form the alphabet for sentences. We assume
furthermore that the empty word is not in $W$. It is not strictly
necessary for the construction given here, but it could make the
parsing yield an arbitrarily long sequence, independently of the
length of the string $w$ being parsed, possibly giving a false idea of
the complexity.</p>

<p>We associate with each word $w\in W$ a unique symbol $\hat w$. Let
$\hat W=\{\hat w \mid w\in W\}$. This is not strictly necessary, but may
avoid confusion as to what is the alphabet.</p>

<p>Then you build a <a href="https://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer">trie</a>, as a DFA that recognizes the words in $W$. Each
final state recognizing a word $w_k\in W$ is then labeled with $\hat w_k$
(cf <a href="https://en.wikipedia.org/wiki/Moore_machine" rel="nofollow noreferrer">Moore machines</a>). Then an $\epsilon$-transition is added from each
final state to the initial state, turning the DFA into a NFA that
recognizes sequences of words in $W$, and which can output $\hat w_k$
whenever $w_k$ has been recognized. Then you apply the powerset
construction to turn this NFA into a DFA $T_W$, such that the states of this new
DFA have all the labels of the trie final states they contain.</p>

<p>This construction, though expensive because of the powerset
construction, is done only once, independently of the sentence $w$,
and thus does not count in the complexity analysis. It is amortized over all string $w$ that will be parsed (as is the case for all parser construction techniques).</p>

<p>Given a string  $w\in\Sigma^*$
you build a DFA $L_{W,w}=(\{q_i\mid 0\leq i\leq |w|\},\hat W,q_0,q_n,\tau_{W,w})$ as follow:</p>

<ul>
<li><p>$q_0$ and $q_n$ are respectively initial and final state</p></li>
<li><p>the number of states is $n+1$</p></li>
<li><p>there is a transition on input $\hat w_k$  from state $q_i$ to state
$q_j$ iff $w[i:j]=w_k$ where $w_k \in W$</p></li>
</ul>

<p>The notation $w[i:j]$ denote the substring of $w$ from index $i+1$ to
index $j$, the first letter having index $1$.</p>

<p>This finite state automaton $L_{W,w}$, called a <strong><a href="http://www.statmt.org/moses/?n=Moses.WordLattices" rel="nofollow noreferrer">word lattice</a></strong> in speech
processing, generates or recognizes all sentences that are sequences
of words in $W$ that concatenate into the string $w$. Note that the literature often presents it as a directed acyclic graph rather than a DFA.</p>

<p>To build the transitions, you apply the DFA $T_W$ to the string
$w$. Whenever you enter a state that has a label $\hat w_k$ (It may
have several labels), it means
that you have just recognized the string $w_k\in W$. If you have read
$j$ letters, it means that $w[i:j]=w_k$ for $i=j-|w_k|$. Thus you add
the corresponding transition to the word lattice.</p>

<p>The DFA $T_W$ executes no more than $|w|$ transition steps, and at
each step adds at most $|W|$ transitions to the word lattice.
Hence the complexity is $O(|W|\times|w|)$</p>

<p>Now we have to find out which sentences in the language recognize by
the language of $L_{W,w}$ are also recognized by the DFA $M_S$ on alphabet
$\hat W$ recognizing $S$.</p>

<p>In other words we want the intersection of the two languages. This can
be obtained by the usual cross product construction of the two
automata, which are both DFA. The resulting automaton is a recognizer
for the solutions, and can be used to generate them non
deterministically.</p>

<p>Since the set $S$ is a regular set, potentially infinite, each
solution must be given explicitely as a word in $\hat W^*$, with
corresponding cost, rather than being named in constant time.
However, if the empty word is not in $W$, the length of each solution
is bound by the length of $w$.</p>

<p>The cross product construction gives a number of states that is the
product of that number for each automaton: $|Q_S|\times(|w|+1)$.
Each of the $|\tau_S|$ of the DFA $M_S$ is associated with each of the
$O(|W|\times|w|)$ transitions of the word lattice to determine the
transitions of the cross product.</p>

<p>Hence the cost of producing the DFA for the solutions is $O(|W|\times|w|\times|M_S|)$</p>

<p>The cross-product DFA is noted $F_{W,S,w}$. Its construction is such
that its mimics exactly the DFA $S$, but only for the sentences in
$\hat W^*$ accepted by the word lattice, i.e. all those corresponding
to the sentence $w$. Hence, it does give all the sentences in $S$ as
words in $\hat W^*$ that are equal letter-wise to $w$.</p>

<p><strong>Enumerating the solutions</strong></p>

<p>Here is how you can enumerate the solutions with the DFA $F_{W,S,w}$
to be conformant to the constraint that the enumeration should be
linear in the size of a trie of all solutions.</p>

<p>We suppose the symbols in $\hat T$ are totally ordered, for example by
the lexicographic order of the corresponding words in $T$.  We also
assume that the DFA $F_{W,S,w}$ has been pruned of all states that do
not have a path to an accepting state, and of transitions to and from
these states (this does not have to exceed the cost of building the
DFA). The missing transitions will be considered as virtually going to
a dead state; they are not needed here.</p>

<p>Let $d$ be the length of the string $w$. Since we
excluded the empty word from $T$, all solutions have a length less
than $d$. Hence the DFA $F_{W,S,w}$ is acyclic, i.e. represented by an
edge labeled DAG. </p>

<p>Initialize an array $\mathcal S$ of length $d$, indexed from 1 to $d$, storing
the words to be enumerated, and a cursor $c$ indexing the last
modified letter of $\mathcal S$.</p>

<p>Initialize a second array $\mathcal Q$ of length $d+1$, indexed from 0
to $d$, storing the states followed to produce/recognize the current
content of $\mathcal S$. The cursor $c$ indexes also the last visited
state.The array $\mathcal Q$ is initialised with the initial state of
the DFA $F_{W,S,w}$ at index 0.</p>

<p>Both arrays are used as pushdown stacks, the cursor $c$ pointing at
the top.</p>

<p>Then perform a simulation of a Depth First Search (DFS) on a virtual
version of the trie of all solutions recognized by the DFA
$F_{W,S,w}$, by updating only the top of the stacks.</p>

<p>When a transition of the DFA is followed, its label is pushed on
$\mathcal S$ and the next state is pushed on $\mathcal Q$.</p>

<p>When a state $q$ has just been pushed on the stack $\mathcal Q$:</p>

<ul>
<li><p>If $q$ is an accepting state the content of stack $\mathcal S$ is a
solution;</p></li>
<li><p>if $q$ has transitions, follow the one with the smallest label;</p></li>
<li><p>if there are no transitions, then pop both stacks.</p></li>
</ul>

<p>When the stacks are popped, let $\hat w$ be the symbol just popped
from $\mathcal S$, and $q$ be the new top of $\mathcal Q$.</p>

<ul>
<li><p>if $q$ has transitions with a label greater than $\hat w$, follow
the one with the smallest label;</p></li>
<li><p>otherwise pop both stack.</p></li>
</ul>

<p>When all transitions of the initial state at the bottom of stack
$\mathcal Q$ have been followed, the enumeration terminates.</p>

<p>This algorithm is essentially a virtual traversal of the trie of all
solutions, because the finite automation $F_{W,S,w}$ is deterministic
and pruned of unproductive states and transitions. Therefore the time
cost is linear in the size of that trie. The solutions are given in
lexicographic order with respect to $\hat V$.</p>

<p>However, though I have not explored the issue, I fear that the size of
that trie may far exceed the size of the DFA $F_{W,S,w}$. Even if S is
finite, it may be represented by a DFA that is much smaller than its
trie (precisely our problem).</p>

<p><strong>Note</strong>:<br>
$S$ does not have to be a regular set.</p>

<p>The essential ingredients for the solution presented and its
complexity are the deterministic real-time character of the automaton
and the cross product construction. Hence it should be applicable with
the same complexity result if $S$ were a real-time deterministic
context-free language.</p>

<p>More generally, all kinds of languages families may be considered,
with a complexity that depends on recognition complexity of the
family.
For example, if $S$ is a context-free language,
then the complexity for $|w|$ is at worst $O(|w|^3)$. But things get
then more complex: parsing with respect to a regular set for $S$ just
means recognizing $\hat W$-strings in $S$ that expand to the word $w$.
However, if S is a context-free language, one may be satisfied with a
recognizer as in the regular case, but one may also want to have some
or all parses with respect to a specific grammar which may itself be
ambiguous. The complexity analysis may then depend somewhat on what is
actually desired, on language properties or on grammar properties.
And this extend to a variety of other grammatical formalisms.</p>

<h2>Allowing to swap letters</h2>

<p>To come later. It can be done also with finite state techniques.</p>

CC BY-SA 3.0
2014-04-01T17:38:31.260Z
Can you explain how your approach would work in a simple case, e.g. when the set $S$ is an aperiodic regular language? In that case it can be represented by a trie with self-loops (right?), but I don't clearly see how to exploit it. Assuming that we have precomputed the "meaningful" subwords it seems that we should enumerate the sentences in "lexicographic order", i.e. a decomposition $w=w1 \ldots wk$ should be indexed by the tuple $(|w1|,|w2|,\ldots,|wk|)$. Do you see a way to do amortized-constant delay enumeration in that situation?
Super0
CC BY-SA 3.0
2014-04-01T17:42:24.930Z
@Super0 I am not sure I understand your question. A finite set is
regular, and my construction works for regular sets. The trie for this
finite set $S$ of words may be read as a DFA for the finite set. Then
the cross-product construction gives you a recognizer, that can be
interpreted as a non-deterministic generator. You can the choose a
policy for following control branches depths first, choosing them in
lexical order of the next label $\hat w_i$. If you wish, you can
choose to replace outputting $\hat w_i$ by $w_i$ or by $|w_i|$.
babou
CC BY-SA 3.0
2014-04-01T17:50:36.683Z
I do not see what there is to amortize at this point. I may not
understand what you mean by "amortized-constant delay enumeration".
I do not know about aperiodic regular languages ... I can look.
Maybe if you explain what you consider missing in my construction, I
will understand better.
babou
CC BY-SA 3.0
2014-04-01T21:55:17.940Z
@Super0 Actually the method I suggest applies to many families of language for
S. However I have to find a good definition of "amortized-constant
delay enumeration" to check for sure that this constraint is met
(suggestion or reference for a definition are welcome). - - - - - - - - - - - - - 
One question, however: are you interested only in recognition (there
is nothing else in the regular case), or are you also interested in
parse structures when they exist, such as parse trees for CF
languages.
babou
CC BY-SA 3.0
2014-04-01T22:55:58.623Z
Thanks for your reply and for the extra motivation :) I agree that if $S$ is described by a DFA then you can reduce to enumerating paths in a dag. But afaik, this only gives a linear-time delay, i.e. the total complexity would be $O(|w| c)$. I was interested in lowering it to $O(|w|+c)$ which should be possible with 'amortized' constant delay, e.g. if the delay is constant on average. Also, extensions to NFAs and grammars would be useful for processing natural languages. If you want to think more about the problem, a useful reference is Ruskey's book 'Combinatorial Generation'.
Super0
CC BY-SA 3.0
2014-04-01T23:12:56.433Z
There are $c$ strings of size bound by $|w|$ to enumerate. How do you
expect to identify the strings in space (hence time) indpendent of
$|w|$. What kind of identification do you expect. You have no bound on
the number of strings in $S$ that "parse" your $w$.  How would you do
it with an oracle who does not even need to compute? I do not know
hown to express the answer with lower complexity, if I am to enumerate
the strings. The only other solution is to keep them compacted in a
generator or recognizer, which is precisely what I did.
babou
CC BY-SA 3.0
2014-04-01T23:15:17.233Z
You won't change my mind, I still think there's a chance unless you convince me otherwise. Ideally, we would like an enumeration $w_1,\ldots,w_n$ of the words such that $\sum_{i = 1}^{n-1} d(w_i,w_{i+1}) = O(n)$, where $d$ denotes the Hamming distance. This might be too optimistic in general, but this is possible in special cases, e.g. if we have a trie we can traverse it in linear time. We should look at the literature to see if the problem is open though.
Super0
CC BY-SA 3.0
2014-04-01T23:16:23.097Z
I did not yet have time to mention it, but it does work for grammars, CF grammars and many others. And it is linear for deterministic grammars as it is for DFA.
babou
CC BY-SA 3.0
2014-04-01T23:39:03.653Z
@Super0 You are suggesting a condensed form, like a trie. Now Can you tell me what is the difference between condensing the answers as a trie or as a finite state generator, which actually will work exactly like a trie and be even more condensed? - - - - - You wanted to enumerate. But I do not see the point.
babou
CC BY-SA 3.0
2014-04-02T00:05:39.877Z
@Super0 OK I see what you want. This April 1st is your lucky day: the
DFA that is built with the technique I suggest has no loop.  This is
for a very simple reason: the size is limited by $|w|$, and any loop
would allow you to pump out. So I guess it is essentially a trie,
which you can traverse in linear time. But what do you want that for?
Actually it may be a bit better than a trie, with some branch
sharing, but that is not a problem regarding traversal, which remain
linear w.r.t. the trie size.
babou
CC BY-SA 3.0
2014-04-02T00:36:32.497Z
I think there's a misunderstanding, luck shouldn't play any role of science, for me it's mainly a matter of dedication. Also, there is a difference between a dag and a trie: the latter has a treelike structure while the former may have undirected cycles. It's not known how to enumerate source,sink-paths in a dag with constant delay, so the question is whether the structure of the language/DFA helps..
Super0
CC BY-SA 3.0
2014-04-02T08:52:34.547Z
@Super0 How do you enumerate the words in a trie with constant delay, and why will it not work for a DAG? I cannot find references on the web.
babou
CC BY-SA 3.0
2014-04-02T17:42:53.570Z
Your question is misleading. Apparently you want a solution
linear in $|w|+c$ rather than in $|w|\times c$. But, rather
than an enumerator, you additionally require explicit enumeration
of answers, which takes at least $O(|w|\times c)$. If you consider that
you can do better, I am asking you to **describe precisely how you do
it, assuming you have an oracle that gives you all answers as a trie**,
since you claim a trie is enough to do it. You give that trie based
procedure, and I will improve my answer. No evasive statement or
formula, just the enumeration based on the trie of solutions.
babou
CC BY-SA 3.0
2014-04-02T17:56:13.340Z
@Super0 You state that "*if we have a trie we can traverse it in linear
time*". And you apparently see that as an answer to your amortized
constant time issue. I am quite willing to accept the idea, but you
should be more precise: linear with respect to what parameter(s) of
the trie?
babou
CC BY-SA 3.0
2014-04-03T22:03:53.443Z
@Super0 Do you have specific reasons to believe this answer can have a major improvement?  You said nothing of your motivation regarding this question.
babou
CC BY-SA 3.0
2014-04-01T02:00:17.803Z
2014-04-02T22:13:42.153Z
2017-04-13T12:54:12.010Z
babou
<p><em>This is not an answer but an extended reply to babou's comment.</em></p>

<p>I suggest looking at some literature on constant-delay enumerators, this can usually be done with 'in place' modification. The simplest example is the lexicographical enumeration of a set of the form $[D]^n$ where $D,n$ are integers. If you identify an element of $[D]^n$ with an $n$-digit word in base $D$, it is easy to see that by starting with the word $(0,\ldots,0)$ and by repeatedly apply the successor operation you get an enumerator with amortized constant delay. The intuition is that a chain of $i$ carry propagations happen with probability $1/D^i$, and thus the average time is $\sum_{i = 1}^{n} i (1/D)^{i-1} (1-\frac{1}{D})$ which is bounded by a function of $D$ only.</p>

<p>More generally, here is how it would work with a trie. Let $d$ be the depth of the trie $T$, initialize an array $w$ of length $d$ storing the words to be enumerated, and a cursor $c$ pointing to the last modified letter of $w$. Perform a dfs of $T$ by updating only the last letter and the cursor: when going back to a parent node move $c$ to the left, when going to a child node write its label under $c$ and move $c$ to the right. It is clear that you get the desired result in time linear in the size in $T$. But this example is not so interesting as it corresponds to a finite language, so the next step would be to look at a star-free language represented by a trie $T$ with self-loops: in that case can you enumerate the words of length $n$ in time $O(|T|+c)$ where $c$ is the number of such words?</p>

CC BY-SA 3.0
2014-04-02T22:31:11.353Z
Thanks for the explanation. The problem is finding documents. I have no
library available right now, and the web has less than one would
expect.
babou
CC BY-SA 3.0
2014-04-02T22:31:45.300Z
Here it is as promised. Enumerating the paths of a DAG cannot be
linear with respect to the size of the DAG. That much is obvious.  But
in the case of the loopless DFA, though enumeration is not linear
w.r.t. the DFA size, it can be linear w.r.t. the size of the trie of
all solutions. I said as much in my April 1st comment yesterday.
**The complexity problem is not in the computation of the solution,
but in the size of the solution itself. That cannot be helped very much.**
Unless you give up enumerating, and do whatever further processing
there is on a condensed representation.
babou
CC BY-SA 3.0
2014-04-02T18:50:03.580Z
2014-04-02T18:50:03.580Z
Super0
<p>Here is one algorithm. It runs in time at most $O(|S|*|w| + c)$, and probably runs much faster for many inputs.</p>

<p>We create a directed graph $G$. The graph $G$ has a vertex $(s,i,j)$ for any $s \in S$ and any indices $i,j$ such that $s=w[i..j]$. Then the graph has a directed edge from $(s,i,j)$ to $(s',i',j')$ whenever $i'=j+1$. Finally, the graph has two additional vertices, a source and a sink. There is a directed edge from the source to any vertex of the form $(s,0,j)$ and from any vertex of the form $(s,0,|w|)$ to the sink.</p>

<p>Now notice that the directed paths from the source of the sink correspond exactly to the parsings of $w$. So it's enough to enumerate all (source,sink)-paths in $G$, which can be done in time $O(|G'|+c)$. Note that the graph $G$ kind of represents all the parsings, so for many applications you wouldn't even have to enumerate them explicitly.</p>

CC BY-SA 3.0
2014-04-01T16:01:28.060Z
I do not understand what you are trying to achieve, but you are not even taking the set $W$ into account in your answer.
babou
CC BY-SA 3.0
2014-04-01T22:57:14.793Z
I think you had essentially the same idea, you both suggested enumerating source,sink-paths in a dag which seems indeed the right approach for a DFA. See my other comment above for possible extensions.
Super0
CC BY-SA 3.0
2014-04-01T23:38:15.370Z
@Super0 Maybe, but $W$ is missing  ... so it cannot possibly use all the data. There is necessarily a bug somewhere.
babou
CC BY-SA 3.0
2014-03-30T20:01:30.650Z
2014-03-30T20:01:30.650Z
greg
<p>Consider the following problem. We are given a set of words $W \subseteq \Sigma^*$ and a set of sentences $S \subseteq W^*$. The "ambiguous parsing" problem consists, given a word $w \in \Sigma^*$, to enumerate the sentences $s \in S$ that parse to $w$ (meaning that $s$ consists of the letters $w_1,\ldots,w_k$ and $w$ is the concatenation of the corresponding words).</p>

<p>The problem has an interesting variant which is the search of <a href="http://www.fun-with-words.com/spoon_example.html" rel="nofollow">spoonerisms</a>: we now allow some number $M$ of letters swap, and we want to enumerate the valid sentences obtainable from $w$ with at most $M$ swaps.</p>

<p>So my question is: under what condition on the language $S$ can the above  problem be solved in linear time? By this I mean time $O(|W|+|S|+|w|+c)$ where $c$ is the number of solutions.</p>

<p>(NOTE ADDED: in response to the comments below, the vocabulary $W$ is assumed to be finite, and the set $S$ can be infinite but "finitely described" by some device $\Delta_S$. As we can report all meaningful subwords of $w$ in $O(|w|)$ time, it may be possible to reduce my question to the enumeration of the accepting paths of a non-deterministic automaton or the derivations of an ambiguous grammar. What I am looking for is restricted models that allow a linear or amortized-constant delay enumeration of the parsings.)</p>

CC BY-SA 3.0
2014-03-30T15:10:42.190Z
You forgot to put |w| in the running time. Also, how is $S$ represented?
greg
CC BY-SA 3.0
2014-03-30T15:33:19.523Z
Thanks, I didn't notice the ommission? for $W$ and $S$ I assumed they were finite sets represented in extension, but they could also be represented by a dfa (at the cost of a higher complexity?..)
Super0
CC BY-SA 3.0
2014-03-30T15:41:40.230Z
About my previous comment: sorry for the confusion, I _don't_ assume that $S$ is regular, although I think we can assume $W$ to be finite. So the description of $S$ would depend on the category of the language, regular, context-free, etc.
Super0
CC BY-SA 3.0
2014-03-30T19:54:58.450Z
I still don't understand how $S$ is represented. Regular on what base set? I don't know what "represented in extension" even means. Could you specify one representation or another? Otherwise it would be very hard to answer the question.
greg
CC BY-SA 3.0
2014-03-30T21:19:39.310Z
Do you really mean that $w_1,\ldots,w_k$ are letters, rather than
words in $W$.
babou
CC BY-SA 3.0
2014-03-31T02:15:10.200Z
@md and babou: by defn, a word is a sequence of letters, and a sentence is a sequence of words. The set $S$ should therefore be considered as a language on the alphabet $W$, and could be represented in extension (by listing its members) or by some machine/grammar. We can't expect $S$ to be finite in general so I'm more interested in the second situation; for instance, what happens with a regular set $S$ described by a DFA?
Super0
CC BY-SA 3.0
2014-03-31T16:02:51.947Z
You did not answer me. You state: "meaning that $s$ consists of the letters and $w$ $w_1,\ldots,w_k$ is the concatenation of the corresponding words". This is inconsistent. Are the $w_i$ elements of $\Sigma$ or of $\Sigma^*$ ?
babou
CC BY-SA 3.0
2014-03-31T18:04:03.240Z
@babou: I gave a non-formal answer by recalling the notion of 'words' and 'sentences' from grade school :) If my notation confuses you, you can think of it as a homomorphism $\phi$ between a set of tokens $T$ and a set of words $W \subseteq \Sigma^*$; a sentence $s = t_1 \ldots t_k$ in $T^*$ can then be translated to a word $\phi(s) = \phi(t_1) \ldots \phi(t_k)$ in $\Sigma^*$.
Super0
CC BY-SA 3.0
2014-04-01T00:36:05.217Z
Are you sure you want $O(|W|+|S|+|w|+c)$, or would
$O(|W|\times|S|\times|w|\times c)$ be ok? I very much doubt the former
is possible.  And being linear in each parameter seems already interesting.
babou
CC BY-SA 3.0
2014-04-04T14:44:33.547Z
You state "we can report all meaningful subwords of $w$ in $O(|w|)$
time". I may miss what you mean by "report" or "meaningful
subword": I interpret it as enumerating occurences in $w$ of words
in $W$. However, even on a single letter alphabet $\Sigma$ there may
be $O(|w|\times|W|)$ such occurences. Of course that is still $O(|w|)$
if you consider $|W|)$ a constant. But you ask for a complexity in the
sum rather than the product of the sizes. Taking $S=\hat W^*$,
which has a very small sized automaton, you get an exponential number of
solutions, that will take as much time to be enumerated.
babou
<string-matching>
Complexity of ambiguous parsing?
Super0
# Complexity of ambiguous parsing?

(Asked by: username_0 on 2014-03-30)

Consider the following problem. We are given a set of words $W \subseteq \Sigma^\*$ and a set of sentences $S \subseteq W^\*$. The "ambiguous parsing" problem consists, given a word $w \in \Sigma^\*$, to enumerate the sentences $s \in S$ that parse to $w$ (meaning that $s$ consists of the letters $w\_1,\ldots,w\_k$ and $w$ is the concatenation of the corresponding words).

The problem has an interesting variant which is the search of [spoonerisms](http://www.fun-with-words.com/spoon_example.html): we now allow some number $M$ of letters swap, and we want to enumerate the valid sentences obtainable from $w$ with at most $M$ swaps.

So my question is: under what condition on the language $S$ can the above problem be solved in linear time? By this I mean time $O(|W|+|S|+|w|+c)$ where $c$ is the number of solutions.

(NOTE ADDED: in response to the comments below, the vocabulary $W$ is assumed to be finite, and the set $S$ can be infinite but "finitely described" by some device $\Delta\_S$. As we can report all meaningful subwords of $w$ in $O(|w|)$ time, it may be possible to reduce my question to the enumeration of the accepting paths of a non-deterministic automaton or the derivations of an ambiguous grammar. What I am looking for is restricted models that allow a linear or amortized-constant delay enumeration of the parsings.)

**Tags:** string-matching
> **Comments:**
> **username_1**: You forgot to put |w| in the running time. Also, how is $S$ represented?  
> **username_0**: Thanks, I didn't notice the ommission? for $W$ and $S$ I assumed they were finite sets represented in extension, but they could also be represented by a dfa (at the cost of a higher complexity?..)  
> **username_0**: About my previous comment: sorry for the confusion, I _don't_ assume that $S$ is regular, although I think we can assume $W$ to be finite. So the description of $S$ would depend on the category of the language, regular, context-free, etc.  
> **username_1**: I still don't understand how $S$ is represented. Regular on what base set? I don't know what "represented in extension" even means. Could you specify one representation or another? Otherwise it would be very hard to answer the question.  
> **username_2**: Do you really mean that $w_1,\ldots,w_k$ are letters, rather than words in $W$.  
> **username_0**: @md and babou: by defn, a word is a sequence of letters, and a sentence is a sequence of words. The set $S$ should therefore be considered as a language on the alphabet $W$, and could be represented in extension (by listing its members) or by some machine/grammar. We can't expect $S$ to be finite in general so I'm more interested in the second situation; for instance, what happens with a regular set $S$ described by a DFA?  
> **username_2**: You did not answer me. You state: "meaning that $s$ consists of the letters and $w$ $w_1,\ldots,w_k$ is the concatenation of the corresponding words". This is inconsistent. Are the $w_i$ elements of $\Sigma$ or of $\Sigma^*$ ?  
> **username_0**: @babou: I gave a non-formal answer by recalling the notion of 'words' and 'sentences' from grade school :) If my notation confuses you, you can think of it as a homomorphism $\phi$ between a set of tokens $T$ and a set of words $W \subseteq \Sigma^*$; a sentence $s = t_1 \ldots t_k$ in $T^*$ can then be translated to a word $\phi(s) = \phi(t_1) \ldots \phi(t_k)$ in $\Sigma^*$.  
> **username_2**: Are you sure you want $O(|W|+|S|+|w|+c)$, or would $O(|W|\times|S|\times|w|\times c)$ be ok? I very much doubt the former is possible.  And being linear in each parameter seems already interesting.  
> **username_2**: You state "we can report all meaningful subwords of $w$ in $O(|w|)$ time". I may miss what you mean by "report" or "meaningful subword": I interpret it as enumerating occurences in $w$ of words in $W$. However, even on a single letter alphabet $\Sigma$ there may be $O(|w|\times|W|)$ such occurences. Of course that is still $O(|w|)$ if you consider $|W|)$ a constant. But you ask for a complexity in the sum rather than the product of the sizes. Taking $S=\hat W^*$, which has a very small sized automaton, you get an exponential number of solutions, that will take as much time to be enumerated.  

---

## 3 answers

### Answer by username_2 on 2014-04-01. Score: 2

Here is the first part of the answer (without swapping). I restated some of the definitions to make them clearer (I think), as I was somewhat confused by the statement of the question.

## Introduction to the problem and its practical importance

I do not know the motivation for the question, as it was not given.
However this is a known problem of natural language processing (NLP),
and specifically of speech processing. The problem is that phonems are
not always clearly identifiable, nor are the boundaries between
lexical elements (words), which is a little bit more general than the
question. As a consequence, there can be several ways to cut the
spoken sentence into words of the language. In order to account for
that, the single linear stream of phonems is actually transformed into
what is called a "[word lattice](http://www.statmt.org/moses/?n=Moses.WordLattices)" which may be seen as a
directed acyclic graph or as an acyclic DFA (though even the
acyclicity is also a topic for discussion in some cases - see my
remark on whether the empty word can be in $W$). This word
lattice corresponds to all the ways the sentence can be cut into
recognizable words. This is often based on probabilities and Markov
models.

Well known examples of the need for word lattices are holorime
verses. See for example "[Phonological ambiguity that changes the syntactic structure](https://linguistics.stackexchange.com/questions/3514)".

The word lattices are then used in various way for further linguistic
processing. One use is to do syntax analysis with respect to a
syntactic definition of the language, the identified lexical elements
(or their lexical category, called "part of speech") being used as
alphabet symbols at that syntactic level. In the question asked, the
collection $S$ or sentences plays the role of the language syntax that
defines allowed sentences. The set $W$ is the collection of acceptable
spoken language words that can be built from the phonems in $\Sigma$.
It is a bit simplified from the real speech processing situation. For
example, the set $W$ is finite, while in speech processing it is
considered open (actually finite, but so large ...). This is dealt with
by replacing all the words of a given category by that category
considered as a whole (I skip many details).

Many modern parsing techniques can be readily extended to the parsing
of word lattices, as most syntactic formalisms are closed under
intersection with regular sets. See for example "[Recognition can be
Harder than Parsing](http://bat8.inria.fr/~lang/papers/harder/harder.pdf)".

The problem addressed by word lattices (and by this question) is **lexical
ambiguity**: the ambiguity resulting from the fact that the sequence of
lexical elements that can correspond to the analyzed string is not
unique. This can be opposed to **syntactic ambiguity** du to the fact that the
lexical sequence can be generated syntactically in two different ways,
as in ambiguous context-free grammars.

The issue of character swapping, here supposedly to detect
"spoonerisms", is part of various techniques to deal with input
ill-formedness that can be modeled by finite state tranducers.
Here again, closure properties are more than helpful.

## A solution without swap, linear in each parameter

The set $W$ may be considered finite, as only a finite number of words
in $W$ can be used to form the alphabet for sentences. We assume
furthermore that the empty word is not in $W$. It is not strictly
necessary for the construction given here, but it could make the
parsing yield an arbitrarily long sequence, independently of the
length of the string $w$ being parsed, possibly giving a false idea of
the complexity.

We associate with each word $w\in W$ a unique symbol $\hat w$. Let
$\hat W=\{\hat w \mid w\in W\}$. This is not strictly necessary, but may
avoid confusion as to what is the alphabet.

Then you build a [trie](https://en.wikipedia.org/wiki/Trie), as a DFA that recognizes the words in $W$. Each
final state recognizing a word $w\_k\in W$ is then labeled with $\hat w\_k$
(cf [Moore machines](https://en.wikipedia.org/wiki/Moore_machine)). Then an $\epsilon$-transition is added from each
final state to the initial state, turning the DFA into a NFA that
recognizes sequences of words in $W$, and which can output $\hat w\_k$
whenever $w\_k$ has been recognized. Then you apply the powerset
construction to turn this NFA into a DFA $T\_W$, such that the states of this new
DFA have all the labels of the trie final states they contain.

This construction, though expensive because of the powerset
construction, is done only once, independently of the sentence $w$,
and thus does not count in the complexity analysis. It is amortized over all string $w$ that will be parsed (as is the case for all parser construction techniques).

Given a string $w\in\Sigma^\*$
you build a DFA $L\_{W,w}=(\{q\_i\mid 0\leq i\leq |w|\},\hat W,q\_0,q\_n,\tau\_{W,w})$ as follow:

* $q\_0$ and $q\_n$ are respectively initial and final state
* the number of states is $n+1$
* there is a transition on input $\hat w\_k$ from state $q\_i$ to state
  $q\_j$ iff $w[i:j]=w\_k$ where $w\_k \in W$

The notation $w[i:j]$ denote the substring of $w$ from index $i+1$ to
index $j$, the first letter having index $1$.

This finite state automaton $L\_{W,w}$, called a **[word lattice](http://www.statmt.org/moses/?n=Moses.WordLattices)** in speech
processing, generates or recognizes all sentences that are sequences
of words in $W$ that concatenate into the string $w$. Note that the literature often presents it as a directed acyclic graph rather than a DFA.

To build the transitions, you apply the DFA $T\_W$ to the string
$w$. Whenever you enter a state that has a label $\hat w\_k$ (It may
have several labels), it means
that you have just recognized the string $w\_k\in W$. If you have read
$j$ letters, it means that $w[i:j]=w\_k$ for $i=j-|w\_k|$. Thus you add
the corresponding transition to the word lattice.

The DFA $T\_W$ executes no more than $|w|$ transition steps, and at
each step adds at most $|W|$ transitions to the word lattice.
Hence the complexity is $O(|W|\times|w|)$

Now we have to find out which sentences in the language recognize by
the language of $L\_{W,w}$ are also recognized by the DFA $M\_S$ on alphabet
$\hat W$ recognizing $S$.

In other words we want the intersection of the two languages. This can
be obtained by the usual cross product construction of the two
automata, which are both DFA. The resulting automaton is a recognizer
for the solutions, and can be used to generate them non
deterministically.

Since the set $S$ is a regular set, potentially infinite, each
solution must be given explicitely as a word in $\hat W^\*$, with
corresponding cost, rather than being named in constant time.
However, if the empty word is not in $W$, the length of each solution
is bound by the length of $w$.

The cross product construction gives a number of states that is the
product of that number for each automaton: $|Q\_S|\times(|w|+1)$.
Each of the $|\tau\_S|$ of the DFA $M\_S$ is associated with each of the
$O(|W|\times|w|)$ transitions of the word lattice to determine the
transitions of the cross product.

Hence the cost of producing the DFA for the solutions is $O(|W|\times|w|\times|M\_S|)$

The cross-product DFA is noted $F\_{W,S,w}$. Its construction is such
that its mimics exactly the DFA $S$, but only for the sentences in
$\hat W^\*$ accepted by the word lattice, i.e. all those corresponding
to the sentence $w$. Hence, it does give all the sentences in $S$ as
words in $\hat W^\*$ that are equal letter-wise to $w$.

**Enumerating the solutions**

Here is how you can enumerate the solutions with the DFA $F\_{W,S,w}$
to be conformant to the constraint that the enumeration should be
linear in the size of a trie of all solutions.

We suppose the symbols in $\hat T$ are totally ordered, for example by
the lexicographic order of the corresponding words in $T$. We also
assume that the DFA $F\_{W,S,w}$ has been pruned of all states that do
not have a path to an accepting state, and of transitions to and from
these states (this does not have to exceed the cost of building the
DFA). The missing transitions will be considered as virtually going to
a dead state; they are not needed here.

Let $d$ be the length of the string $w$. Since we
excluded the empty word from $T$, all solutions have a length less
than $d$. Hence the DFA $F\_{W,S,w}$ is acyclic, i.e. represented by an
edge labeled DAG.

Initialize an array $\mathcal S$ of length $d$, indexed from 1 to $d$, storing
the words to be enumerated, and a cursor $c$ indexing the last
modified letter of $\mathcal S$.

Initialize a second array $\mathcal Q$ of length $d+1$, indexed from 0
to $d$, storing the states followed to produce/recognize the current
content of $\mathcal S$. The cursor $c$ indexes also the last visited
state.The array $\mathcal Q$ is initialised with the initial state of
the DFA $F\_{W,S,w}$ at index 0.

Both arrays are used as pushdown stacks, the cursor $c$ pointing at
the top.

Then perform a simulation of a Depth First Search (DFS) on a virtual
version of the trie of all solutions recognized by the DFA
$F\_{W,S,w}$, by updating only the top of the stacks.

When a transition of the DFA is followed, its label is pushed on
$\mathcal S$ and the next state is pushed on $\mathcal Q$.

When a state $q$ has just been pushed on the stack $\mathcal Q$:

* If $q$ is an accepting state the content of stack $\mathcal S$ is a
  solution;
* if $q$ has transitions, follow the one with the smallest label;
* if there are no transitions, then pop both stacks.

When the stacks are popped, let $\hat w$ be the symbol just popped
from $\mathcal S$, and $q$ be the new top of $\mathcal Q$.

* if $q$ has transitions with a label greater than $\hat w$, follow
  the one with the smallest label;
* otherwise pop both stack.

When all transitions of the initial state at the bottom of stack
$\mathcal Q$ have been followed, the enumeration terminates.

This algorithm is essentially a virtual traversal of the trie of all
solutions, because the finite automation $F\_{W,S,w}$ is deterministic
and pruned of unproductive states and transitions. Therefore the time
cost is linear in the size of that trie. The solutions are given in
lexicographic order with respect to $\hat V$.

However, though I have not explored the issue, I fear that the size of
that trie may far exceed the size of the DFA $F\_{W,S,w}$. Even if S is
finite, it may be represented by a DFA that is much smaller than its
trie (precisely our problem).

**Note**:  
$S$ does not have to be a regular set.

The essential ingredients for the solution presented and its
complexity are the deterministic real-time character of the automaton
and the cross product construction. Hence it should be applicable with
the same complexity result if $S$ were a real-time deterministic
context-free language.

More generally, all kinds of languages families may be considered,
with a complexity that depends on recognition complexity of the
family.
For example, if $S$ is a context-free language,
then the complexity for $|w|$ is at worst $O(|w|^3)$. But things get
then more complex: parsing with respect to a regular set for $S$ just
means recognizing $\hat W$-strings in $S$ that expand to the word $w$.
However, if S is a context-free language, one may be satisfied with a
recognizer as in the regular case, but one may also want to have some
or all parses with respect to a specific grammar which may itself be
ambiguous. The complexity analysis may then depend somewhat on what is
actually desired, on language properties or on grammar properties.
And this extend to a variety of other grammatical formalisms.

## Allowing to swap letters

To come later. It can be done also with finite state techniques.

> **Comments:**
> **username_0**: Can you explain how your approach would work in a simple case, e.g. when the set $S$ is an aperiodic regular language? In that case it can be represented by a trie with self-loops (right?), but I don't clearly see how to exploit it. Assuming that we have precomputed the "meaningful" subwords it seems that we should enumerate the sentences in "lexicographic order", i.e. a decomposition $w=w1 \ldots wk$ should be indexed by the tuple $(|w1|,|w2|,\ldots,|wk|)$. Do you see a way to do amortized-constant delay enumeration in that situation?  
> **username_2**: @Super0 I am not sure I understand your question. A finite set is regular, and my construction works for regular sets. The trie for this finite set $S$ of words may be read as a DFA for the finite set. Then the cross-product construction gives you a recognizer, that can be interpreted as a non-deterministic generator. You can the choose a policy for following control branches depths first, choosing them in lexical order of the next label $\hat w_i$. If you wish, you can choose to replace outputting $\hat w_i$ by $w_i$ or by $|w_i|$.  
> **username_2**: I do not see what there is to amortize at this point. I may not understand what you mean by "amortized-constant delay enumeration". I do not know about aperiodic regular languages ... I can look. Maybe if you explain what you consider missing in my construction, I will understand better.  
> **username_2**: @Super0 Actually the method I suggest applies to many families of language for S. However I have to find a good definition of "amortized-constant delay enumeration" to check for sure that this constraint is met (suggestion or reference for a definition are welcome). - - - - - - - - - - - - -  One question, however: are you interested only in recognition (there is nothing else in the regular case), or are you also interested in parse structures when they exist, such as parse trees for CF languages.  
> **username_0**: Thanks for your reply and for the extra motivation :) I agree that if $S$ is described by a DFA then you can reduce to enumerating paths in a dag. But afaik, this only gives a linear-time delay, i.e. the total complexity would be $O(|w| c)$. I was interested in lowering it to $O(|w|+c)$ which should be possible with 'amortized' constant delay, e.g. if the delay is constant on average. Also, extensions to NFAs and grammars would be useful for processing natural languages. If you want to think more about the problem, a useful reference is Ruskey's book 'Combinatorial Generation'.  
> **username_2**: There are $c$ strings of size bound by $|w|$ to enumerate. How do you expect to identify the strings in space (hence time) indpendent of $|w|$. What kind of identification do you expect. You have no bound on the number of strings in $S$ that "parse" your $w$.  How would you do it with an oracle who does not even need to compute? I do not know hown to express the answer with lower complexity, if I am to enumerate the strings. The only other solution is to keep them compacted in a generator or recognizer, which is precisely what I did.  
> **username_0**: You won't change my mind, I still think there's a chance unless you convince me otherwise. Ideally, we would like an enumeration $w_1,\ldots,w_n$ of the words such that $\sum_{i = 1}^{n-1} d(w_i,w_{i+1}) = O(n)$, where $d$ denotes the Hamming distance. This might be too optimistic in general, but this is possible in special cases, e.g. if we have a trie we can traverse it in linear time. We should look at the literature to see if the problem is open though.  
> **username_2**: I did not yet have time to mention it, but it does work for grammars, CF grammars and many others. And it is linear for deterministic grammars as it is for DFA.  
> **username_2**: @Super0 You are suggesting a condensed form, like a trie. Now Can you tell me what is the difference between condensing the answers as a trie or as a finite state generator, which actually will work exactly like a trie and be even more condensed? - - - - - You wanted to enumerate. But I do not see the point.  
> **username_2**: @Super0 OK I see what you want. This April 1st is your lucky day: the DFA that is built with the technique I suggest has no loop.  This is for a very simple reason: the size is limited by $|w|$, and any loop would allow you to pump out. So I guess it is essentially a trie, which you can traverse in linear time. But what do you want that for? Actually it may be a bit better than a trie, with some branch sharing, but that is not a problem regarding traversal, which remain linear w.r.t. the trie size.  
> **username_0**: I think there's a misunderstanding, luck shouldn't play any role of science, for me it's mainly a matter of dedication. Also, there is a difference between a dag and a trie: the latter has a treelike structure while the former may have undirected cycles. It's not known how to enumerate source,sink-paths in a dag with constant delay, so the question is whether the structure of the language/DFA helps..  
> **username_2**: @Super0 How do you enumerate the words in a trie with constant delay, and why will it not work for a DAG? I cannot find references on the web.  
> **username_2**: Your question is misleading. Apparently you want a solution linear in $|w|+c$ rather than in $|w|\times c$. But, rather than an enumerator, you additionally require explicit enumeration of answers, which takes at least $O(|w|\times c)$. If you consider that you can do better, I am asking you to **describe precisely how you do it, assuming you have an oracle that gives you all answers as a trie**, since you claim a trie is enough to do it. You give that trie based procedure, and I will improve my answer. No evasive statement or formula, just the enumeration based on the trie of solutions.  
> **username_2**: @Super0 You state that "*if we have a trie we can traverse it in linear time*". And you apparently see that as an answer to your amortized constant time issue. I am quite willing to accept the idea, but you should be more precise: linear with respect to what parameter(s) of the trie?  
> **username_2**: @Super0 Do you have specific reasons to believe this answer can have a major improvement?  You said nothing of your motivation regarding this question.  

---

### Answer by username_0 on 2014-04-02. Score: 0

*This is not an answer but an extended reply to babou's comment.*

I suggest looking at some literature on constant-delay enumerators, this can usually be done with 'in place' modification. The simplest example is the lexicographical enumeration of a set of the form $[D]^n$ where $D,n$ are integers. If you identify an element of $[D]^n$ with an $n$-digit word in base $D$, it is easy to see that by starting with the word $(0,\ldots,0)$ and by repeatedly apply the successor operation you get an enumerator with amortized constant delay. The intuition is that a chain of $i$ carry propagations happen with probability $1/D^i$, and thus the average time is $\sum\_{i = 1}^{n} i (1/D)^{i-1} (1-\frac{1}{D})$ which is bounded by a function of $D$ only.

More generally, here is how it would work with a trie. Let $d$ be the depth of the trie $T$, initialize an array $w$ of length $d$ storing the words to be enumerated, and a cursor $c$ pointing to the last modified letter of $w$. Perform a dfs of $T$ by updating only the last letter and the cursor: when going back to a parent node move $c$ to the left, when going to a child node write its label under $c$ and move $c$ to the right. It is clear that you get the desired result in time linear in the size in $T$. But this example is not so interesting as it corresponds to a finite language, so the next step would be to look at a star-free language represented by a trie $T$ with self-loops: in that case can you enumerate the words of length $n$ in time $O(|T|+c)$ where $c$ is the number of such words?

> **Comments:**
> **username_2**: Thanks for the explanation. The problem is finding documents. I have no library available right now, and the web has less than one would expect.  
> **username_2**: Here it is as promised. Enumerating the paths of a DAG cannot be linear with respect to the size of the DAG. That much is obvious.  But in the case of the loopless DFA, though enumeration is not linear w.r.t. the DFA size, it can be linear w.r.t. the size of the trie of all solutions. I said as much in my April 1st comment yesterday. **The complexity problem is not in the computation of the solution, but in the size of the solution itself. That cannot be helped very much.** Unless you give up enumerating, and do whatever further processing there is on a condensed representation.  

---

### Answer by username_1 on 2014-03-30. Score: 0

Here is one algorithm. It runs in time at most $O(|S|\*|w| + c)$, and probably runs much faster for many inputs.

We create a directed graph $G$. The graph $G$ has a vertex $(s,i,j)$ for any $s \in S$ and any indices $i,j$ such that $s=w[i..j]$. Then the graph has a directed edge from $(s,i,j)$ to $(s',i',j')$ whenever $i'=j+1$. Finally, the graph has two additional vertices, a source and a sink. There is a directed edge from the source to any vertex of the form $(s,0,j)$ and from any vertex of the form $(s,0,|w|)$ to the sink.

Now notice that the directed paths from the source of the sink correspond exactly to the parsings of $w$. So it's enough to enumerate all (source,sink)-paths in $G$, which can be done in time $O(|G'|+c)$. Note that the graph $G$ kind of represents all the parsings, so for many applications you wouldn't even have to enumerate them explicitly.

> **Comments:**
> **username_2**: I do not understand what you are trying to achieve, but you are not even taking the set $W$ into account in your answer.  
> **username_0**: I think you had essentially the same idea, you both suggested enumerating source,sink-paths in a dag which seems indeed the right approach for a DFA. See my other comment above for possible extensions.  
> **username_2**: @Super0 Maybe, but $W$ is missing  ... so it cannot possibly use all the data. There is necessarily a bug somewhere.  

---

