Automatic presentation of multimedia documents using relational grammars

ABSTRACT

This paper describes an approach to the automatic presentation of multimedia documents based on parsing and syntax-directed translation using Relational Grammars. This translation is followed by a constraint solving mechanism to create the final layout. Grammatical rules provide the mechanism for mapping from a representation of the content of a presentation to forms that specify the media objects to be realized. These realization forms include sets of spatial and temporal constraints between elements of the presentation. Individual grammars encapsulate the “look and feel” of a presentation and can be used as generators of that style. By making the grammars sensitive to the requirements of the output medium, parsing can introduce flexibility into the information realization process.

REFERENCES

• Aho86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• All83: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• And93: Elizabeth André , Wolfgang Finkler , Winfried Graf , Thomas Rist , Anne Shauder , Wolfgang Walhstein, WIP: the automatic synthesis of multimodal presentations, Intelligent multimedia interfaces, American Association for Artificial Intelligence, Menlo Park, CA, 1993
• Are88: Arens, Y., Miller, L., Shapiro, S. and Sondheimer, N. Automatic Construction of User- Interface Displays, In Proceedings of the American Association of Artificial Intelligence, Vol. 2 (August 21-26, St. Paul, MN). 1988, pp. 808- 813.
• Cyp93: Allen Cypher , Daniel C. Halbert , David Kurlander , Henry Lieberman , David Maulsby , Brad A. Myers , Alan Turransky, Watch what I do: programming by demonstration, MIT Press, Cambridge, MA, 1993
• Fre90: Bjorn N. Freeman-Benson , John Maloney , Alan Borning, An incremental constraint solver, Communications of the ACM, v.33 n.1, p.54-63, Jan. 1990 [doi>10.1145/76372.77531]
• Fei88: S. K. Feiner, A grid-based approach to automating display layout, Proceedings on Graphics interface '88, p.192-197, December 1989, Edmonton, Alberta, Canada
• Fei93: Steven K. Feiner , Kathleen R. McKeown, Automating the generation of coordinated multimedia explanations, Intelligent multimedia interfaces, American Association for Artificial Intelligence, Menlo Park, CA, 1993
• Fol86: Foley, J. and McMath, C. Dynamic Process Visualization, IEEE Computer Graphics and Application 6, 3 (March, 1986), pp. 16-25.
• Fol91: James Foley , Won Chul Kim , Srdjan Kovacevic , Kevin Murray, UIDE—an intelligent user interface design environment, Intelligent user interfaces, ACM Press, New York, NY, 1991 [doi>10.1145/107215.128716]
• Hel91: Helm, R., and Marriott, K. A Declarative Specification and Semantics for Visual Languages, Journal of Visual Languages and Computing, 2 (1991), pp. 311-331.
• Hen93: Henkenius, Merle. Surface Wiring, Popular Mechanics 170, 12 (December, 1993). pp. 63-66.
• Hol84: Hollan, J., Hutchins, E. and Weitzman, L. Steamer: An Interactive Inspectable Simulation- Based Training System, A! Magazine 5, 2 (1984), pp. 15-28.
• Hur78: Hurlburt, A. The Grid, Van Nostrand Reinhold Co., New York, 1978.
• Kar90: P. Karp , S. Feiner, Issues in the automated generation of animated presentations, Proceedings on Graphics interface '90, p.39-48, June 1990, Halifax, Nova Scotia
• Kim93: Won Chul Kim , James D. Foley, Providing high-level control and expert assistance in the user interface presentation design, Proceedings of the SIGCHI conference on Human factors in computing systems, p.430-437, April 24-29, 1993, Amsterdam, The Netherlands [doi>10.1145/169059.169346]
• Knu68: Knuth, D. E. Semantics of context-free languages, Mathematical Systems Theory 2 (1968), pp. 127- 146.
• Koc90: Sandeep Kochhar , Mark Friedell, User control in cooperative computer-aided design, Proceedings of the 3rd annual ACM SIGGRAPH symposium on User interface software and technology, p.143-151, October 03-05, 1990, Snowbird, Utah, United States [doi>10.1145/97924.97941]
• Koc91: Kochhar, S., Marks, J., and Friedell, M. Interaction Paradigms for Human-Computer Cooperation in Graphical-Object Modeling, in Proceedings of Graphics Interface '91 (June, Calgary, Canada). 1991, pp. 180-19 I.
• Mac86: Jock Mackinlay, Automating the design of graphical presentations of relational information, ACM Transactions on Graphics (TOG), v.5 n.2, p.110-141, April 1986 [doi>10.1145/22949.22950]
• Mal91: John Harold Maloney, Using constraints for user interface construction, University of Washington, Seattle, WA, 1992
• Mar90: Marks, J., A syntax and semantics for network diagrams, In Proceedings of the IEEE Workshop on Visual Languages (October 4-6, Skokie, Illinois). 1990, pp. 104-110.
• May93: Mark T. Maybury, Intelligent multimedia interfaces, American Association for Artificial Intelligence, Menlo Park, CA, 1993
• Mit76: Mitchell, W., Steadman, J. and Liggett, R. Synthesis and optimization of small rectangular floor plans, Environment and Planning B: Planning and Design 3, 1 (1976), pp. 37-70.
• NCS93: NCSA. Internet Manuscript from mosaic @ncsa.uiuc.edu, 1993.
• Oxm87: Oxman, R. and Gero, J. Using an expert system for design diagnosis and design synthesis, Expert Systems 4, 1 (February, 1987), pp. 4-15.
• Ros90: Rosenfeld, A. Array, Tree, and Graph Grammars, in Bunke, H., and Sanfeliu, A., Eds. Syntactic and Structural Pattern Recognition.' Theory and Applications, World Scientific, Singapore, 1990.
• Ros90: Rosenstein, M. and Weitzman, L. Icon Editor: The Specification of Graphic Behavior without Coding, In Proceedings of the 23rd Annual Hawaii International Conference on Systems Sciences (January 2-5, Kailua-Kona, HI.). 1990, pp. 523-530.
• Sel91: Dorée Duncan Seligmann , Steven Feiner, Automated generation of intent-based 3D Illustrations, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.123-132, July 1991
• Wei93: Weitzman, L. and Wittenburg, K. Relational Grammars for Interactive Design, In IEEE Symposium on Visual Languages (August 24- 27, Bergen, Norway). 1993, pp. 4-i 1.
• Wie90: Charles Wiecha , William Bennett , Stephen Boies , John Gould , Sharon Greene, ITS: a tool for rapidly developing interactive applications, ACM Transactions on Information Systems (TOIS), v.8 n.3, p.204-236, July 1990 [doi>10.1145/98188.98194]
• Wit91: Wittenburg, K., Weitzman, L. and Talley, J. Unification-Based Grammars and Tabular Parsing for Graphical Languages, Journal of Visual Languages and Computing 2 (1991), pp. 347- 370.
• Wit92: Wittenburg, K. Earley-style Parsing for Relational Grammars, In Proceedings of IEEE Workshop on Visual Languages (Sept. 15-18, Seattle, Wa.). 1992, pp. 192-199.
• Wit93: Wittenburg, K. Adventures in Multidimensional Parsing: Cycles and Disorders. In Proceedings of the Third International Workshop on Parsing Technology (August, Tilburg, Netherlands and Durbuy, Belgium). Association for Computational Linguistics and Tilburg University, 1993, pp. 333-348.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Multi/mixed media

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing; Grammar types (e.g., context-free, context-sensitive)

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Format and notation

General Terms:
Algorithms, Design, Documentation, Languages