David Harel
Abstract
The higraph, a general kind of diagramming object, forms a visual formalism of topological nature. Higraphs are suited for a wide array of applications to databases, knowledge representation, and, most notably, the behavioral specification of complex concurrent systems using the higraph-based language of statecharts.
- 1 Berge, C. Graphs and Hypergraphs. North-Holland, Amsterdam, 1973. Google Scholar
Digital Library
- 2 Berry. G., and Cosserat, I. The ESTEREL synchronous programming language and its mathematical semantics. In Seminar on Concurrency, S. Brookes and G. Winskel, Eds. Lecture Notes in Computer Science, vol. 197. Springer-Verlag, New York, 1985, pp. 389-448. Google ScholarDigital Library
- 3 Biggs, N.L., Lloyd, E.K., and Wilson, R.J. Graph Theory: 1736-1936. Clarendon Press, Oxford, 1976. Google ScholarDigital Library
- 4 B rachman, R.J. On the epistemological status of semaniic networks. I n Associative Networks: Representation and Use of Knowledge by Computer, N.V. Findler, Ed. Academic Press, New York, 1979, pp. 3-50.Google Scholar
- 5 Cardelli, L.A. Semantics of multiple inheritance in semantics of data types. Kahn, G. et al. Lecture Notes in Computer Science. vol. 173, Springer-Verlag, 1984, pp. 51-67. Google ScholarDigital Library
- 6 Charniak, E. and McDermott, D. Introduction to Artificial Intelligence. Addison-Wesley, Reading, Mass., 1985. Google ScholarDigital Library
- 7 Chen, P.P.-S. The entity-relationship model--toward a unified view of data. ACM Trans. Database Syst. 1, 1 (Mar. 1976). 9-36. Google ScholarDigital Library
- 8 Conklin, J. Hypertext: An introduction and survey. IEEE Computer 20, 9 (Sept. 1987), 17-41. Google ScholarDigital Library
- 9 Davis, P.J., Anderson, J.A. Nonanalytic aspects on mathematics and their implication on research and education. SIAM Review 21, 1 (Jan. 1979), 112-127.Google ScholarCross Ref
- 10 dos Santos, C.S., Neuhold, E.J. and Furtado. A.L. A data type approach to the entity-relationship model. In Entity-Relationship Approach to Systems Analysis and Design, P.P. Chen, Ed. North-Holland, Amsterdam, 1980, pp. 103-119. Google ScholarDigital Library
- 11 Dugundji, J. Topology. Allyn and Bacon, Boston, Mass., 1966.Google Scholar
- 12 Euler, L. Solutio problematis ad geometriam situs pertinentis. Comm. Acad. Sci. Imp. Petropol. 8 (1736), 128-140.Google Scholar
- 13 Euler, L. Lettres il une Princesse d'Allemagne. Vol. 2. 1772 (letters 102-108).Google Scholar
- 14 Fagin, R. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30, 3 (July 1983), 514-550. Google ScholarDigital Library
- 15 Fagin, R., Mendelzon, A., and Ullman, }. A simplified universal relation assumption and its properties. ACM Trans. Database Syst. 7, 3 (Sept. 1982), 343-360. Google ScholarDigital Library
- 16 al-Fedaghi, S.S. An entity-relationship approach to modelling petroleum engineering database. In Entity-Relationship Approach to Software Engineering, C.G. Davis et al., Eds. Elsevier Science Publishers, Amsterdam, 1983, pp. 761-779.Google Scholar
- 17 Findler, N.V., Ed. Associative Networks: Representation and Use of Knowledge by Computer. Academic Press, New York, 1979. Google ScholarDigital Library
- 18 Fitter, M., and Green, T.R.G. When do diagrams make good computer languages? Int. J. Man-Mach. Stud. 11, 2 (March 1979), 235-261.Google Scholar
- 19 Gardner, M. Logic Machines and Diagrams. 2nd ed. University of Chicago Press, Chicago, I11., 1982.Google Scholar
- 20 Green, T.R. Pictures of programs and other processes, or how to do things with lines. Behav. Inf. Technol. 1, 1 (1982), 3-36.Google ScholarCross Ref
- 21 Hard, D. Statecharts: A visual formalism for complex systems. Sci. Comput. Program. 8, 3 (June 1987), 231-274. Google ScholarDigital Library
- 22 Harel, D., and Pnueli, A. On the development of reactive systems. In Logics and Models of Concurrent Systems, NATO, ASI Series, vol. 13, K.R. Apt, Ed. Springer-Verlag, New York, 1985, pp. 477-498. Google ScholarCross Ref
- 23 Hard, D., Pnueli, A., Schn,idt, J.P., and Sherman, R. On the formal semantics of statecharts. In Proceedings of the 2nd IEEE Symposium on Logic in Computer Science (Ithaca, N.Y., June 22-24}. IEEE Press, New York, 1987, pp. 54-64.Google Scholar
- 24 Harel, D., Lachover, H., Naamad, A., Pnueli, A., Politi, M., Sherman, R., and Shtul-Trauring, A. STATEMENT: A working environment for the development of complex reactive systems. In Proceedings of the Tenth IEEE International Conference on Software Engineering (Singapore, April 13-15}. IEEE Press. New York, 1988. Google ScholarDigital Library
- 25 Hendrix, G.G. Expanding the utility of semantic networks through partitioning. In Proceedings of the 4th International Conference on Artificial Intelligence (Tbilisi, Georgia, USSR, Sept. 3-8). International Joint Council on Artificial Intelligence, Cambridge, Mass., 1975, pp. 115-121.Google ScholarCross Ref
- 26 Hoare, C.A.R. Communicating sequential processes. Commun. ACM 21, 8 (Aug. 1978), 666-677. Google ScholarDigital Library
- 27 Hopcrofi, }.E., and Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979. Google ScholarDigital Library
- 28 i-Logic. The languages of STATEMATE. Tech. Rep., i-Logix, Burlington, Mass., 1987.Google Scholar
- 29 Kahana, C.A. Statecharts with overlapping states. M.S. thesis, Dept. of Mathematics and Computer Science, Bar-Ilan University, Ramat Gan, Israel, 1986 (in Hebrew).Google Scholar
- 30 Lefschetz, S. Introduction to Topology. Princeton University Press, Princeton, N.J., 1949.Google Scholar
- 31 Mater, D., and Ullman, J.D. Connections in acyclic hypergraphs. In Proceedings of the ACM Symposium on Database Systems (Los Angeles. Calif., March 29-31). ACM. New York, 1982, pp. 34-39. Google ScholarDigital Library
- 32 Manna, Z., and Pnueli, A. Specification and verification of concurrent programs by Y-automata. In Proceedings of the 14th ACM Symposium on Principles of Programming Languages (Munich). ACM, New York, 1987, pp. 1-12. Google ScholarDigital Library
- 33 Martin. J., and McClure, C. Diagramming Techniques for Analysts and Programmers. Prentice-Hall, Englewood Cliffs, N.J., 1985. Google ScholarDigital Library
- 34 McSkimin, J.R., and Minker. J. A predicate calculus based semantic network for deductive searching. In Associative Networks: Representation and Use of Knowledge by Computer, N.V. Findler, Ed. Academic Press, New York, 1979, pp. 205-238.Google ScholarCross Ref
- 35 MiZlner, R. A Calculus of Communicating Systems. Lecture Notes in Computer Science, voI. 92. Springer-Verlag, New York. 1980. Google ScholarDigital Library
- 36 Nakano, R. Integrity checking in a logic-oriented ER model. In Entity-Relationship Approach to Software Engineering, C.G. Davis et al., Eds. Elsevier Science Publishers, Amsterdam, 1983, pp. 551-564.Google Scholar
- 37 Nilsson, N.J. Principles of Artificiat Intelligence. Tioga, Palo Alto, Calif., 1980. Google ScholarDigital Library
- 38 Owicki, S., and Lamport, L. Proving liveness properties of concurrent programs. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 455-495. Google ScholarDigital Library
- 39 Pnueli, A. Applications of temporal logic to the specification and verification of reactive systems: A survey of current trends. In Current Trends in Concurrency, J. W. de Bakker et al., Eds. Lecture Notes in Computer Science, vol. 224, Springer-Verlag, New York, 1986, pp. 510-584. Google Scholar
- 40 Quillian, M.R. Semantic memory. In Semantic Information Processing, M. Minsky, Ed. MIT Press, Cambridge, Mass., 1968, pp. 227-270.Google Scholar
- 41 Reisig, W. Petri Nets: An Introduction. Springer-Verlag, Berlin, 1985. Google ScholarDigital Library
- 42 Schiffner, G., and Schuermann, P. Multiple views and abstractions with an extended-entity-relationship model. Comput. Lang. 4, 3/4 (1979), 139-154.Google ScholarDigital Library
- 43 Schmid, C.F. Statistical Graphics: Design Principles and Practices. Wiley, New York, 1983.Google Scholar
- 44 Shapiro, S.C. A net structure for semantic information storage, deduction, and retrieval. In Proceedings of the 2nd International Joint Conference on Artificial Intelligence. 1971, pp. 512-523.Google ScholarDigital Library
- 45 Touretzky, D.S. The Mathematics of Inheritance Systems. Pitman, London, and Morgan Kaufmann, Los Altos, Calif. 1986. Google ScholarDigital Library
- 46 Tufie, E.R. The Visual Display of Quantitative Information. Graphics Press, Cheshire, Conn., 1983. Google ScholarDigital Library
- 47 Tygar, J.D. and Wing. J.M. Visual specification of security constraints. In The IEEE Workshop on Visual Languages (Link6ping, Sweden, Aug. 19-21). IEEE Press, New York, 1987.Google Scholar
- 48 Venn, J. On the diagrammatic and mechanical representation of propositions and reasonings. Phil. Mag. (1880), 123.Google Scholar
- 49 Venn, J. Symbolic Logic. 2nd ed. London, 1894. (Reprinted by Chelsea, Bronx, N.Y., 1971.}Google Scholar
- 50 Woods, W.A. What's in a link? Foundations for semantic networks. In Representation and Understanding, D.G. Bobrow and A.M. Collins, Eds. Academic Press, New York, 1975, pp. 35-82.Google Scholar
- 51 Zave, P. A distributed alternative, to finite-state-machine specifications. ACM Trans. Program. Lang. Syst. 7, 1 (Jan. 1985), 10-36. Google ScholarDigital Library
Index Terms
- On visual formalisms
Recommendations
Towards extensible graphical formalisms
IWSSD '93: Proceedings of the 7th international workshop on Software specification and designWe discuss how to tailor a graphical notation on top of a kernel formal (graphical) specification language. The goal is to allow an environment supporting formal specifications written in a kernel formal notation to be extended to support additional, ...
Customizable notations for kernel formalisms
ICECCS '95: Proceedings of the 1st International Conference on Engineering of Complex Computer SystemsRigorous formal methods and intuitive graphical notations can greatly enhance the development of complex computer systems. Formal methods guarantee non-ambiguity and support powerful analysis techniques. Intuitive graphical notations facilitate the ...
On Teaching Visual Formalisms
A graduate course on visual formalisms for reactive systems emphasized using such languages for not only specification and requirements but also (and predominantly) actual execution. The course presented two programming approaches: an intra-object ...
Reviews
Ioan I. Sofroniciu
This paper describes higraphs, which are “a general kind of diagramming object,” according to the author. Higraphs, a notion introduced by the author, are tools for diagramming objects; they were conceived as an extension and a combination of Euler's two topo-visual formalisms—graphs and Euler circles. A formal definition of higraphs is presented in an appendix. The power of this formalism is illustrated by brief discussions on the higraph-based versions of more graphical languages such as entity-relationship diagrams, semantic and associative networks, and dataflow diagrams. A section of this paper is devoted to a less obvious application, called statecharts. They are higraph-based extensions of finite state machines and their standard state-transition diagrams, and they represent a new attempt at solving the problem of the behavioral specification of complex concurrent systems. This paper is clearly written and is an original contribution to the development of visual formalisms. It opens new doors for research in the conceptual improvement of the notion of higraphs, the applications of higraphs to databases, and knowledge representation.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments