On tabular expressions

ABSTRACT

Tabular expressions (Parnas et al. [18, 26, 28, 29]) are a means to represent the complex relations that are used to specify or document software systems. A formal model and a semantics for tabular expressions are presented. The model covers most known types of tables used in Software Engineering, and admits precise classification and definition of new types of tables. The practical importance of the semantics of tabular expressions is discussed briefly.

REFERENCES

• 1: {1} R. Abraham, Evaluating Generalized Tabular Expressions in Software Documentation, M. Eng. Thesis, Dept. of Electrical and Computer Engineering, McMaster University 1997, also CRL Report 346, McMaster University, Hamilton, Ontario, Canada, 1997.
• 2: Alfred V. Aho , Jeffrey D. Ullman, Foundations of computer science, Computer Science Press, Inc., New York, NY, 1992
• 3: {3} G. H. Archinoff, R. J. Hohendorf, A. Wassyng, B. Quigley, M. R. Borsch, Verification of the Shutdown System Software at the Darlington Nuclear Generating Station, International Conference on Control and Instrumentation in Nuclear Installations , Glasgow, U.K., 1990, No. 4.3.
• 4: {4} P. C. Clements, Function Specification for the A- 7E Function Driver Module, NRL Memorandum Report 4658, U.S.Naval Research Lab., 1981.
• 5: {5} J. Desharnais, R. Khédri, A. Mili, Towards a Uniform Relational Semantics for Tabular Expressions, Proc. of RELMICS 98, Warsaw 1998.
• 6: {6} P. R. Halmos, Naive Set Theory, Springer 1960.
• 7: Mats P. E. Heimdahl , Nancy G. Leveson, Completeness and consistency analysis of state-based requirements, Proceedings of the 17th international conference on Software engineering, p.3-14, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225015]
• 8: {8} C. Heitmeyer, A. Bull, C. Gasarch, B. Labaw, SCR* : A Toolset for Specifying and Analyzing Requirements, Proc. 9th Annual Conf. on Computer Assurance (COMPASS'95), Gaithersburg, MD, 1995.
• 9: {9} K. L. Heninger, Specifying Software Requirements for Complex Systems: New Techniques and their Applications, IEEE Transactions on Software Engineering , 6, 1, (1980), 2-13.
• 10: {10} K. L. Heninger, J. Kallander, D. L. Parnas, J. E. Shore, Software Requirements for the A-7E Aircraft, NRL Memorandum Report 3876, U.S.Naval Research Lab., 1978.
• 11: {11} D. N. Hoover, Z. Chen, Tablewise, a Decision Table Tool, Proc. 9th Annual Conf. on Computer Assurance (COMPASS'95), Gaithersburg, MD, 1995.
• 12: Richard B. Hurley, Decision Tables in Software Engineering, John Wiley & Sons, Inc., New York, NY, 1983
• 13: Ryszard Janicki, Towards a formal semantics of Parnas tables, Proceedings of the 17th international conference on Software engineering, p.231-240, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225036]
• 14: {14} R. Janicki, On Formal Semantics of Tabular Expressions, CRL Report 355, McMaster University, Hamilton, Ontario 1997.
• 15: {15} R. Janicki, Remarks on Mereology of Direct Products and Relations, in J. Desharnais, M. Frappier, W. MacCaull (eds.), Relational Methods in Computer Science, Methodos Publ. 2002, pp.65-84.
• 16: Ryszard Janicki , Ridha Khedri, On a formal semantics of tabular expressions, Science of Computer Programming, v.39 n.2-3, p.189-213, March 2001 [doi>10.1016/S0167-6423(00)00004-6 ]
• 17: {17} R. Janicki, P.E. Lauer, Specification and Analysis of Concurrent Systems: The COSY Approach, EATCS Monographs on Theoretical Computer Science, Volume 26, Springer-Verlag 1992.
• 18: Ryszard Janicki , David Lorge Parnas , Jeffery Zucker, Tabular representations in relational documents, Relational methods in computer science, Springer-Verlag New York, Inc., New York, NY, 1997
• 19: {19} R. Khédri, Requirements Scenarios Formalization Technique: N Versions Towards One Good Version, in W. Kahl, D. L. Parnas, G. Schmidt (eds.), Relational Methods in Software, Elsevier 2001, 19- 37.
• 20: {20} L. Lamport, How to Write a Long Formula, SRC Research Report 119, DEC System Research Centre, Palo Alto, CA, 1993.
• 21: Mark Lawford , Jeff McDougall , Peter Froebel , Greg Moum, Practical Application of Functional and Relational Methods for the Specification and Verification of Safety Critical Software, Proceedings of the 8th International Conference on Algebraic Methodology and Software Technology, p.73-88, May 20-27, 2000
• 22: Nancy G. Leveson , Mats Per Erik Heimdahl , Holly Hildreth , Jon D. Reese, Requirements Specification for Process-Control Systems, IEEE Transactions on Software Engineering, v.20 n.9, p.684-707, September 1994 [doi>10.1109/32.317428 ]
• 23: {23} J. McDougall, E. Jankowski, Procedure for the Specification of Software Requirements for Safety Critical Systems, Report CE-1001-PROC, Computer Centre of Excellence, 1995.
• 24: {24} D. L. Parnas, G. J. K. Asmis, J. D. Kendall, Reviewable Development of Safety Critical Software, International Conference on Control and Instrumentation in Nuclear Installations, Glasgow, U.K., 1990, No. 4.3.
• 25: {25} D. L. Parnas, G. L. K. Asmis, J. Madey, Assessment of Safety-Critical Software in Nuclear Power Plants, Nuclear Safety, 32,2 (1991), 189-198.
• 26: David Lorge Parnas, A generalized control structure and its formal definition, Communications of the ACM, v.26 n.8, p.572-581, Aug. 1983 [doi>10.1145/358161.358168]
• 27: {27} D. L. Parnas, Tabular Representation of Relations, CRL Report 260, Telecommunications Research Institute of Ontario (TRIO), McMaster University, Hamilton, Ontario, Canada, 1992.
• 28: David Lorge Parnas , Jan Madey, Functional documents for computer systems, Science of Computer Programming, v.25 n.1, p.41-61, Oct. 1995 [doi>10.1016/0167-6423(95)96871-J ]
• 29: David Lorge Parnas , Jan Madey , Michal Iglewski, Precise Documentation of Well-Structured Programs, IEEE Transactions on Software Engineering, v.20 n.12, p.948-976, December 1994 [doi>10.1109/32.368133 ]
• 30: {30} B. Plenderleith, Care and Feeding of Living Software Documentation, Lecture at Workshop on Tools for Tabular Notation, McMaster University, Hamilton, Ontario, Canada 1996.
• 31: Gunther Schmidt , Thomas Ströhlein, Relations and graphs: discrete mathematics for computer scientists, Springer-Verlag, London, 1993
• 32: {32} A. J. van Schouwen, The A-7 Requirements Model: Re-examination for Real-Time Systems and an Application to Monitoring Systems, Technical Report 90-276, Queen's University, CIS, TRIO, Kingston, Ontario, Canada, 1990.
• 33: {33} SERG - Software Engineering Group, Table Tool System Developer's Guide, CRL Report 339, TRIO, McMaster University, Hamilton, Ontario, Canada 1997.
• 34: {34} A. Wassyng, GARD Research Consulting Inc., Software Requirements for AECB Project 2.314.1, 23141-DOC-4, Revision 2, 1995.
• 35: {35} A. Wassyng, M. Lawford, Lessons Learned from a Successful Implementation of Formal Methods in an Industrial Project, Proceedings of Formal Methods '03, Springer, to appear.
• 36: {36} Y. Yang, Modelling Concurrency by Tabular Expressions, M. Sc. Thesis, Dept. of Computing and Software, McMaster University, Hamilton, Ontario, Canada 2002.
• 37: {37} J. Zucker, Transformations of Normal and Inverted Function Tables, Formal Aspects of Programming , 8 (1996), 679-705.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Documentation

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages

General Terms:
Documentation, Languages, Theory