Patent Document ID: 20020124208
Application ID: 09746695
Patent Status: 0

Claim One:
1. A computer-implemented method for pruning a computation-tree defining a set of model behaviors of a state machine to a subset of the model behaviors, thereby reducing a complexity of the computation-tree and allowing analysis thereof by a computer in a shorter calculation time than would be possible fox the complete computation-tree, said method comprising the steps of: (a) obtaining as input: i) a Finite State Machine, and ii) a Regular Expression defining a set of behaviors that are of interest to the user, (b) using the Regular Expression to construct: i) a finite automaton accepting all prefixes of words accepted by the Regular Expression, and ii) a Boolean expression that realizes a property that the state is part of some path of a behavior defined by the Regular Expression and evaluates to a first logic state for each of said words that are allowable according to the Regular Expression and evaluates to a second logic state otherwise, and (c) exploring the state space of a product machine comprising the Finite State Machine and the constructed finite automaton such that for each state of the product machine there exists a corresponding Finite State Machine component and a corresponding finite automaton component, and for each explored state of the product machine, if the finite automaton component of a currently explored state of the product machine does not satisfy the Boolean Expression, then: (d) pruning the currently explored state from the computation tree so as to abort further exploration from the currently explored state.