The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Implicit state enumeration for extended finite state machines relies on a decision procedure for Presburger arithmetic. We compare the performance of two Presburger packages, the automata-based Shasta package and the polyhedrabased Omega package. While the raw speed of each of these two packages can be superior to the other by a factor of 50 or more, we found the asymptotic performance of Shasta to...
We describe a method for reducing the complexity of temporal logic model checking of a system of interacting finite state machines, and prove that it yields correct results. The method consists essentially of reducing each component machine with respect to the property we want to verify, and then verifying the property on the composition of the reduced components. We demonstrate the method on a simple...
BDD-based implicit state enumeration usually fails for systems with wide numeric datapaths. It may be possible to take advantage of higher level structure in designs to improve efficiency. By treating the integer variables as atomic types, rather than breaking them into individual bits, one can perform implicit state enumeration using Presburger arithmetic decision procedures; the complexity of this...
We present a state equivalence that is defined with respect to a given CTL formula. Since it does not attempt to preserve all CTL formulas, like bisimulation does, we can expect to compute coarser equivalences. We use this equivalence to manage the size of the transition relations encountered when model checking a system of interacting FSMs. Specifically, the equivalence is used to reduce the size...
Given a Free BDD for the characteristic function of an input-output relation T(x, y), we show how to construct a combinational logic circuit satisfying that relation. Such relations occur as environmental constraints for module specifications, as parts of a proof strategies, or can be computed from existing circuits, e.g., by formal analysis of combinational cycles. The resulting circuit C can be...
We classify gate level circuits with cycles based on their stabilization behavior. We define a formal class of combinational circuits, the constructive circuits, for which signals settle to a unique value in bounded time, for any input, under a simple conservative delay model, called the up-bounded non-inertial (UN) delay. Since circuits with combinational cycles can exhibit asynchronous behavior,...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.