Formal Methods in Standards: A Report from the BCS Working Group

3. 1 What are formal methods? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3. 2 A survey of formal methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3. 2. 1 FDTs and FSLs for sequential software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3. 2. 1. 1 VDM (Vienna Development Method). . . . . . . . . . . . . . . . . . . . . 19 3. 2. 1. 2 Z. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3. 2. 1. 3 me too . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3. 2. 1. 4 HOS and AXES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3. 2. 1. 5 Gist. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3. 2. 1. 6 Clear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3. 2. 1. 7 OBJ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3. 2. 1. 8 ACT ONE and ACT TWO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3. 2. 1. 9 CIP-L. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3. 2. 1. 10 LPG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3. 2. 1. 11 Larch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3. 2. 1. 12 Logic languages-the Prolog family. . . . . . . . . . . . . . . . . . . 22 3. 2. 1. 13 Functional languages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3. 2. 2 FDTs and FSLs for concurrent software. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3. 2. 2. 1 LOTOS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3. 2. 2. 2 Estelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3. 2. 2. 3 SDL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3. 2. 2. 4 ASN. l . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3. 2. 2. 5 TTCN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3. 2. 2. 6 Gypsy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3. 2. 3 Graphical formalisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3. 2. 3. 1 Petri nets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3. 2. 3. 2 Higraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3. 2. 4 Less formal methods and notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3. 2. 4. 1 SADT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3. 2. 4. 2 Structured Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3. 2. 4. 3 SSADM and LSDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3. 2. 4. 4 JSPandJSD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3. 2. 4. 5 HDM and the SPECIAL language . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3. 2. 4. 6 Structured analysis and design of real-time systems. . 27 3. 3 Support tools for FDTs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .