Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to explore $M$, i.e., visit every state of $M$, or as many states as possible. Unfortunately, I'm not given $M$; I only have the ability to send inputs to $M$.

In particular, what I can do is specify some input strings $x,y,\dots \in \Sigma^*$. The string $x$ will drive $M$ down some path, namely, down the sequence of states $s_0,s_1,s_2,\dots$ where $s_{i+1} = \delta(s_i,x_i)$. I can specify as many input strings as I want.

The cost to me is the sum of the lengths of the input strings. In other words, each transition costs me \$1.

The benefit to me is the fraction of $M$'s states that are visited at least once in response to at least one of these input strings.

I have complete freedom to choose the set of input strings, but I am not given any feedback (I can't see the sequence of states that $M$ follows, I don't learn when I've visited a new state, etc.). I'm hoping to get as much coverage of $M$'s statespace as possible.

How should I choose the set of input strings to maximize the coverage while minimizing the cost? For instance, given a fixed budget, what's the best set of input strings that will give the best benefit? Is there a reasonable strategy, or any theory to help guide the choice of input strings?


Of course, I realize that the worst-case coverage, taken over all possible DFAs, might be very poor. But I would be satisfied with any approach that one can argue is close to optimal, in any meaningful sense. For instance, maybe one metric might be to use a regret ratio, where the regret of strategy 1 compared to strategy 2 is the maximum, over all DFA's $M$, of the benefit of strategy 2 on $M$ divided by the benefit of strategy 1 on $M$. Or maybe you can suggest some other way to formulate this in a principled way that admits an interesting solution. I'm open to suggestions about how to formulate the problem in a way that permits analysis.

If it's helpful, I'll promise that the alphabet is small (say, $|\Sigma| \le 10$), the number of states is not too large (say, $|S| \le 1000$), and the diameter of the graph is small (say, at most 10).

I'm also interested in the variant where $M$ is a NFA instead of a DFA, but I thought I'd start with the simpler case.

This is an attempt at an application of theory to practice. The application is randomized testing of UI-driven applications, where we think of the application as a DFA and the inputs represent user actions (e.g., tapping on a particular portion of the screen). The problem above is an idealization of the problem where we don't get any feedback as we go (which is motivated by the fact that it's not trivial to observe anything reliable about the state of the application).

  • After sending an input do I get as feedback the percentage of state visited? – Marzio De Biasi Oct 25 '13 at 22:04
  • @MarzioDeBiasi, no, you don't. (In practice you might get some feedback, but it's very unreliable, which is why I wanted to start to see how good you can do without any feedback at all. So I'd prefer to say "no" and see how good a solution we can get without any feedback.) – D.W. Oct 25 '13 at 22:10
  • D.W. ok, what is exactly the "total" benefit function to maximize (it should be a function of both the transition cost, and the final percentage of covered states) ? – Marzio De Biasi Oct 25 '13 at 22:12
  • P.S. I'm not an expert, but perhaps the problem is similar to the cover time in a Markov-chain (with n-states and equal probability on the outgoing transitions). See also cover time of DAGs (e.g. cstheory.stackexchange.com/questions/2908/…) – Marzio De Biasi Oct 25 '13 at 22:29
  • 1
    I fear you may need a lot more features from this model to get good results. As an adversary, I'd pick $s$, the shortest string that doesn't appear as a prefix in your set of words. Then, I'd construct $M$ to force all inputs not containing $s$ as a prefix into a single sink state and put as many states as I'd like corresponding to strings with $s$ as a prefix. To beat this adversary, all you could do is pick your set of words to be the set of all words (of a given length). – mhum Oct 25 '13 at 23:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.