Nothing Special   »   [go: up one dir, main page]

skip to main content
10.5555/1806222.1806227guidebooksArticle/Chapter ViewAbstractPublication PagesBookacm-pubtype
chapter

On mathematical laws of software

Published: 01 January 2008 Publication History

Abstract

Recent studies on the laws and mathematical constraints of softwarehave resulted in fundamental discoveries in computing and software engineeringtoward exploring the nature of software. It was recognized that software isnot constrained by any physical laws discovered in the natural world. However,software obeys the laws of mathematics, cognitive informatics, system science,and formal linguistics. This paper investigates into the mathematical laws ofsoftware and computing behaviors. A generic mathematical model of programsis created that reveals the nature of software as abstract processes and itsuniqueness beyond other mathematical entities such as sets, relations, functions,and abstract concepts. A comprehensive set of mathematical laws for softwareand its behaviors is established based on the generic mathematical model ofprograms and the fundamental computing behaviors elicited in Real-Time ProcessAlgebra (RTPA). A set of 95 algebraic laws of software behaviors is systematicallyderived, which encompasses the laws of meta-processes, processrelations, and system compositions. The comprehensive set of mathematicallaws of software lays a theoretical foundation for analyzing and modeling softwarebehaviors and software system architectures, as well as for guiding rigorouspractice in programming. They are also widely applicable for the rigorousmodeling and manipulation of human cognitive processes and computational intelligentbehaviors.

References

[1]
Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, NewYork. Addison-Wesley Publication Co, Reading (1985).
[2]
Baeten, J.C.M., Bergstra, J.A.: Real Time Process Algebra. Formal Aspects of Computing3, 142-188 (1991).
[3]
Boole, G.: The Laws of Thought, Prometheus Books, NY (1854) (reprint, 2003).
[4]
Boucher, A., Gerth, R.: A Timed Model for Extended Communicating Sequential Processes.In: Ottmann, T. (ed.) ICALP 1987. LNCS, vol. 267. Springer, Heidelberg (1987).
[5]
Cardelli, L., Wegner, P.: On Understanding Types, Data Abstraction and Polymorphism.ACM Computing Surveys 17(4), 471-522 (1985).
[6]
Chomsky, N.: Three Models for the Description of Languages. I.R.E. Transactions on InformationTheory 2(3), 113-124 (1956).
[7]
Chomsky, N.: On Certain Formal Properties of Grammars. Information and Control 2,137-167 (1959).
[8]
Dierks, H.: A Process Algebra for Real-Time Programs. In: Maibaum, T.S.E. (ed.) ETAPS2000 and FASE 2000. LNCS, vol. 1783, pp. 66-76. Springer, Heidelberg (2000).
[9]
Dijkstra, E.W.: A Discipline of Programming. Prentice Hall, Englewood Cliffs (1976).
[10]
Fecher, H.: A Real-Time Process Algebra with Open Intervals and Maximal Progress.Nordic Journal of Computing 8(3), 346-360 (2001).
[11]
Goguen, J.A., Thatcher, J.W., Wagner, E.G., Wright, J.B.: Initial Algebra Semantics andContinuous Algebras. Journal of the ACM 24(1), 59-68 (1977).
[12]
Higman, B.: A Comparative Study of Programming Languages, 2nd edn. MacDonald(1977).
[13]
Hoare, C.A.R.: An Axiomatic Basis for Computer Programming. Communications of theACM 12(10), 576-580 (1969).
[14]
Hoare, C.A.R.: Communicating Sequential Processes. Communications of the ACM 21(8),666-677 (1978).
[15]
Hoare, C.A.R.: Communicating Sequential Processes. Prentice-Hall International, London(1985).
[16]
Hoare, C.A.R., Hayes, I.J., He, J., Morgan, C.C., Roscoe, A.W., Sanders, J.W., Sorensen,I.H., Spivey, J.M., Sufrin, B.A.: Laws of Programming. Communications of heACM 30(8), 672-686 (1987).
[17]
Klusener, A.S.: Abstraction in Real Time Process Algebra. In: Huizing, C., de Bakker,J.W., Rozenberg, G., de Roever, W.-P. (eds.) REX 1991. LNCS, vol. 600, pp. 325-352.Springer, Heidelberg (1992).
[18]
Louden, K.C.: Programming Languages: Principles and Practice. PWS-Kent PublishingCo., Boston (1993).
[19]
Martin-Lof, P.: An Intuitionistic Theory of Types: Predicative Part. In: Rose, H., Shepherdson,J.C. (eds.) Logic Colloquium 1973. North-Holland, Amsterdam (1975).
[20]
Milner, R.: A Calculus of Communicating Systems. LNCS, vol. 92. Springer, Heidelberg(1980).
[21]
McDermid, J.A. (ed.): Software Engineer's Reference Book. Butterworth-Heinemann Ltd.,Oxford (1991).
[22]
Mitchell, J.C.: Type systems for programming languages. In: van Leeuwen, J. (ed.) Handbookof Theoretical Computer Science, pp. 365-458. North Holland, Amsterdam (1990).
[23]
Nicollin, X., Sifakis, J.: An Overview and Synthesis on Timed Process Algebras. In: Larsen,K.G., Skou, A. (eds.) CAV 1991. LNCS, vol. 575, pp. 376-398. Springer, Heidelberg(1992).
[24]
Parnas, D.L., Clements, P.C.: A Rational Design Process: How and Why to Fake It. IEEETrans. on Software Engineering 12(2), 251-257 (1986).
[25]
Reed, G.M., Roscoe, A.W.: A Timed model for Communicating Sequential Processes. In:Kott, L. (ed.) ICALP 1986. LNCS, vol. 226. Springer, Heidelberg (1986).
[26]
Scott, D.S., Strachey, C.: Towards a Mathematical Semantics for Computer Languages,Programming Research Group Technical Report PRG-1-6, Oxford University (1971).
[27]
Schneider, S.A.: An Operational Semantics for Timed CSP, Programming Research GroupTechnical Report TR-1-91, Oxford University (1991).
[28]
Stubbs, D.F., Webre, N.W.: Data Structures with Abstract Data Types and Pascal.Brooks/Cole Publishing Co., Monterey (1985).
[29]
Tan, X., Wang, Y., Ngolah, C.F.: A Novel Type Checker for Software System Specificationsin RTPA. In: Proc. 17th Canadian Conference on Electrical and Computer Engineering(CCECE 2004), Niagara Falls, ON, Canada, pp. 1549-1552. IEEE CS Press, LosAlamitos (2004).
[30]
Tan, X., Wang, Y., Ngolah, C.F.: Design and Implementation of an Automatic RTPACode Generator. In: Proc. 19th Canadian Conference on Electrical and Computer Engineering(CCECE 2006), Ottawa, ON, Canada, pp. 1605-1608 (May 2006).
[31]
Tarski, A.: The Semantic Conception of Truth. Philosophic Phenomenological Research 4,13-47 (1944).
[32]
Wang, Y.: The Real-Time Process Algebra (RTPA). Annals of Software Engineering: AInternational Journal 14, 235-274 (2002).
[33]
Wang, Y.: On Cognitive Informatics (Keynote Speech). In: Proc. 1st IEEE InternationalConference on Cognitive Informatics (ICCI 2002), Calgary, Canada, pp. 34-42. IEEE CSPress, Los Alamitos (2002).
[34]
Wang, Y.: On Cognitive Informatics. Brain and Mind: A Transdisciplinary Journal of Neuroscienceand Neurophilosophy, USA 4(3), 151-167 (2003).
[35]
Wang, Y.: Using Process Algebra to Describe Human and Software System Behaviors.Brain and Mind 4(2), 199-213 (2003).
[36]
Wang, Y.: On the Informatics Laws and Deductive Semantics of Software. IEEE Transactionson Systems, Man, and Cybernetics (C) 36(2), 161-171 (2006).
[37]
Wang, Y.: Keynote: Cognitive Informatics - Towards the Future Generation Computersthat Think and Feel. In: Proc. 5th IEEE International Conference on Cognitive Informatics(ICCI 2006), Beijing, China, pp. 3-7. IEEE CS Press, Los Alamitos (2006).
[38]
Wang, Y.: Cognitive Informatics and Contemporary Mathematics for Knowledge Representationand Manipulation (Invited Plenary Talk). In: Wang, G.-Y., Peters, J.F., Skowron,A., Yao, Y. (eds.) RSKT 2006. LNCS (LNAI), vol. 4062, pp. 69-78. Springer, Heidelberg(2006).
[39]
Wang, Y.: Software Engineering Foundations: A Software Science Perspective. CRC Seriesin Software Engineering, vol. II. Auerbach Publications, NY, USA (2007).
[40]
Wang, Y.: The Theoretical Framework of Cognitive Informatics. International Journal ofCognitive Informatics and Natural Intelligence 1(1), 1-27 (2007).
[41]
Wang, Y.: Keynote: On Theoretical Foundations of Software Engineering and DenotationalMathematics. In: Proc. 5th Asian Workshop on Foundations of Software, Xiamen,China, pp. 99-102 (2007).
[42]
Wang, Y.: On the Big-R Notation for Describing Iterative and Recursive Behaviors. InternationalJournal of Cognitive Informatics and Natural Intelligence 2(1), 17-28 (2008).
[43]
Wang, Y.: Deductive Semantics of RTPA. International Journal of Cognitive Informaticsand Natural Intelligence 2(2), 95-121 (2008).
[44]
Wang, Y.: On Concept Algebra: A Denotational Mathematical Structure for Knowledgeand Software Modeling. International Journal of Cognitive Informatics and Natural Intelligence2(2), 1-19 (2008).
[45]
Wang, Y.: On System Algebra: A Denotational Mathematical Structure for Abstract Systemmodeling. International Journal of Cognitive Informatics and Natural Intelligence 2(2),20-42 (2008).
[46]
Wang, Y.: RTPA: A Denotational Mathematics for Manipulating Intelligent and ComputationalBehaviors. International Journal of Cognitive Informatics and Natural Intelligence2(2), 44-62 (2008).
[47]
Wang, Y.: On Laws of Work Organization in Human Cooperation. International Journal ofCognitive Informatics and Natural Intelligence 1(2), 1-15 (2008).
[48]
Wang, Y.: On Contemporary Denotational Mathematics for Computational Intelligence.In: Gavrilova, M.L., et al. (eds.) Transactions on Computational Science, II. LNCS,vol. 5150, pp. 6-29. Springer, Heidelberg (2008).
[49]
Wang, Y., Noglah, C.F.: Formal Specification of a Real-Time Lift Dispatching System. In:Proc. 2002 IEEE Canadian Conference on Electrical and Computer Engineering (CCECE2002), Winnipeg, Manitoba, Canada, pp. 669-674 (May 2002).
[50]
Wang, Y., Noglah, C.F.: Formal Description of Real-Time Operating Systems usingRTPA. In: Proc. 2003 Canadian Conference on Electrical and Computer Engineering(CCECE 2003), Montreal, Canada, pp. 1247-1250. IEEE CS Press, Los Alamitos (2003).
[51]
Wang, Y., Zhang, Y.: Formal Description of an ATM System by RTPA. In: Proc. 16thCanadian Conference on Electrical and Computer Engineering (CCECE 2003), Montreal,Canada, pp. 1255-1258. IEEE CS Press, Los Alamitos (2003).
[52]
Wilson, L.B., Clark, R.G.: Comparative Programming Language. Addison-Wesley PublishingCo, Reading (1988).
[53]
Woodcock, J., Davies, J.: Using Z: Specification, Refinement, and Proof. Prentice Hall International,London (1996).

Cited By

View all
  • (2012)Seamless Implementation of a Telephone Switching System Based on Formal Specifications in RTPAInternational Journal of Software Science and Computational Intelligence10.4018/jssci.20120401054:2(81-104)Online publication date: 1-Apr-2012
  • (2012)The Formal Design Models of Digraph Architectures and BehaviorsInternational Journal of Software Science and Computational Intelligence10.4018/jssci.20120101054:1(100-129)Online publication date: 1-Jan-2012
  • (2011)The Formal Design Models of Tree Architectures and BehaviorsInternational Journal of Software Science and Computational Intelligence10.4018/jssci.20111001063:4(84-108)Online publication date: 1-Oct-2011
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide books
Transactions on computational science II
January 2008
245 pages
ISBN:354087562X
  • Editors:
  • Marina L. Gavrilova,
  • C. J. Kenneth Tan,
  • Yingxu Wang,
  • Yiyu Yao,
  • Guoyin Wang

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 January 2008

Author Tags

  1. RTPA
  2. algebraic laws
  3. analysis
  4. computational intelligence
  5. denotational mathematics
  6. generic model of software
  7. laws of meta-processes
  8. laws of process compositions
  9. laws of process relations
  10. mathematical models
  11. modeling
  12. process models
  13. programs
  14. software
  15. software engineering
  16. software science

Qualifiers

  • Chapter

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2012)Seamless Implementation of a Telephone Switching System Based on Formal Specifications in RTPAInternational Journal of Software Science and Computational Intelligence10.4018/jssci.20120401054:2(81-104)Online publication date: 1-Apr-2012
  • (2012)The Formal Design Models of Digraph Architectures and BehaviorsInternational Journal of Software Science and Computational Intelligence10.4018/jssci.20120101054:1(100-129)Online publication date: 1-Jan-2012
  • (2011)The Formal Design Models of Tree Architectures and BehaviorsInternational Journal of Software Science and Computational Intelligence10.4018/jssci.20111001063:4(84-108)Online publication date: 1-Oct-2011
  • (2011)The Formal Design Model of Doubly-Linked-Circular Lists DLC-ListsInternational Journal of Software Science and Computational Intelligence10.4018/jssci.20110401063:2(83-102)Online publication date: 1-Apr-2011
  • (2011)The Formal Design Models of a Universal Array UA and its ImplementationInternational Journal of Software Science and Computational Intelligence10.4018/IJSSCI.20110701063:3(69-89)Online publication date: 1-Jul-2011
  • (2011)Empirical Studies on the Functional Complexity of Software in Large-Scale Software SystemsInternational Journal of Software Science and Computational Intelligence10.4018/IJSSCI.20110701033:3(23-42)Online publication date: 1-Jul-2011
  • (2010)The Formal Design Model of an Automatic Teller Machine ATMInternational Journal of Software Science and Computational Intelligence10.4018/jssci.20101019072:1(102-131)Online publication date: 1-Jan-2010
  • (2010)The Formal Design Models of a Set of Abstract Data Types ADTsInternational Journal of Software Science and Computational Intelligence10.4018/jssci.20101001062:4(72-100)Online publication date: 1-Oct-2010
  • (2010)The Formal Design Model of a Real-Time Operating System RTOS+International Journal of Software Science and Computational Intelligence10.4018/jssci.20100701062:3(79-105)Online publication date: 1-Jul-2010
  • (2010)The Formal Design Model of a Real-Time Operating System RTOS+International Journal of Software Science and Computational Intelligence10.4018/jssci.20100401062:2(105-122)Online publication date: 1-Apr-2010
  • Show More Cited By

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media