3
$\begingroup$

For a given finite alphabet $\Sigma$, my goal is to write an algorithm that receives as input a sequence $V=V_{1}V_{2}\dots V_{n}$ of subsets ($V_{i}\subseteq\Sigma$), and returns a weighted deterministic finite-state automaton with the following property: for every input string $s$, the automaton penalizes each substring $s_{1}s_{2}\dots s_{n}$ of $s$ if $s_{i}\in V_{i}$ for every $1\le i\le n$.

For example, if $\Sigma=\{a,b\}$, $V=V_{1}V_{2}=\{b\}\{b\}$, the returned automaton would penalize the string $s=bbbb$ $3$ times, i.e. when accepting the string and summing over the weighted arcs, the result would be $3$.

The algorithm should return the weighted DFA as a 4-tuple $<Q,\delta ,q_0 , F>$:

$Q=\{q_{0},q_{1}\}$

$\delta=\{(q_{0},a,0,q_{0}),(q_{0},b,0,q_{1}),(q_{1},b,1,q_{1}),(q_{1},a,0,q_{0})\}\subseteq Q\times\Sigma\times\{0,1]\times Q$

$q_{0}=q_{0}$

$F=\{q_{0},q_{1}\}$

The algorithm must return the DFA as a 4-tuple as described. My main concern is the size of the resulting DFA. Therefore, the structure of $V$ should be taken advantage of. Capitalizing on subset relations, it is possible to eliminate states from the resulting automaton. For example, when all subsets are pairwise disjoint, the automaton would have $n$ states.

The problem arises in the general case, where the inclusion relation between subsets is unknown.

For example, if $\Sigma=\{a,b,c,d,e\}$ and $V=\{a,b\}\{b,c,d\}\{d,e\}$, the string $abde$ should be penalized twice (both $abd$ and $bde$ are penalized), where $acde$ should be penalized only once ($acd$ is penalized, but not $cde$). This happens since there is a chain of non-empty intersections between subsets $(V_{1}\cap V_{2},V_{2}\cap V_{3}\not=\emptyset)$, so having accepted a penalized substring, some paths taken must be remembered in order to know how to move on. Paths in the required automaton would have to be splitted accordingly. In this case the resulting automaton could be minimally built with 5 states.

When the sequence is longer, there is a chance for more complex inclusion relations between its subsets.

I'm interested in a general algorithmic solution for this problem, currently not in any implementation or performance considerations. As stated, my main concern is the size of the DFA.

Any insight, reference or suggestion on how to tackle this problem would be appreciated.

More specifically, I'm now trying to figure out how to capitalize on inclusion relations between subsets in order to eliminate states (in advance) when building the DFA.

EDIT: Added a paragraph and a final comment about using the structure of V to minimize the DFA, emphasis on my need of a smallest DFA as possible.

$\endgroup$
  • $\begingroup$ In what form do you want the DFSA -- a state/input/output graph? Or would an algorithm in a programming language do? If the latter, then why pose this as a DFSA? Do you have a system that executes DFSAs, and if so, what model does it expect? Is the need for a "pre-compiled" DFSA motivated by performance considerations, that is, there's a ton of data to process and/or it needs to be done quickly, perhaps in real time?. In any case, it will help a lot to explain the context of the problem in more detail. There could be complex optimization issues, but without the context, it's hard to say. $\endgroup$ – David Lewis Apr 29 '12 at 16:51
  • $\begingroup$ Thanks for your input. I've added an example DFA which is expected by the system, and a statement that "I'm interested in a general algorithmic solution for this problem, currently not in any implementation or performance considerations." These would certainly be in interest after I manage to better understand the problem and the solution. $\endgroup$ – ezer Apr 29 '12 at 18:46
  • $\begingroup$ As far as feasibility, one can construct an NFA from your regular expression (/[ab][bcd][de]/ in your example) and just count the number of times it hits the 'accept' state. In general, you pay an exponential increase in size when transitioning from an NFA to a DFA but I'm not sure about your specific case. If this question is only asking for an algorithm to count the number of occurrences of a regular expression in a string, then perhaps this question is best suited to the CS SE. If this question is really asking for a polynomial sized DFA, then you should make that clear. $\endgroup$ – user834 Apr 29 '12 at 21:13
  • $\begingroup$ I am indeed in need for a small as possible DFA. I have added a clarification. $\endgroup$ – ezer Apr 30 '12 at 12:27
4
$\begingroup$

I'm still not sure why you want it in strict quadruple form, with a set of structure-less states. That's a model that mainly intended for doing the abstract mathematics surrounding state-transition systems, but famously ill-suited to actual computation unless you are looking for the extreme speed offered by "pre-compiling" into deterministic form, at the expense of storage space.

User834 is correct that this is a fairly simple sub-problem of regular expression matching, with the added feature of counting matches, so you may take my solution in that vein. I'm not a RE maven, but I think there is a way to get match counting out of REs in most implementations. So that's an approach you might consider for practical implementation without all the trouble of constructing your own FSAs.

I also agree that this probably belongs in the CS area rather than theoretical CS.

If I read your problem correctly, it amounts to taking a set of strings $V$ and looking for every occurrence of a string in $V$ as a maximal substring (prefix, suffix or interior) of $x$, the input to the DFSA we'll call $D$. That count is the "penalty" for $x$. Here's one way to do it, though following your prescription not to worry about performance, takes no advantage of any structure or redundancy in $V$.

In your example, $V=\{abd, abe, acd, ace, add, ade, b...\}$. Pre-multiply all the sets $V_i$ into strings of $V$ in tree form, with elements of $V_i$ all on level $i$, each descended directly from each element of $V_{i-1}$. Level $0$ is an abstract root, say $\epsilon$. For your example, descended from $\epsilon$ are $a$ and $b$, the elements of $V_1$. On level 2, descended from each of $a$ and $b$ are the members of $V_2$: $b$, $c$ and $d$. So there are 6 nodes on level 2 altogether, the 3 members of $V_2$ repeated twice. And so on to the leaves. Each path from $\epsilon$ to a leaf of the tree represents one "penalty string" in V. You did not make clear what happens if a string appears more than once in $V$. If you don't want it to count for multiple penalties, then you should prune duplicate strings out of the tree by some suitable algorithm.

Construct the a non-deterministic FSA $D'$ as follows. States of $Q$ are pointers to nodes of the tree. Each state thus represents a complete string in $V$ or a prefix of such a string, to be represented here by $[x]$ (though that $x$ isn't unique to a node -- I assume there is a pointer to the actual node of the tree). The transition function $\delta$ contains three kinds of edges:

$\langle[x],a,0,[xa])\rangle$ where $a$ is a direct descendant of $[x]$, and $[xa]$ is that descendant node. Note that we output 0 at this point because we aren't sure we've reached the maximal match.

$\langle[x],a,1,[])\rangle$ where $a$ is not a direct descendant of $[x]$ in the tree, and $[]$ is a dead state. We output $1$ here because $[x]$ is matched but it is maximal, since $[xa]$ is not matched.

If we were dealing with prefixes only and not interior and suffix matches, we'd be done and this would be a deterministic automaton. To account for non-prefixes, we need to non-deterministically circle back to $[\epsilon]$, the start state, at every stage with an edge like this for every state $[x]$ except $[\epsilon]$ and $[]$:

$\langle[x], \epsilon, 0, [\epsilon]\rangle$

Convert that NFSA to a DFSA and you are done.

$\endgroup$
  • $\begingroup$ Thank you very much. This is definitely an easier way to look at the problem. My main concern, which I should have clarified in advance, is the size of the resulting DFA. Since converting an NFA (especially the one in question) might be costly in terms of size, I'm trying to directly build a DFA, and for it to be as small as possible it seems that the structure of V must be taken full advantage of. Converting an NFA and then simplifying it, the problem of structure still remains. $\endgroup$ – ezer Apr 30 '12 at 12:19
  • 2
    $\begingroup$ Size can be addressed -- for example represent multiple states in some very efficient fashion using bit-packing or small numbers. But I'm still curious why it is an issue? Is this going on some minuscule device and/or V is very large? Again, a more complete description of your specs -- including environment, amount of data, size of V, space available, speed requirements, etc -- would help us answer. And this definitely belongs in the CS area, not Theoretical CS -- any moderators listening in? $\endgroup$ – David Lewis Apr 30 '12 at 16:29
  • $\begingroup$ Sorry for the late response. By "size" of the DFA I mean the number of states in it. Many such DFAs are going to be created once, then intersected repeatedly in different variations. The resulting intersected DFA will be run (many times) through algorithms with runtime up to quartic in the number of states. That is why a large DFA will be very costly in the long run. The solution I'm looking for would not depend on the size of the subsets of V (since arcs should be merged) and use as few states as possible. Would you recommend reposting the question in the CS area? $\endgroup$ – ezer May 4 '12 at 0:32
  • $\begingroup$ @ezer -- thanks for the new information. Sounds like a substantially more complex project, with this is only a part. Are you sure you are not suboptimizing by picking out this one subproblem for independent solution? By "intersected DFA will be run through algorithms" do you mean it will be executed, or used to build other automata or objects? As for minimizing states, you can always do that algorithmically with the DFA you get from my procedure (which, by the way, has mistakes). Another approach might be to base the whole thing on regular expressions. Tough to tell. $\endgroup$ – David Lewis May 4 '12 at 2:40
  • $\begingroup$ @ezer -- as for posting on CS rather than TCS -- might make sense, but I'm not sure. I'm relatively new in both, but it does sound like an implementation problem as much as a theoretical one. You might look around for similar stuff to see if yours fits. OTOH, your whole project might be too big and complex for SE altogether, more of a consulting job. I don't know if it's kosher to say this here, but if you want to talk about consulting, I'd be interested. $\endgroup$ – David Lewis May 4 '12 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.