Petri-net-based hypertext: document structure with browsing semantics

ABSTRACT

We present a formal definition of the Trellis model of hypertext and describe an authoring and browsing prototype called &agr;Trellis that is based on the model. The Trellis model not only represents the relationships that tie individual pieces of information together into a document (i.e., the adjacencies), but specifies the browsing semantics to be associated with the hypertext as well (i.e., the manner in which the information is to be visited and presented). The model is based on Petri nets, and is a generalization of existing directed graph-based forms of hypertext. The Petri net basis permits more powerful specification of what is to be displayed when a hypertext is browsed and permits application of previously developed Petri net analysis techniques to verify properties of the hypertext. A number of useful hypertext constructs, easily described in the Trellis model, are presented. These include the synchronization of simultaneous traversals of separate paths through a hypertext, the incorporation of access controls into a hypertext (i.e., specifying nodes that can be proven to be accessible only to certain classes of browsers), and construction of multiple specialized (tailored) versions from a single hypertext.

REFERENCES

• 1: Robert M. Akscyn , Donald L. McCracken , Elise A. Yoder, KMS: a distributed hypermedia system for managing knowledge in organizations, Communications of the ACM, v.31 n.7, p.820-835, July 1988 [doi>10.1145/48511.48513]
• 2: P. J. Brown, Hypertext: the way forward, Proceedings of the International Conference on Electronic Publishing on Document manipulation and typography, p.183-191, May 1988, Nice, France
• 3: BUSH, V. As we may think. The Atlantic 176, 1 (July 1945), 101-108.
• 4: Brad Campbell , Joseph,M. Goodman, HAM: a general purpose hypertext abstract machine, Communications of the ACM, v.31 n.7, p.856-861, July 1988 [doi>10.1145/48511.48515]
• 5: CARMODY, S., GROSS, W., NELSON, T. E., RICE, D., AND VAN DAM, A. A hypertext editing system for the/360. Tech. Rep., Center for Computer and Information Sciences, Brown Univ., Providence, R.I., Mar. 1969. Also contained in Pertinent Concepts in Computer Graphics, M. Faiman and J. Nievergelt, Eds., University of Illinois, Urbana, Mar. 1969, pp. 291-330.
• 6: S. Christodoulakis , F. Ho , M. Theodoridou, The multimedia object presentation manager of MINOS: a symmetric approach, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.295-310, May 28-30, 1986, Washington, D.C., United States
• 7: S. Christodoulakis , M. Theodoridou , F. Ho , M. Papa , A. Pathria, Multimedia document presentation, information extraction, and document formation in MINOS: a model and a system, ACM Transactions on Information Systems (TOIS), v.4 n.4, p.345-383, Oct. 1986 [doi>10.1145/9760.9764]
• 8: Jeff Conklin, Hypertext: an introduction and survey, Computer, v.20 n.9, p.17-41, Sept. 1987 [doi>10.1109/MC.1987.1663693]
• 9: James E. Coolahan, Jr. , Nick Roussopoulos, A Timed Petri Net Methodolgoy for Specifying Real-Time System Timing Requirements, International Workshop on Timed Petri Nets, p.24-31, July 01-03, 1985
• 10: DAMI, L., FLUME, E., NIERSTRASZ, 0., AND TSICHRITZlS, D. Temporal scripts for objects. In Active Object Environments (Environnements d'Objets Actifs), D. Tsichritzis, Ed. Centre Universitaire D'Informatique, Univ. de Geneve, June 1988, pp. 144-161.
• 11: Norman Delisle , Mayer Schwartz, Neptune: a hypertext system for CAD applications, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.132-143, May 28-30, 1986, Washington, D.C., United States
• 12: Norman M. Delisle , Mayer D. Schwartz, Contexts—a partitioning concept for hypertext, ACM Transactions on Information Systems (TOIS), v.5 n.2, p.168-186, April 1987 [doi>10.1145/27636.27639]
• 13: ENGELBART, O. C., AND ENGLISH, W.S. A research center for augmenting human intellect. In Proceedings, AFIPS Fall Joint Computer Conference 33 (1968), pp. 395-410.
• 14: ENGELBART, D. C., WATSON, R. W., AND NORTON, J.C. The augmented knowledge workshop. ARC Journal Accession Number 14724, Stanford Research Center, Menlo Park, Calif., Mar. 1973. Paper presented at the National Computer Conference, June 1973.
• 15: S. Feiner , S. Nagy , A. van Dam, An experimental system for creating and presenting interactive graphical documents, ACM Transactions on Graphics (TOG), v.1 n.1, p.59-77, Jan. 1982 [doi>10.1145/357290.357296]
• 16: Pankaj,K. Garg, Abstraction mechanisms in hypertext, Communications of the ACM, v.31 n.7, p.862-870, July 1988 [doi>10.1145/48511.48516]
• 17: Frank,G. Halasz, Reflections on NoteCards: seven issues for the next generation of hypermedia systems, Communications of the ACM, v.31 n.7, p.836-852, July 1988 [doi>10.1145/48511.48514]
• 18: Richard Ilson, Interactive effectivity control: design and applications, Proceedings of the ACM conference on Document processing systems, p.85-91, December 05-08, 1988, Santa Fe, New Mexico, United States [doi>10.1145/62506.62522]
• 19: JENSEN, K. Coloured Petri nets and the invariant method. Theor. Comput. Sci. 14 (1981), 317-336.
• 20: LIFSHITZ, K., AND SHNEIDERMAN, B. Window control strategies for on-line text traversal. Working paper, July 1987.
• 21: Gary Marchionini , Ben Shneiderman, Finding Facts vs. Browsing Knowledge in Hypertext Systems, Computer, v.21 n.1, p.70-80, January 1988 [doi>10.1109/2.222119]
• 22: Michael K. Molloy, A CAD tool for stochastic Petri nets, Proceedings of 1986 ACM Fall joint computer conference, p.1082-1091, November 1986, Dallas, Texas, United States
• 23: James Lyle Peterson, Petri Net Theory and the Modeling of Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 24: Wolfgang Reisig, Petri nets: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: Ben Shneiderman, User interface design for the Hyperties electronic encyclopedia (panel session), Proceeding of the ACM conference on Hypertext, p.189-194, November 1987, Chapel Hill, North Carolina, United States [doi>10.1145/317426.317441]
• 26: STOTTS, P. D., AND FURUTA, R. Alpha: An authoring language for Petri-net-based hypertext, 1989. Hypertext 2, Univ. of York, June 29th and 30th, 1989. To appear.
• 27: P. David Stotts, Jr. , Terrence W. Pratt, Hierarchical Modeling of Software Systems with Timed Petri Nets, International Workshop on Timed Petri Nets, p.32-39, July 01-03, 1985
• 28: Randall H. Trigg, Guided tours and tabletops: tools for communicating in a hypertext environment, ACM Transactions on Information Systems (TOIS), v.6 n.4, p.398-414, Oct. 1988 [doi>10.1145/58566.59299]
• 29: Willem R. van Biljon, Extending Petri nets for specifying man-machine dialogues, International Journal of Man-Machine Studies, v.28 n.4, p.437-455, April 1988 [doi>10.1016/S0020-7373(88)80021-X]
• 30: Andries van Dam, Hypertext '87: keynote address, Communications of the ACM, v.31 n.7, p.887-895, July 1988 [doi>10.1145/48511.48519]
• 31: W. Wulf , E. Cohen , W. Corwin , A. Jones , R. Levin , C. Pierson , F. Pollack, HYDRA: the kernel of a multiprocessor operating system, Communications of the ACM, v.17 n.6, p.337-345, June 1974 [doi>10.1145/355616.364017]
• 32: ZELLWEGER, P. T. Directed paths through collections of multi-media documents. Position paper. In Hypertext '87 (Nov. 1987).
• 33: Polle T. Zellweger, Active paths through multimedia documents, Proceedings of the International Conference on Electronic Publishing on Document manipulation and typography, p.19-34, May 1988, Nice, France
• 34: ZISMAN, M.D. Use of production systems for modeling asynchronous, concurrent processes. In Pattern-Directed inference Systems, D. A. Waterman and F. Hayes-Roth, Eds. Academic Press, Orlando, Fla., 1978, pp. 53-68.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Design, Languages, Theory