FACTOID # 22: South Dakota has the highest employment ratio in America, but the lowest median earnings of full-time male employees.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Formal methods

In computer science and software engineering, formal methods are mathematically-based techniques for the specification, development and verification of software and hardware systems.[1] The use of formal methods for software and hardware design is motivated by the expectation that, as in other engineering disciplines, performing appropriate mathematical analyses can contribute to the reliability and robustness of a design.[2] However, the high cost[citation needed] of using formal methods means that they are usually only used in the development of high-integrity systems, where safety or security is important. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Software Engineering (SE) is the design, development, and documentation of software by applying technologies and practices from computer science, project management, engineering, application domains, interface design, digital asset management and other fields. ... Mathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of figures and numbers. Mathematical knowledge is constantly growing, through research and application, but mathematics itself is not usually considered a natural science. ... A formal specification is a mathematical description of software or hardware that may be used to develop an implementation. ... In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of a system with respect to a certain formal specification or property, using formal methods of mathematics. ... Computer software (or simply software) refers to one or more computer programs and data held in the storage of a computer for some purpose. ... Hardware is the general term that is used to describe physical artifacts of a technology. ... Warning signs, such as this one, can improve safety awareness. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

Formal methods can be used at a number of levels:[citation needed]

Level 0: Formal specification may be undertaken and then a program developed from this informally. This has been dubbed formal methods lite. This may be the most cost-effective option in many cases. A formal specification is a mathematical description of software or hardware that may be used to develop an implementation. ...

Level 1: Formal development and verification may be used to produce a program in a more formal manner. For example, proofs of properties or refinement from the specification to a program may be undertaken. This may be most appropriate in high-integrity systems involving safety or security. Software development is the translation of a user need or marketing goal into a software product. ... In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of a system with respect to a certain formal specification or property, using formal methods. ... The word selectivity has more meanings: Selectivity, the ability to notice/distinguish small diferences. ... A formal specification is a mathematical description of software or hardware that may be used to develop an implementation. ... Warning signs, such as this one, can improve safety awareness. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

Level 2: Theorem provers may be used to undertake fully formal machine-checked proofs. This can be very expensive and is only practically worthwhile if the cost of mistakes is extremely high (e.g., in critical parts of microprocessor design). Automated theorem proving (currently the most important subfield of automated reasoning) is the proving of mathematical theorems by a computer program. ...

Further information on this is expanded below.

As with the sub-discipline of programming language semantics, styles of formal methods may be roughly classified as follows: In theoretical computer science formal semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation. ...

• Denotational semantics, in which the meaning of a system is expressed in the mathematical theory of domains. Proponents of such methods rely on the well-understood nature of domains to give meaning to the system; critics point out that not every system may be intuitively or naturally viewed as a function.
• Operational semantics, in which the meaning of a system is expressed as a sequence of actions of a (presumably) simpler computational model. Proponents of such methods point to the simplicity of their models as a means to expressive clarity; critics counter that the problem of semantics has just been delayed (who defines the semantics of the simpler model?).
• Axiomatic semantics, in which the meaning of the system is expressed in terms of preconditions and postconditions which are true before and after the system performs a task, respectively. Proponents note the connection to classical logic; critics note that such semantics never really describe what a system does (merely what is true before and afterwards).

In computer science, denotational semantics is an approach to formalizing the semantics of computer systems by constructing mathematical objects (called denotations or meanings) which express the semantics of these systems. ... Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. ... In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way (See formal semantics of programming languages). ... Axiomatic Semantics is an approach based on mathematical logic to proving the correctness of computer programs. ... In logic a precondition is a condition that has to be met, before a main argument can have any value. ... A postcondition is a fact that must always be true just after the execution of some section of code. ... Logic, from Classical Greek Î»ÏŒÎ³Î¿Ï‚ (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason) is the study of criteria for the evaluation of arguments, although the exact definition of logic is a matter of controversy among philosophers. ...

### Lightweight formal methods

Some practitioners believe that the formal methods community has overemphasized full formalization of a specification or design.[3][4] They contend that the expressiveness of the languages involved, as well as the complexity of the systems being modelled, make full formalization a difficult and expensive task. As an alternative, various lightweight formal methods, which emphasize partial specification and focused application, have been proposed. Examples of this lightweight approach to formal methods include the Alloy object modelling notation,[5] Denney's synthesis of some aspects of the Z notation with use case driven development,[6] and the CSK VDMTools.[7] The Alloy specification language is a simple structural modelling tool based on first-order logic. ... The Z notation (universally pronounced zed, named after Zermelo-FrÃ¤nkel set theory) is a formal specification language used for describing and modelling computing systems. ... In software engineering and system engineering, a use case is a technique for capturing functional requirements of systems and systems-of-systems. ... Vienna Development Method (VDM) is a program development method based on formal specification using the VDM specification language (VDM-SL), with tool support. ...

## Uses

Formal methods can be applied at various points through the development process. (For convenience, we use terms common to the waterfall model, though any development process could be used.) This does not cite its references or sources. ... The waterfall model is a sequential software development model (a process for the creation of software) in which development is seen as flowing steadily downwards (like a waterfall) through the phases of requirements analysis, design, implementation, testing (validation), integration, and maintenance. ...

### Specification

Formal methods may be used to give a description of the system to be developed, at whatever level(s) of detail desired. This formal description can be used to guide further development activities (see following sections); additionally, it can be used to verify that the requirements for the system being developed have been completely and accurately specified.

The need for formal specification systems has been noted for years. In the ALGOL 60 Report, John Backus presented a formal notation for describing programming language syntax (later named Backus normal form or Backus-Naur form (BNF)); Backus also described the need for a notation for describing programming language semantics. The report promised that a new notation, as definitive as BNF, would appear in the near future; it never appeared. ALGOL (short for ALGOrithmic Language) is a programming language originally developed in the mid 1950s which became the de facto standard way to report algorithms in print for almost the next 30 years. ... John Backus (born December 3, 1924) is an American computer scientist, notable as the inventor of the first high-level programming language (FORTRAN), the Backus-Naur form (BNF, the almost universally used notation to define formal language syntax), and the concept of Function-level programming. ... The Backus-Naur form (BNF) (also known as Backus normal form) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. ... The Backus-Naur form (BNF) (also known as Backus normal form) is a metasyntax used to express context-free grammars: that is, a formal way to describe formal languages. ...

### Development

Once a formal specification has been developed, the specification may be used as a guide while the concrete system is developed (i.e. realized in software and/or hardware). Examples:

• If the formal specification is in an operational semantics, the observed behavior of the concrete system can be compared with the behavior of the specification (which itself should be executable or simulateable). Additionally, the operational commands of the specification may be amenable to direct translation into executable code.
• If the formal specification is in an axiomatic semantics, the preconditions and postconditions of the specification may become assertions in the executable code.

In computer programming, an assertion statement is a programming language construct that indicates an assumption on which the program is based. ...

### Verification

Once a formal specification has been developed, the specification may be used as the basis for proving properties of the specification (and hopefully by inference the developed system). In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true. ...

#### Human-Directed Proof

Sometimes, the motivation for proving the correctness of a system is not the obvious need for re-assurance of the correctness of the system, but a desire to understand the system better. Consequently, some proofs of correctness are produced in the style of mathematical proof: handwritten (or typeset) using natural language, using a level of informality common to such proofs. A "good" proof is one which is readable and understandable by other human readers. In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true. ... The term natural language is used to distinguish languages spoken and signed (by hand signals and facial expressions) by humans for general-purpose communication from constructs such as writing, computer-programming languages or the languages used in the study of formal logic, especially mathematical logic. ...

Critics of such approaches point out that the ambiguity inherent in natural language allows errors to be undetected in such proofs; often, subtle errors can be present in the low-level details typically overlooked by such proofs. Additionally, the work involved in producing such a good proof requires a high level of mathematical sophistication and expertise. Look up ambiguity in Wiktionary, the free dictionary. ...

#### Automated Proof

In contrast, there is increasing interest in producing proofs of correctness of such systems by automated means. Automated techniques fall into two general categories:

• Automated theorem proving, in which a system attempts to produce a formal proof from scratch, given a description of the system, a set of logical axioms, and a set of inference rules.
• Model checking, in which a system verifies certain properties by means of an exhaustive search of all possible states that a system could enter during its execution.

Neither of these techniques work without human assistance. Automated theorem provers usually require guidance as to which properties are "interesting" enough to pursue; model checkers can quickly get bogged down in checking millions of uninteresting states if not given a sufficiently abstract model. Automated theorem proving (currently the most important subfield of automated reasoning) is the proving of mathematical theorems by a computer program. ... Model checking is a method to algorithmically verify formal systems. ...

Proponents of such systems argue that the results have greater mathematical certainty than human-produced proofs, since all the tedious details have been algorithmically verified. The training required to use such systems is also less than that required to produce good mathematical proofs by hand, making the techniques accessible to a wider variety of practitioners.

Critics note that such systems are like oracles: they make a pronouncement of truth, yet give no explanation of that truth. There is also the problem of "verifying the verifier"; if the program which aids in the verification is itself unproven, there may be reason to doubt the soundness of the produced results. In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ...

## Criticisms

In addition to the internal criticisms mentioned above, the field of formal methods as a whole has its critics. At the current state of the art, proofs of correctness, whether handwritten or computer-assisted, need significant time (and thus money) to produce, with limited utility other than assuring correctness. This makes formal methods more likely to be used in fields where the benefits of having such proofs, or the danger in having undetected errors, makes them worth the resources. Example: in aerospace engineering, undetected errors may cause death, so formal methods are more popular than in other application areas. Aerospace engineering is the branch of engineering that concerns aircraft, spacecraft, and related topics. ... This article or section does not cite its references or sources. ...

At times, proponents of formal methods have claimed that their techniques would be the silver bullet to the software crisis. Of course, it is widely believed that there is no silver bullet for software development, and some have written off formal methods due to those overstated, overreaching claims. The metaphor of the silver bullet applies to any straightforward solution perceived to have extreme effectiveness. ... The software crisis was a term used in the early days of software engineering, before it was a well-established subject. ... No Silver Bullet is a well-known paper on software engineering written by Fred Brooks in 1987. ...

## Formal methods and notations

There are a variety of formal methods and notations available, including

Abstract State Machines (ASM), formerly known as Evolving Algebras, are a formal method for specification and verification. ... The Alloy specification language is a simple structural modelling tool based on first-order logic. ... B is a tool-supported formal method based around AMN (Abstract Machine Notation), used in the development of computer software. ... The process calculi (or process algebras) are a diverse family of related approaches to formally modelling concurrent systems. ... In computer science, Communicating Sequential Processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. ... In theoretical computer science, the &#960;-calculus is a notation originally developed by Robin Milner, Joachim Parrow and David Walker to model concurrency (just as the &#955;-calculus is a simple model of sequential programming languages). ... In computer science, the Actor model is a mathematical model of concurrent computation that has its origins in a 1973 paper by Carl Hewitt, Peter Bishop, and Richard Steiger. ... Esterel is a formally defined synchronous imperative language for the programming of reactive systems. ... Lustre is a formally defined, declarative, and synchronous data-flow programming language, for programming reactive systems. ... A Petri net (also known as a place/transition net or P/T net) is one of several mathematical representations of discrete distributed systems. ... RAISE (Rigorous Approach to Industrial Software Engineering) was developed as part of the European ESPRIT II LaCoS project in the 1990s, led by Dines BjÃ¸rner. ... Vienna Development Method (VDM) is a program development method based on formal specification using the VDM specification language (VDM-SL), with tool support. ... The Z notation (universally pronounced zed, named after Zermelo-FrÃ¤nkel set theory) is a formal specification language used for describing and modelling computing systems. ...

Automated theorem proving (currently the most important subfield of automated reasoning) is the proving of mathematical theorems by a computer program. ... Model checking is a method to algorithmically verify formal systems. ... Software Engineering (SE) is the design, development, and documentation of software by applying technologies and practices from computer science, project management, engineering, application domains, interface design, digital asset management and other fields. ... Rebeca (Reactive Objects Language) is an actor-based language with a formal foundation, designed in an effort to bridge the gap between formal verification approaches and real applications. ...

## References

1. ^ R. W. Butler (2001-08-06). What is Formal Methods?. Retrieved on 2006-11-16.
2. ^ C. Michael Holloway. "Why Engineers Should Consider Formal Methods". 16th Digital Avionics Systems Conference (27-30 October 1997). Retrieved on 2006-11-16.
3. ^ Daniel Jackson and Jeannette Wing, "Lightweight Formal Methods", IEEE Computer, April 1996
4. ^ Vinu George and Rayford Vaughn, "Application of Lightweight Formal Methods in Requirement Engineering", Crosstalk: The Journal of Defense Software Engineering, January 2003
5. ^ Daniel Jackson, "Alloy: A Lightweight Object Modelling Notation", ACM Transactions on Software Engineering and Methodology (TOSEM), Volume 11, Issue 2 (April 2002), pp. 256-290
6. ^ Richard Denney, Succeeding with Use Cases: Working Smart to Deliver Quality, Addison-Wesley Professional Publishing, 2005, ISBN 0-321-31643-6.
7. ^ Sten Agerholm and Peter G. Larsen, "A Lightweight Approach to Formal Methods", In Proceedings of the International Workshop on Current Trends in Applied Formal Methods, Boppard, Germany, Springer-Verlag, October 1998

I am missing a number of references: 2006 (MMVI) is a common year starting on Sunday of the Gregorian calendar. ... November 16 is the 320th day of the year (321st in leap years) in the Gregorian Calendar, with 45 days remaining. ... 2006 (MMVI) is a common year starting on Sunday of the Gregorian calendar. ... November 16 is the 320th day of the year (321st in leap years) in the Gregorian Calendar, with 45 days remaining. ...

1. David Gries, the science of programming 2. C. Hoare, lots of articles about proving programs 3. E. Dijkstra, another writer who has written a lot about proofing programs, especially about semaphores and such.

Results from FactBites:

 Formal methods - Wikipedia, the free encyclopedia (1414 words) Formal methods are particularly effective early in development at the requirements and specification levels, but can be used for a completely formal development of an implementation (e.g., a program). Formal methods may be used to give a description of the system to be developed, at whatever level(s) of detail desired. At times, proponents of formal methods have claimed that their techniques would be the silver bullet to the software crisis.
More results at FactBites »

Share your thoughts, questions and commentary here