next_inactive up previous


A ``Grand Challenge'':
Unifying Theories of Formal Methods
- Integrating Formal Methods -

Dines Bjørner
CSE: Computer Science and Engineering
IMM: Informatics and Mathematical Modelling
Building 322, Richard Petersens Plads
DTU: Technical University of Denmark
DK-2800 Kgs.Lyngby, Denmark
E-Mail: db@imm.dtu.dk, URL: www.imm.dtu.dk/~db

June 18, 2003

THIS PAGE IS PRESENTLY UNDER CONSTRUCTION


Contents

[1.] Background

To be written

[1.1] A Diversity of Formal Techniques and Tools


[1.1.1] A List of Formal Techniques and Tools

  1. ASM: Abstract-State Machines
  2. Action Systems: A refinement calculus for parallel and reactive systems
  3. B France, or B UK - for Bourbaki
  4. CafeOBJ: A rewrite logic and hidden algebra OBJ-like specification and programming language
  5. CASL: Common Algebraic Specification Language
  6. Coq: A proof assistant. Coq, as a project, has been dissolved, 2000. Now see LOGICAL
  7. CSP: Communicating Sequential Processes
  8. Duration Calculi: A continuous time interval temporal logic
  9. Esterel: Synchronous teactive programming
  10. HOL: Higher Order Logic
  11. HyTech: Hybrid Technology -- an automatic tool for the analysis of embedded systems
  12. Isabelle: A generic theorem proving environment
  13. Interval Temporal Logic
  14. Linear Temporal Logic
  15. LSCs: , and Live Sequence Charts
  16. LOGICAL: Logic and computing
  17. Maude: Algebraic semantics based equational and rewriting logic specification and programming language
  18. MSCs: , and Message Sequence Charts, or even this !
  19. Model-checking @ CMU
  20. Nqthm: The Boyer-Moore prover
  21. nuprl: A proof & program refinment logic.
  22. Petri Nets
  23. Pi-Calculus: Calculi for Mobile Processes
  24. PVS: Prototype Verification System
  25. Refinement Calculus
  26. RAISE: Rigorous Approach to Industrial Software Engineering
  27. REACT: The specification, verification and synthesis of concurrent, reactive, real-time and hybrid systems.
    See also STeP: Stanford Temporal Prover.
  28. SpecWare
  29. SPIN: On-the-fly Linear Temporal Logic Model Checking
  30. Statecharts
  31. TLA / TLA+ Temporal Logic of Actions
  32. UNITY: A programming notation and a logic to reason about parallel and distributed programs.
  33. UppAal: An integrated tool environment for modeling, validation and verification of real-time systems
  34. VDM: Vienna Development Method
  35. Z - for Zermelo

[1.1.2] Some Comments on the List

To be written

[1.2] Unifying Theories of Programming

To be written

[1.3] The Integrating Formal Methods Community

Several Integrating Formal Methods (IFM) conferences have been held. Proceedings have been published in Springer-Verlag's Lecture Notes in Computer Scxience Series:

[1.4] From Domains via Requirements to Software -- Some Personal Views

This section can be skipped in any reading. It presents a set of characterisations of the fields of computer & computing science, domain, requirements and software engineering, and the concepts of domain, requirements, model and theory such as the present author of the current document understands these fields. As such the section ``signals'' the didactics ``from'' which the present author of the current document understands the challenge being put forward.

We ``risk'' some characterisations:

Domain

By a(n application) domain we understand an area of (possibly computing supportable) human activity -- such as a bank and its interfaces to its customers, other banks, regulatory agencies, etc.

We are to understand, in the ``narrow'' context of the term `domain', such a domain void of any reference to computing not already in the domain. That is: If the purpose of our trying to understand a domain is - later on - to install computing /and communication) in support of activities of the domain, then (requirements to, let alone software of) that future computing (and communications) is not to be mentioned in the domain.

Model

Theory

When models are formalised, then it is possible to derive properties from the model that are believed to be properties of the domain (being modelled). The set of axioms and inference rules upon which the formal description of the models are based, as well as the possible lemmas, propostions and theorems derived from those axioms and deduction rules, form a theory.

See the last two entries itemised above.

Computing Systems Engineering

Computing systems engineering, to us, is concerned with the development of hardware + software solutions to problems. As such it involves software engineering and hardware engineering and their interplay, usually referred to as co-design. We shall only further characterise software engineering.

Informatics

By informatics we shall understand the confluence of mathematics, computer science cum programming methodology, and applications.

  • Informatics versus Information Technology (IT):

    Informatics relate to IT as biology relates to bio technology, that is ``tangentially''. One embodies the other. Informatics is basically a science and a practice which builds on mathematics (linguistics and philosophy). IT builds on the natural sciences.

  • Abstract, Intellectual Concepts versus Concrete, Material Artifacts:

    IT is characterised by material issues of quantity: Faster, smaller volume, cheaper, large capacity, etc. Informatics can be characterised by issues of intellectual quality: Better ``fit'', more pleasing, elegant, etc.

    IT, in a sense, represents a universe of material quantity. Informatics one of intellectual quality.

[2.] Examples of Unification and/or Integration

Here we plan to give reference to a great number of papers &c.

[2.1] Example 1: RSL with either of CPN, MSC, or Statechart

  • CPN: Coloured Petri Nets
  • MSC: Message Sequence Charts

We refer to the following MSc student project report:

Event Condition, Place Transition and Coloured Petri Nets are explained and formalised in RSL (the RAISE Specification Language ). So are Message Sequence Charts and Statecharts. Then three different, non-trivial examples are expressed in respectively Coloured Petri Nets, Message Sequence Charts and Statecharts. Each of these three examples are then re-stated in RSL.

In Christian Krog Madsen's continued work it is expected that he will (1) define translations from Coloured Petri Nets (CPNs) into RSL, from Live Sequence Charts (LSCs) into Timed RSL, and from Statecharts (SCs) into RSL; (2) then be concerned with these translations satisfying some semantics relations or other; (3) investigating under which conditions reverse translations can occur for certain RSL specifications into respective CPNs, LSCs or SCs.

[2.2] Example 2: ...

To be written

[2.3] Example 3: ...

To be written

...

...
...
...
...
...
...
...
...
...
...

[2.n] Example N: ...

To be written

[3.] The Challenge

[3.1] Some Caveats

In the companion ``Grand Challenge'' for Domain Models & Theories of Transportation Systems & Logistics an assumption was tacitly made:
That the intrinsics of the domain was basically invariant: That indeed, the core parts of a domain model had a stable ``target'' to model.

For the area of `Unifying Theories of Formal Methods - Integrating Formal Methods' the very basics of the problem has been captured in:

  • C.A.R. Hoare and He JiFeng: Unifying Theories of Programming. Prentice Hall, 1997;

but that basis is too abstract. A ``Grand Challenge'' for `Unifying Theories of Formal Methods - Integrating Formal Methods', must, we take as a dogma, start on the basis of existing formal techniques. Some such were tentatively listed in A List of Formal Techniques and Tools. But any such list is temporary: Some of the techniques listed above have endured 30 years (ie., VDM), others have basically been extended (more or less beyond comparison, viz.: LCS and MSC).

Thus the challenge can not only be that of finding suitable pairings (or triplings, etc.) of existing formal techniques and provide ``unifications'' cum ``integrations'' for these ``groupings''. Instead, it is believed, it must also be that of providing such relations whenever a new formal notational tool and its techniques are being put forward.

[3.2] Formulation of the Challenge

To be written

[3.3] Some Comments

To be written

[4.] Modalities of Pursuing The Challenge

To be written

[4.1] Time Frame

The current author of this document presently (ie., June 18, 2003) thinks that it will take at least 10 years, probably more realistically up towards 20 years, before a reasonably complete ``Unification'' will have been both established and generally accepted.

[4.2] Resources

The current author of this document presently (ie., June 18, 2003) expects the following to hold for at least an initial 4-5 years of a ``Grandest Challenge'' project:

  • R&D Sites: That at least some 20 R&D groups be involved, worldwide, in the R&D of such a ``Grandest Challenge'' theory.

  • Site Staffing: That, in any 1/2 year period (ie., winter/spring, summer/fall) at least the following kinds of people are involved at least 40% time in the effort:

    • 1 Site Leader: At least PhD level, experienced staff researcher in computing science, well versed in `formal methods'.

    • 2-3 PhD Students: Well versed in `formal methods', and doing a PhD study well within the `Unification'area. (Since a PhD study is normally three years, it means that new PhD students ``enter'' the ``Grand Challenge'' project every two-three years.)

    • 2 MSc Thesis Students: Well familiar with `formal methods', and doing a MSc Thesis Project well within the use of unified or possibly unifiable techniques. (Since an MSc Thesis Project is normally of 6 months full-time duration, we expect 2 new MSc Students to enter (and, alas, leave) project every six months.)

    • 2-4 MSc Term Project Students: (Since an MSc Thesis Project is normally of 6 months 20% time duration, we expect 2-4 new MSc Students to enter (and, alas, leave) project every six months.)

  • Cross-Site Workshops:

    To be written

  • Yearly ``Grand Challenge'' Symposium:

    To be written

  • &c.

[4.3] Financial Issues

The current author of the present document has the following, somewhat provocative, opinions:

  • No Initial Funding: If the idea of a ``G/G/S Challenge'' is worth anything, then it must be possible to start a ``Unification'' project across 5-10-20 groups worldwide without that project, as such, needing any ``centralised'' yet ``shared'' funding.

    It may be that some of the 5-10-20 worldwide groups are locally funded. No comments.

  • Spontaneous Funding: If results of the first 1-2 years of a non-initially funded ``Grand Challenge'' are worth anything, the project can go on.

    Otherwise it should be curtailed.

    And: If they are worth anything, that ``worth'' should be of such a nature, and so obvious, that local, say software industry, and/or regional, public, say EU, funding agencies wishes to fund - ie., by themselves ought offer to ``ride the band-waggon'', to be associated with an emerging success story.

...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...

/home/db/colognet/web/utopia.tex

About this document ...

A ``Grand Challenge'':
Unifying Theories of Formal Methods
- Integrating Formal Methods -

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.47)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -toc_depth 6 utopia

The translation was initiated by on 2003-06-18


next_inactive up previous
2003-06-18