Around 1990, various groups began to sense that the methods were sufficiently mature to warrant turning them into commercial tools. With ever-increasing design complexity, the cost of design testing was consuming an ever-greater portion of the design budget - as much as 80% - so more powerful methods for testing became badly needed. However, it soon became evident that what was useful in the hands of experts could not be directly converted into a useful commercial tool. The required methodology change included advancing verification to earlier stages of the development flow. This offered a big potential advantage for reducing development costs, since finding bugs earlier could save more costly fixes later. However, it required that developers participate in the verification process.

We characterize three successively more restrictive classes of ‘effectively linear’ CTL* formulas, with and without fairness: the equi‐linear formulas, which do not distinguish among models with the same language, the sub‐linear formulas, which are preserved under model language inclusion and the strong linear formulas, which are characterized by a given ω‐regular language. Moreover, strong linearity characterizes those CTL* formulas equivalent to LTL formulas. This taxonomy helps to clarify the expressive distinctions between CTL*, LTL and ω‐regular languages. It has also practical implications. Verification tools based on language inclusion can handle any CTL* formula which is equi‐linear, for purposes of model checking, and sub‐linear for purposes of abstraction. Furthermore, minimization techniques that preserve the subset of CTL* which consists of only effectively linear formulas, result in smaller structures than bisimulation minimization.

Timed and hybrid automata are extensions of finite state machines for formal modeling of embedded systems with both discrete and continuous components. Reachability problems for these automata are well studied and have been implemented in verification tools. For the purpose of effective error reporting and testing, we consider the membership problems for such automata. We consider different types of membership problems depending on whether the path (i.e. edge sequence), or the trace (i.e. event sequence), or the timed trace (i.e. timestamped event sequence), is specified. We give comprehensive results regarding the complexity of these membership questions for different types of automata, such as timed automata and linear hybrid automata, with and without /spl epsiv/ transitions. In particular we give an efficient O(n/spl middot/m/sup 2/) algorithm for generating timestamps corresponding to a path of length n in a timed automaton with m clocks. This algorithm is implemented in the verifier COSPAN to improve its diagnostic feedback during timing verification. Second, we show that for automata without /spl epsiv/ transitions, the membership question is NP complete for different types of automata whether or not the timestamps are specified along with the trace. Third, we show that for automata with /spl epsiv/ transitions, the membership question is as hard as the reachability question even for timed traces: it is PSPACE complete for timed automata, and undecidable for slight generalizations.

This tutorial addresses the following questions: ffl why do formal verification? ffl who is doing it today? ffl what are they doing? ffl how are they doing it? ffl what about the future? Introduction Formal methods long have been touted as a means to produce "provably correct implementations". It is only recently, however, with rather more modest claims, that one formal method: modelchecking, has been embraced by industry. In stark contrast with its two-decade development, only the last two years have laid witness to its commercial viability. Nonetheless, in this very short time, this technology has blossomed from scattered pilot projects at a very few commercial sites, into implementations in at least five commercially offered Design Automation tools. This acceleration of activity has even caught the attention of the investment community. Happy graduate students of this technology are basking in an unexpected competition for their talents in an otherwise lack-luster job market. W...

Article Free Access Share on The complexity of verification Author: R. P. Kurshan AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 365–371https://doi.org/10.1145/195058.195194Published:23 May 1994Publication History 7citation599DownloadsMetricsTotal Citations7Total Downloads599Last 12 Months17Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article A unified approach to language containment and fair CTL model checking Share on Authors: Ramin Hojati View Profile , Thomas R. Shiple View Profile , Robert K. Brayton View Profile , Robert P. Kurshan View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 475–481https://doi.org/10.1145/157485.164985Online:01 July 1993Publication History 7citation260DownloadsMetricsTotal Citations7Total Downloads260Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The paper provides a synthesis between two main approaches to automatic verification of finite-state systems: temporal logic model checking and language containment of automata on infinite tapes. A new branching-time temporal logic is suggested, in which automata on infinite tapes are used to define new temporal operators. Each such operator defines a set of acceptable computation paths. Path quantifiers are used to specify whether all paths or some path from a state should be in some acceptable set. The logic is very powerful and includes both linear-time and branching-time temporal logics. We give an efficient model checking procedure that checks whether a finite-state system satisfies its specification, given by a formula of the new logic. Our procedure is linear in the size of the system and a low level polynomial in the size of the specification.

The authors describe a semi-algorithmic method to extract finite-state models from an analog circuit-level model by means of homomorphic (behavior preserving) transformations. Properties to be verified are defined by omega -automata. Efficient algorithms for testing language containment of automata can then be applied to verify properties of the finite-state models. Proof of the property in the finite-state model guarantees the property in the analog circuit-level model over a continuous range of input waveforms and circuit parameters. While in practice this method applies directly only to smaller circuit components, it can be used to analyze larger circuits as well by deriving a hierarchy of increasingly abstract models, through repeated applications of homomorphic transformations. Examples of extraction, homomorphism, and verification are described.>

Article Free Access Share on A structural induction theorem for processes Authors: R. P. Kurshan AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile , K. McMillan Carnegie Mellon University, Pittsburgh, PA Carnegie Mellon University, Pittsburgh, PAView Profile Authors Info & Claims PODC '89: Proceedings of the eighth annual ACM Symposium on Principles of distributed computingJune 1989 Pages 239–247https://doi.org/10.1145/72981.72998Online:01 June 1989Publication History 121citation550DownloadsMetricsTotal Citations121Total Downloads550Last 12 Months19Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF