article

Free access

On visual formalisms

Author:

David HarelAuthors Info & Claims

Communications of the ACM, Volume 31, Issue 5

Pages 514 - 530

https://doi.org/10.1145/42411.42414

Published: 01 May 1988 Publication History

PDF eReader

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.

References

[1]

Berge, C. Graphs and Hypergraphs. North-Holland, Amsterdam, 1973.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[3]

Biggs, N.L., Lloyd, E.K., and Wilson, R.J. Graph Theory: 1736-1936. Clarendon Press, Oxford, 1976.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[6]

Charniak, E. and McDermott, D. Introduction to Artificial Intelligence. Addison-Wesley, Reading, Mass., 1985.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[8]

Conklin, J. Hypertext: An introduction and survey. IEEE Computer 20, 9 (Sept. 1987), 17-41.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[21]

Hard, D. Statecharts: A visual formalism for complex systems. Sci. Comput. Program. 8, 3 (June 1987), 231-274.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[26]

Hoare, C.A.R. Communicating sequential processes. Commun. ACM 21, 8 (Aug. 1978), 666-677.

Digital Library

Google Scholar

[27]

Hopcrofi, }.E., and Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[33]

Martin. J., and McClure, C. Diagramming Techniques for Analysts and Programmers. Prentice-Hall, Englewood Cliffs, N.J., 1985.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[35]

MiZlner, R. A Calculus of Communicating Systems. Lecture Notes in Computer Science, voI. 92. Springer-Verlag, New York. 1980.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[38]

Owicki, S., and Lamport, L. Proving liveness properties of concurrent programs. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 455-495.

Digital Library

Google Scholar

[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.

Crossref

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.

Digital Library

Google Scholar

[42]

Schiffner, G., and Schuermann, P. Multiple views and abstractions with an extended-entity-relationship model. Comput. Lang. 4, 3/4 (1979), 139-154.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[45]

Touretzky, D.S. The Mathematics of Inheritance Systems. Pitman, London, and Morgan Kaufmann, Los Altos, Calif. 1986.

Digital Library

Google Scholar

[46]

Tufie, E.R. The Visual Display of Quantitative Information. Graphics Press, Cheshire, Conn., 1983.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

Cited By

View all

Polančič GKous K(2024)High-Level Process Modeling—An Experimental Investigation of the Cognitive Effectiveness of Process Landscape DiagramsMathematics10.3390/math1209137612:9(1376)Online publication date: 30-Apr-2024
https://doi.org/10.3390/math12091376
Nag SBasu NBose PBandyopadhyay S(2024)A Novel Grammar-Based Approach for Patients’ Symptom and Disease Diagnosis Information Dissemination to Maintain Confidentiality and Information IntegrityBioengineering10.3390/bioengineering1112126511:12(1265)Online publication date: 13-Dec-2024
https://doi.org/10.3390/bioengineering11121265
Giacomo EDidimo WLiotta GMontecchiani FTappini A(2024)Comparative Study and Evaluation of Hybrid Visualizations of GraphsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.323338930:7(3503-3515)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1109/TVCG.2022.3233389
Show More Cited By

Index Terms

On visual formalisms

Recommendations

Towards extensible graphical formalisms
IWSSD '93: Proceedings of the 7th international workshop on Software specification and design

We 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 Systems

Rigorous 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

Reviewer: 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 31, Issue 5

May 1988

114 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/42411

Editor:
Peter J. Denning
NASA Ames Research Center, Moffitt Field, CA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1988

Published in CACM Volume 31, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

924
Total Citations
View Citations
3,702
Total Downloads

Downloads (Last 12 months)363
Downloads (Last 6 weeks)56

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Polančič GKous K(2024)High-Level Process Modeling—An Experimental Investigation of the Cognitive Effectiveness of Process Landscape DiagramsMathematics10.3390/math1209137612:9(1376)Online publication date: 30-Apr-2024
Nag SBasu NBose PBandyopadhyay S(2024)A Novel Grammar-Based Approach for Patients’ Symptom and Disease Diagnosis Information Dissemination to Maintain Confidentiality and Information IntegrityBioengineering10.3390/bioengineering1112126511:12(1265)Online publication date: 13-Dec-2024
Giacomo EDidimo WLiotta GMontecchiani FTappini A(2024)Comparative Study and Evaluation of Hybrid Visualizations of GraphsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.323338930:7(3503-3515)Online publication date: 1-Jul-2024
Gatterbauer W(2024)A Comprehensive Tutorial on Over 100 Years of Diagrammatic Representations of Logical Statements and Relational Queries2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00407(5387-5392)Online publication date: 13-May-2024
Dyrda DBelloni C(2024)Space Foundation System: An Approach to Spatial Problems in Games2024 IEEE Conference on Games (CoG)10.1109/CoG60054.2024.10645661(1-8)Online publication date: 5-Aug-2024
Myers B(2024)Pick, Click, Flick!undefinedOnline publication date: 14-Mar-2024
Müller-Sielaff JBeladi SVrede SMeuschke MLucas PPijnenborg JOeltze-Jafra S(2023)Visual Assistance in Development and Validation of Bayesian Networks for Clinical Decision SupportIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.316607129:8(3602-3616)Online publication date: 1-Aug-2023
Ferro MSilva EFidalgo R(2023)AStarData & Knowledge Engineering10.1016/j.datak.2023.102174145:COnline publication date: 1-May-2023
Exelmans JPietron JRaschke AVangheluwe HTichy M(2023)A new versioning approach for collaboration in blended modelingJournal of Computer Languages10.1016/j.cola.2023.10122176(101221)Online publication date: Aug-2023
Hu CHu C(2023)Software Modeling Languages and ToolsAn Introduction to Software Design10.1007/978-3-031-28311-6_6(137-186)Online publication date: 25-Jul-2023
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Towards extensible graphical formalisms

Customizable notations for kernel formalisms

On Teaching Visual Formalisms

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations