Bunt H., Beun R.-J., Borghuis T. (eds.) Multimodal Human-Computer Communication. Systems, Techniques, and Experiments

Подождите немного. Документ загружается.

Visual Language Parsing: If I Had a Hammer... 241

Fig. 4. a-c. A page layout design sequence

242 Kent Wittenburg

expressions in the input. In Fig. 4a, it can be noted that the number item is

roughly above and left aligned to the text item. A pattern has been recognized

that can lead to the automatic creation of a caption object. In Fig. 4b, this

action has been excercised, and, in the process, the basic elements are left-

aligned exactly and certain font styles are selected. Then this newly created

caption object is added to the input and another fragment is recognized whose

constituents are an image and a caption. The action to create a figure composite

object is exercised, which results in constraints for left-alignment and certain

marginal spacing arrangements.

The architecture for such design assistance parallels visual language interpre-

tation. Obviously there is a different 'semantics'. Other than that, the primary

difference has to do with the fact that a full interpretation, and thus a full

parse, is not required, so there is a different interaction loop. This loop allows

more flexibility to the user, which is appropriate in applications where sugges-

tions and help are welcome but deviations from the norm are to be tolerated. In

such an application, bottom-up parsing rather than syntax-directed editing is a

requirement.

Similar functionality in the context of sketching with pen-based input has

been suggested by Gross (1994), Landay and Myers (1995), and Kramer (1994),

although none of them make use of grammar-based specification or parsing meth-

ods. Earlier work by Wittenburg et al. (1991) used a grammar-based framework

to interpret pen-based input, but did not consider design support as an applica-

tion.

5.2 Multimedia Document Generation

Another application area involves multimedia document generation. Weitzman

and Wittenburg (1996) propose grammar-based methods for what they refer to

as 'articulation' of electronic documents in heterogeneous environments. In the

generation-as-parsing model, the input is abstract representations of content, and

the output is forms for creating multimedia objects and their layout. Figures 5

and 6 illustrate one of the primary motivations for a system such as this. They

are examples of realized output of the system.

The information is the same in the two figures but its presentation is not,

motivated by differences in presentation resources available in the end-delivery

environments. The design in Fig. 5 is appropriate for a large, high-resolution

display; the one in Fig. 6 is appropriate for a small screen device, such as a

hand-held digital assistant. Figure 6 displays just the first step of a complete

repair procedure. As part of the presentation, the horizontal bar at the top of

the page becomes an active object which controls the presentation of remaining

elements. As the user interacts with the bar, information is presented temporally

that is all laid out spatially in Fig. 5.

While designers could create each of these alternative designs individually by

hand, the complexity of accommodating myriad variations in today's networked

environments is enormous. The Weitzman/Wittenburg proposal is that the de-

signers might be able to author a set of general realization rules using design

Visual Language Parsing: If I Had a Hammer... 243

Fig. 5. A presentation for a large display

Fig. 6. A presentation for a small display

244 Kent Wittenburg

assistance technology such as was discussed in the last section. The architecture

is shown in Fig. 7. Abstract content takes the form of objects and relations,

Fig. 7. System architecture

and could be held in a database. Rules include a syntax, i.e., a specification

for matching against abstract content, and a semantics, i.e., a set of forms to

define multimedia objects and layout constraints. Given the content as input

together with parameters that define different environment conditions, higher-

dimensional parsing is used to map to different abstract structures and different

realization rules. Decompositions evident in the parse trees determine, for in-

stance, different screens of information. A translation step employing attribute

evaluation then produces forms for creation of media objects and temporal and

spatial constraints that need to be satisfied. Constraint solving is then utilized

to produce the final layout.

Visual Language Parsing: If I Had a Hammer... 245

Brandenburg (1994) has a similar architecture for layout of hierarchically

structured graphs in which he uses dynamic programming methods to control the

search through alternative design solutions at each node of the derivation tree. He

assumes classical attribution techniques, rather than general contraint solving,

for the actual computation of values necessary for full layout specifications.

5.3 Hierarchical Aggregation

The last application area I will mention is one involving visualization of at-

tributed graphs. As in the previous examples, a derivation tree is the starting

point for providing useful services to the underlying application. Wittenburg and

Weitzman (1997a; 1997b) have authored an application to support documenta-

tion and redesign of work process flows. Workflow models can be large and

complex, and, just as with computer programming, good design entails decom-

position into manageable chunks. For workflows, repeatable processes should

be encapsulated so as to be reuseable in other parts of the models. Existing

commercial flowgraph drawing tools standardly support the feature of hierar-

chically structured flowgraphs, where a single node in a graph can be expanded

into another window, in which more detail is shown. However, these hierarchical

structures must be assembled by hand and, once created, they are permanent.

A feature offered in this tool is for users to be able to dynamically aggregate

subgraphs in a larger graph through interactive parsing. The subgraphs can then

be collapsed or expanded to suit visualization and modeling needs. This allows

the creation of views of workflow processes that can span a large part of the rel-

evant business domain but that nonethless contain a manageable level of detail.

Figure 8a shows a subgraph that has been selected through interactive parsing.

In Fig. 8b, the user has chosen to collapse that subgraph.

It is possible that higher-dimensional parsing techniques can be used in other

information domains that can benefit from hierarchical aggregation. Sablowski

and Frick (1997), for example, used a technique similar to graph grammar parsing

to form hierarchical structures over World Wide Web link graphs.

6 Conclusion

This chapter has considered how higher-level grammars and parsing might con-

tribute to visual modes of human-computer communication. The results so far

have been mixed. It is not clear that visual parsing is actually necessary to

interpret visual language expressions under the control of a Graphical User In-

terface. Nevertheless, there are potential benefits when/if more progress can be

made on error-correction and incremental editing. The field really must agree on

standard formalisms (Constraint Multiset Grammars is one candidate) as well as

standard representations for input. The continuing proliferation of ill-understood

variations on visual language formalisms is not helpful.

246 Kent Wittenburg

Fig. 8. Interactive parsing in support of visualization

Visual Language Parsing: If I Had a Hammer... 247

I am more sanguine about the immediate prospects of higher-dimensional

parsing for solving problems in other areas of visual communication. I men-

tioned the examples of design support, generation-as-parsing, and hierarchical

composition in support of visual focusing and modeling. These techniques are

one level removed from the basic interpretation processes. They are applicable

once visual objects and relations are formed, which makes it possible for them

to be used with GUIs as well as with pen-based systems or perhaps with other

input devices such as data gloves or eye-tracking.

Acknowledgements

I am grateful to Kim Marriott, Bernd Meyer, and Franz Brandenburg for con-

versations on topics related to this paper.

References

Aho, A., and Johnson, S.C. (1974), Programming Utilities and Libraries - LR Parsing,

Computing Surveys, June 1994.

Aho, A., Sethi, R., and Ullmml, J. (1986), Compilers: Principles, Techniques, and

Tools, Addison-Wesley.

Anderson, R.H. (1968), Syntax-Directed Recognition of Hand-Printed Two-

Dimensional Mathematics. In Interactive Systems ]or Experimental Applied Math-

ematics, Klerer, M., and Reinfelds, J. (eds.), Academic Press.

Backlund, B., Hagsand, O., and Pehrson, B. (1990), Generation of Visual Language-

oriented Design Environments, Journal of Visual Languages and Computing 1, pp.

333-354.

Baird, H. (1990), Industrial Applications. In Syntactic and Structural Pattern Recogni-

tion: Theory and Applications, Bunke, H. and Sanfeliu, A. (eds.), World Scientific,

pp. 369-380.

Brandenburg, F. 1994. Designing Graph Drawings by Layout Graph Grammars. In

Graph Drawing: DIMACS International Workshop, R. Tamassia and I.G. Tollis

(eds.), Lecture Notes in Computer Science 894, Springer-Verlag, pp. 416-427.

Brandenburg, F. (1989), On Polynomial Time Graph Grammars. In STACS 88: 5th

Annual Symposium on Theoretical Aspects of Computer Science, Goos, G., and

Hartmanis, J. (eds.), Lecture Notes in Computer Science 294, Springer-Verlag, pp.

227-236.

Bunke, H. (1982), Attributed Programmed Graph Grammars and their Application

to Schematic Diagram Interpretation, IEEE Transactions on Pattern Analysis and

Machine Intelligence 4, PP. 574-582.

Chang, S.-K. (1988), The Design of a Visual Language Compiler. In Proceedings of

IEEE Workshop on Visual Languages, Pittsburgh, Pennsylvania, USA, pp. 84-91.

Chok, S.S., and Marriott, K. (1995), Automatic Construction of User Interfaces from

Constraint Multiset Grammars. In Proceedings of IEEE Workshop on Visual Lan-

guages, Darmstadt, Germany, pp. 90-98.

Costagliola, G., Tomita, M., and Chang, S.K. (1991), A Generalized Parser for 2-D

Languages. In Proceedings of IEEE Workshop on Visual Languages, Kobe, Japan,

pp. 98-104.

248 Kent Wittenburg

Cox, P.T., Giles, F.R., and Pietrzykowsky, T. (1989), Prograph: a step towards liber-

ating programming from textual conditioning. In Proceedings of IEEE Workshop

on Visual Languages, Rome, Italy.

Crimi, A., Guercio, A., Nota, G., Pacini, G., Tortora, G., and Tucci, M. (1991), Rela-

tion Grammars and their Application to Multi-dimensional Languages, Journal of

Visual Languages and Computing 2, pp. 333-346.

Curly, J. (1995), Graph Grammars and Their Application to Computer Science: 5th

International Workshop, Williamsburg, Va, Usa, Springer-Verlag.

Fu, K.-S. (1974), Syntactic Methods in Pattern Recognition, Academic Press.

Golin, E., and Reiss, S. (1989), The Specification of Visual Language Syntax. In Pro-

ceedings of IEEE Workshop on Visual Languages, Rome, Italy, pp. 105-110.

Golin, E. (1991), Parsing Visual Languages with Picture Layout Grammars, Journal

of Visual Languages and Computing 2, pp. 371-393.

Gross, M. (1994), Recognizing and Interpreting Diagrams in Design. In Proceedings

of Advanced Visual Interfaces (AVI), Catarci, T. Costabile, M., Levialdi, S., and

Santucci, G. (eds).

Helm, R., and Marriott, K. (1991), A Declarative Specification and Semantics for Visual

Languages, Journal of Visual Languages and Computing 2, pp. 311-331.

Jagadeesh, J. and Wang, Y. (1993), Labview, Computer, February 1993.

Joshi, A. (1985), Tree Adjoining Grammars: How Much Context-Sensitivity is Re-

quired to Provide Reasonable Structural Descriptions? In Perspectives, Dowty, D.,

Karttunen, L., and Zwicky, A. (eds.), Cambridge University Press, pp. 206-250.

Kahn, K. and Saraswat, V. (1990), Complete Visualizations of Concurrent Programs

and their Executions. In Proceedings of IEEE Workshop on Visual Languages,

Skokie, Illinois, USA, pp. 7-14.

Kramer, A. (1994), Translucent Patches-Dissolving Windows. In Proceedings of the

ACM Symposium on User Interface Software and Technology (UIST), pp. 121-130.

Landay, J. and Myers, B. (1995), Interactive Sketching for the Early Stages of User

Interface Design. In Proceedings of ACM Conference on Human Factors in Com-

puting (CHI), pp. 43-50.

Marriott, K. and Meyer, B. (1997), The CCMG Visual Language Hierarchy. In Theory

of Visual Languages, Marriott, K. and Meyer, B. (eds.), Lecture Notes in Computer

Science, Springer Verlag (in press).

Marriott, K., Meyer, B., and Wittenburg, K. (1997), Survey: Visual Language Speci-

fication and Recognition. In Theory of Visual Languages, Marriott, K. and Meyer,

B. (eds.), Lecture Notes in Computer Science, Springer Verlag (in press).

Meyer, B. (1992), Pictures Depicting Pictures: On the Specification of Visual Languages

by Visual Grammars. In Proceedings of IEEE Workshop on Visual Languages, Seat-

tle, Washington, USA, pp. 41-47.

Minas, M. and Viehstaedt, G. (1995), DiaGen: A Generator for Diagram Editors Pro-

viding Direct Manipulation and Execution of Diagrams. In Proceedings of IEEE

Workshop on Visual Languages, Darmstadt, Germany.

Nagl, M. (1983), Bibliography on Graph Rewriting Systems (Graph Grammars), Bul-

letin of European Association of Theoretical Computer Science 20 (Austria), pp.

114-148.

Pineda, L. (1992), Reference, Synthesis and Constraint Satisfaction, Eurographics 11,

pp. C333-C344.

Rekers, J. (1994), On the Use of Graph Grammars forDefining the Syntax of Graph-

iced Languages. In Proceedings of Colloquium on Graph Transformation and its

Application in Computer Science, Palma de Mallorca, Spain.

Visual Language Parsing: If I Had a Hammer... 249

Rosenfeld, A. (1990), Array, Tree, and Graph Grammars. In Syntactic and Structural

Pattern Recognition: Theory and Applications, Bunke, H. and Sanfeliu, A. (eds.),

Singapore: World Scientific.

Sablowski, R. and Frick, A. (1997), Automatic Graph Clustering. In Graph Drawing:

Symposium on Graph Drawing GD '96, North, S. (ed.), Berkeley, California, USA,

Lecture Notes in Computer Science 1190, Springer-Verlag, pp. 4395-400.

Shaw, A.C. (1969), A Formal Picture Description Scheme as a Basis for Picture Pro-

cessing Systems, Information and Control 14, pp. 9-52.

Soiffer, N.M. (1991), The Design of a User Interface for Computer Algebra Systems,

Ph.D. Thesis, University of California at Berkeley.

Telelogic (1997), http://www.telelogic.se.

0skiidarli, S. and Dinesh, T.B. (1995), Towards a visual programming environment

generator for algebraic specifications. In IEEE Symposium on Visual Languages,

Darmstadt, Germany.

Wahlster, W. (1991), User and Discourse Models for Multimodal Communication. In

Intelligent User Interfaces, Sullivan, J.W. and Tyler, S.W. (eds.), ACM Press, pp.

45-67.

Weimer, D. and Ganapathy, S.K. (1992), Interaction Techniques Using Hand Track-

ing and Speech Recognition. In Multimedia Interface Design, Blattner, M.H. and

Dannenberg, R.B. (eds.), ACM Press, pp. 109-126.

Weitzman, L. and Wittenburg, K. (1993), Relational Grammars for Interactive Design.

In Proceedings of IEEE Symposium on Visual Languages, Bergen, Norway, pp. 4-11.

Weitzman, L., and Wittenburg, K. (1994), Automatic Generation of Multimedia Doc-

uments Using Relational Grammars. In Proceedings of ACM Multimedia 94, San

Francisco, California, USA, pp. 443-451.

Weitzman, L. and Wittenburg, K. (1996), Grammar-based Articulation for Multimedia

Document Design, Multimedia Systems 4, PP. 99-111.

Wittenburg, K., Weitzman, L., and Talley, J. (1991), Unification-Based Grammars

and Tabular Parsing for Graphical Languages, Journal of Visual Languages and

Computing 2, pp. 347-370.

Wittenburg, K. (1992), Earley-style Parsing for Relational Grammars. In Proceedings

of IEEE Workshop on Visual Languages, Seattle, Wa., USA, pp. 192-199.

Wittenburg, K. (1996), Predictive Parsing for Unordered Relational Languages. In

Recent Advances in Parsing Technologies, Bunt, H. and Tomita, M. (eds.), Kluwer,

pp. 389-411.

Wittenburg, K. and Weitzman, L. (1997a), Qualitative Visualization of Processes: At-

tributed Graph Layout and Focusing Techniques. In Graph Drawing: Symposium

on Graph Drawing GD '96, North, S. (ed.), Berkeley, California, USA, Lecture

Notes in Computer Science 1190, Springer-Verlag, pp. 401-408.

Wittenburg, K. and Weitzman, L. (1997b), Relational Grammars: Theory and Prac-

tice in a Visual Language Interface for Process Modeling. In Theory of Visual

Languages, Lecture Notes in Computer Science, Marriott, K. and Meyer, B. (eds.),

Springer Verlag (in press).

Wolfram, S. (1996), The Mathematica Book, Cambridge University Press.

Anaphora in Multimodal Discourse

John Lee and Keith Stenning

Human Communication Research Centre, University of Edinburgh

2, Buccleuch Place, Edinburgh EH8 9LW, Scotland, UK

j ohn~cogsci, ed. ac. uk

Abstract. The question is addressed whether the linguistic phenomenon

of anaphora exists in multimodal dialogue. Anaphora is contrasted with

deixis and ellipsis as being an essentially co-referential phenomenon; it

is argued that existing discussions in the areas of HCI and presentation

generation, e.g. by Singer and Wahlster, have failed to demonstrate mul-

timodal anaphora. This is argued to be because the 'token-referential'

nature of graphics (as opposed to the 'type-referential' nature of lan-

guage) means that identification and predication can't be separated;

hence graphics tends to be 'unfocussed', and re-identification of refeer-

ents for further predication does not happen.

1 Introduction

This chapter seeks to clarify some of the issues concerning the phenomenon of

anaphora in natural language, and its extension to multimodal discourse and

dialogue. The literature on human-computer interaction (HCI), in particular,

contains a number of examples where the concept of anaphora has been applied

to graphical expressions, and to the relation between graphical and linguistic ex-

pressions, in ways which sometimes do not relate clearly to the issues underlying

the uses of the term in linguistics.

The general question that needs to be confronted is what the use would be of

speaking of cross-modal anaphora; i.e. what theoretical utility could be derived

from the analogy with language implied by the term. In linguistics, it is intended

to pick out a set of phenomena that support interesting generalisations. They are

all coreferential cases; they often have certain constraints concerning e.g. gender

and animacy of the coreferring expressions; they may relate particularly to the

claims of a theory, such as Chomsky's 'government and binding' structures. Even

here it can be difficult to decide whether a relationship is best accounted for by

such quasi-syntactic issues, or whether it should be treated as resulting from an

inference based on semantic and pragmatic information about some situation.

In the final analysis, it may in fact appear that anaphora is simply a subclass of

cases of reference-assignment which it is wholly artificial and ultimately point-

less to single out. This conclusion would be strongly resisted in linguistics, and

perhaps with good reason, but is not so clearly resistible in multimodal contexts.

Although anaphora is often discussed in the context of

discourse,

we believe

that this is an important first step to understanding the issues at play in the