Determining large-scale finite state machines using constraint relaxation
AssigneeSynopsys, Inc.
InventorNiels Vanspauwen
Life of this patent
Estimating the term…
Abstract
A computer-implemented method of finite state machine using constraint relaxation. A first expression having a plurality of variables is accessed. A second expression is accessed that describes a constraint with respect to a first variable of the plurality of variables. At least one of the variables from the second expression is eliminated to create a third expression with the constraint relaxed. The third expression is applied to the first expression to determine a finite state machine for the first expression.
Claims28
A computer-implemented method of finite state machine creation using a processor comprising:
- a) accessing a first expression comprising a plurality of variables for which a finite state machine is desired;
- b) accessing a second expression that is derived independently of a modification or a reduction of said first expression that describes a constraint with respect to a first variable of said plurality of variables of said first expression;
- c) eliminating at least one variable from said second expression to create a third expression with said constraint modified;
- d) determining an individual finite state machine for said first expression using said third expression wherein a set of rules identify said at least one variable for removal from said second expression;
- and
- e) using said processor creating said individual finite state machine by collapsing multiple states of said individual finite state machine to a single state by merging states that transition to a common state for which inputs and outputs are identical.
A computer-implemented method of relaxing an expression using a processor, comprising:
- a) accessing a first expression;
- b) identifying a variable in said first expression for removal wherein said first expression is derived independently of a modification or a reduction of a second expression;
- c) normalizing said first expression to produce a normalized expression therefrom wherein said normalized expression comprises modified terms;
- d) removing said variable by applying a set of rules to said normalized expression wherein said set of rules identify said variable for removal, wherein said normalized expression is used to determine an individual finite state machine for said second expression after said set of rules are applied to said normalized expression;
- and
- e) using said processor creating said individual finite state machine by collapsing multiple states of said individual finite state machine to a single state by merging states that transition to a common state for which inputs and outputs are identical.
A system comprising a processor and a computer readable medium coupled to a bus, wherein said computer readable medium has stored thereon instructions that when executed on said processor implement a method of finite state machine creation, said system executing a method comprising:
- a) accessing a first expression comprising a plurality of variables for which a finite state machine is desired;
- b) accessing a second expression that is derived independently of a modification or a reduction of said first expression that describes a constraint with respect to a first variable of said plurality of variables of said first expression;
- c) eliminating at least one variable from said second expression to create a third expression with said constraint modified;
- d) determining an individual finite state machine for said first expression using said third expression wherein a set of rules identify said at least one variable in said second expression for removal;
- and
- e) using said processor, creating said individual finite state machine by collapsing multiple states of said individual finite state machine to a single state by merging states that transition to a common state for which inputs and outputs are identical.
A non-transitory computer-readable storage medium having computer-executable instructions, comprising:
- a) accessing a first expression;
- b) identifying a variable in said first expression for removal wherein said first expression is derived independently of a modification or a reduction of a second expression;
- c) normalizing said first expression to produce a normalized expression therefrom wherein said normalized expression comprises modified terms;
- d) removing said variable by applying a set of rules to said normalized expression wherein said set of rules identify said variable for removal, wherein said normalized expression is used to determine an individual finite state machine for said second expression after said set of rules are applied to said normalized expression;
- and
- e) using a processor creating said individual finite state machine by collapsing multiple states of said individual finite state machine to a single state by merging states that transition to a common state for which inputs and outputs are identical.
Dependencies are inferred from the claim text.