« That song from Crossing Jordan | Main | Blog upgrade info »
August 04, 2004
"To store or not to store" by Behrmann, Larsen and Pelanek
[Google Search: "to store or not to store" , The paper] The idea is to store only enough states to expand every state at least once. This is done by storing one state per cycle. Various heuristics are used to find a single state per cycle to store from the components of the network fo automata representing the system under test.
Our approach is on the fly. We compute the states to store as we find them, rather than beforehand. The difficulty is that we will have a hard time proving that we expand every state at least once if we don't start with the assumption that we store at least one state per cycle and work toward that. However, our on the fly algorithm may guarunte that.
They note that storing the waiting states (ie, waiting to be expanded) in a queue rather than a stack significanlty reduces the revisit count. This is because the bfs you get from a queue often contains the revisited state already when it would have been revisited. This is not the case in dfs. However, we note that bfs queues often get much longer than dfs stacks so this seems to be another time/space tradeoff. Good to know though.
Posted by jones at August 4, 2004 02:23 PM
Comments
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)