Spatial graph grammars for graphical user interfaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spatial graph grammars for graphical user interfaces

Full text

Pdf (2.56 MB)

Source

ACM Transactions on Computer-Human Interaction (TOCHI) archive
Volume 13 , Issue 2 (June 2006) table of contents

Pages: 268 - 307

Year of Publication: 2006

ISSN:1073-0516

Authors

Jun Kong	The North Dakota State University, ND
Kang Zhang	The University of Texas at Dallas, TX
Xiaoqin Zeng	The University of Texas at Dallas, Nanjing, China

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 168, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1165734.1165739 What is a DOI?

ABSTRACT

In a graphical user interface, physical layout and abstract structure are two important aspects of a graph. This article proposes a new graph grammar formalism which integrates both the spatial and structural specification mechanisms in a single framework. This formalism is equipped with a parser that performs in polynomial time with an improved parsing complexity over its nonspatial predecessor, that is, the Reserved Graph Grammar. With the extended expressive power, the formalism is suitable for many user interface applications. The article presents its application in adaptive Web design and presentation.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	Robert Allen , David Garlan, Formalizing architectural connection, Proceedings of the 16th international conference on Software engineering, p.71-80, May 16-21, 1994, Sorrento, Italy
	3	R. Bardohl , M. Minas , G. Taentzer , A. Schürr, Application of graph transformation to visual languages, Handbook of graph grammars and computing by graph transformation: vol. 2: applications, languages, and tools, World Scientific Publishing Co., Inc., River Edge, NJ, 1999
	4	Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
	5	Dorothea Blostein , Andy Schürr, Computing with graphs and graph transformations, Software—Practice & Experience, v.29 n.3, p.197-217, March 1999 [doi>10.1002/(SICI)1097-024X(199903)29:3<197::AID-SPE228>3.3.CO;2-6]
	6	Alan Borning , Richard Kuang-Hsu Lin , Kim Marriott, Constraint-based document layout for the Web, Multimedia Systems, v.8 n.3, p.177-189, October 2000 [doi>10.1007/s005300000043]
	7	P. Bottoni , M. F. Costabile , P. Mussio, Specification and dialogue control of visual interaction through visual rewriting systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.6, p.1077-1136, Nov. 1999 [doi>10.1145/330643.330644]
	8	Paolo Bottoni , Mark Minas, Workshop on Graph Transformation and Visual Modeling Techniques, Proceedings of the First International Conference on Graph Transformation, p.445-449, October 07-12, 2002
	9	Brachman, R. J. and Schmolze, J. G. 1985. An overview of the KL-ONE knowledge representation system. Cognitive Science, 171--216.
	10	Franz-Josef Brandenburg, Designing Graph Drawings by Layout Graph Grammars, Proceedings of the DIMACS International Workshop on Graph Drawing, p.416-427, October 10-12, 1994
	11	Margaret M. Burnett , Herkimer J. Gottfried, Graphical definitions: expanding spreadsheet languages through direct manipulation and gestures, ACM Transactions on Computer-Human Interaction (TOCHI), v.5 n.1, p.1-33, March 1998 [doi>10.1145/274444.274445]
	12	Margaret Burnett , Sherry Yang , Jay Summet, A scalable method for deductive generalization in the spreadsheet paradigm, ACM Transactions on Computer-Human Interaction (TOCHI), v.9 n.4, p.253-284, December 2002 [doi>10.1145/586081.586083]
	13	Burnett, M. M. 2006. Visual language research bibliography. http://www.cs.orst.edu/~burnett/vpl.html.
	14	Orkut Buyukkokten , Hector Garcia-Molina , Andreas Paepcke, Accordion summarization for end-game browsing on PDAs and cellular phones, Proceedings of the SIGCHI conference on Human factors in computing systems, p.213-220, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365102]
	15	S. K. Chang , Q. Y. Shi , C. W. Yan, Iconic indexing by 2-D strings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.3, p.413-428, May 1987 [doi>10.1109/TPAMI.1987.4767923]
	16	Yu Chen , Wei-Ying Ma , Hong-Jiang Zhang, Detecting web page structure for adaptive viewing on small form factor devices, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775184]
	17	Sitt Sen Chok , Kim Marriott, Automatic generation of intelligent diagram editors, ACM Transactions on Computer-Human Interaction (TOCHI), v.10 n.3, p.244-276, September 2003 [doi>10.1145/937549.937553]
	18	Eliseo Clementini , Paolino Di Felice , Peter van Oosterom, A Small Set of Formal Topological Relationships Suitable for End-User Interaction, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.277-295, June 23-25, 1993
	19	Eliseo Clementini , Paolino Di Felice , Daniel Hernández, Qualitative representation of positional information, Artificial Intelligence, v.95 n.2, p.317-356, Sept. 1997 [doi>10.1016/S0004-3702(97)00046-5]
	20	Anthony G. Cohn, Qualitative Spatial Representation and Reasoning Techniques, Proceedings of the 21st Annual German Conference on Artificial Intelligence: Advances in Artificial Intelligence, p.1-30, September 09-12, 1997
	21	A. G. Cohn , S. M. Hazarika, Qualitative spatial representation and reasoning: an overview, Fundamenta Informaticae, v.46 n.1-2, p.1-29, May 2001
	22	Thomas R. Dean , James R. Cordy, A Syntactic Theory of Software Architecture, IEEE Transactions on Software Engineering, v.21 n.4, p.302-313, April 1995 [doi>10.1109/32.385969]
	23	Del Bimbo, A., Vicario, E., and Zingoni, D. 1994. A spatial logic for symbolic description of image contents. J. Visual Lang. Comput. 5, 3, 267--286.
	24	H. Ehrig , G. Engels , H.-J. Kreowski , G. Rozenberg, Handbook of graph grammars and computing by graph transformation: vol. 2: applications, languages, and tools, World Scientific Publishing Co., Inc., River Edge, NJ, 1999
	25	H. Ehrig , H.-J. Kreowski , U. Montanari , G. Rozenberg, Handbook of graph grammars and computing by graph transformation: vol. 3: concurrency, parallelism, and distribution, World Scientific Publishing Co., Inc., River Edge, NJ, 1999
	26	Thorsten Fischer , Jörg Niere , Lars Torunski , Albert Zündorf, Story Diagrams: A New Graph Rewrite Language Based on the Unified Modeling Language and Java, Selected papers from the 6th International Workshop on Theory and Application of Graph Transformations, p.296-309, November 16-20, 1998
	27	Frank, A. U. 1996. Qualitative spatial reasoning: cardinal directions as an example. Int. J. Geograph. Inform. Sci. 10, 3, 269--290.
	28	Golin, E. J. and Reiss, S. P. 1989. The specification of visual language syntax. In Proceedings of the IEEE Workshop on Visual Languages. 105--110.
	29	Golin, E. J. 1991. Parsing visual languages with picture layout grammars. J. Visual Lang. Comput. 4, 2, 371--394.
	30	Volker Haarslev , Michael Wessel, GenEd - An Editor with Generic Semantics for Formal Reasoning about Visual Notations, Proceedings of the 1996 IEEE Symposium on Visual Languages, p.204, September 03-06, 1996
	31	Volker Haarslev, A fully formalized theory for describing visual notations, Visual language theory, Springer-Verlag New York, Inc., New York, NY, 1998
	32	Heckel, R., Mens, T., and Wermelinger, M. Eds. 2003. In Proceedings of the Workshop on Software Evolution Through Transformations Toward Uniform Support Throughout the Software Lift-Cycle. Electronic Notes in Theoretical Computer Science 72, 4. Elsevier Science.
	33	Hernández, D., Clementini, E., and Felice, P. D. 1995. Qualitative distance. In Proceedings of the Spatial Information Theory: A Theoretical Basis for GIS, Lecture Notes in Computer Science, vol. 988, 45--58.
	34	Pourang Irani , Colin Ware, Diagramming information structures using 3D perceptual primitives, ACM Transactions on Computer-Human Interaction (TOCHI), v.10 n.1, p.1-19, March 2003 [doi>10.1145/606658.606659]
	35	Jun Kong , Kang Mang, Graph-based consistency checking in spatial information systems, Proceedings of the 2003 IEEE Symposium on Human Centric Computing Languages and Environments, p.153-160, October 28-31, 2003
	36	Kreowski, H. J. and Knirsch, P. Eds. 2002. In Proceedings of the AGT2002-Applied Graph Transformation.
	37	Lakin, F. 1987. Visual grammars for visual languages. In Proceedings of the American Association for Artificial Intelligence. 683--688.
	38	Marriott, K. 1994. Constraint multiset grammars. In Proceedings of the IEEE Symposium on Visual Languages. 118--125.
	39	Marriott, K. and Meyer, B. 1997. On the classification of visual languages by grammar hierarchies. J. Visual Language Comput. 8, 375--402.
	40	Kim Marriott , Bernd Meyer , Kent B. Wittenburg, A survey of visual language specification and recognition, Visual language theory, Springer-Verlag New York, Inc., New York, NY, 1998
	41	Kim Marriott , Bernd Meyer , Laurent Tardif, Fast and efficient client-side adaptivity for SVG, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511510]
	42	Mens, T., Schürr, A., and Taentzer, G. Eds. 2002. In Proceedings of the GraBaTs 2002-Graph-Based Tools. Electronic Notes in Theoretical Computer Science 72, 2, Elsevier Science.
	43	Daniel Le Métayer, Describing Software Architecture Styles Using Graph Grammars, IEEE Transactions on Software Engineering, v.24 n.7, p.521-533, July 1998 [doi>10.1109/32.708567]
	44	Meyer, B. 1992. Pictures depicting pictures on the specification of visual languages by visual grammars. In Proceedings of the IEEE Workshop on Visual Languages. 41--47.
	45	Mark Minas, Concepts and realization of a diagram editor generator based on hypergraph transformation, Science of Computer Programming, v.44 n.2, p.157-180, August 2002 [doi>10.1016/S0167-6423(02)00037-0]
	46	Brad Myers , Scott E. Hudson , Randy Pausch, Past, present, and future of user interface software tools, ACM Transactions on Computer-Human Interaction (TOCHI), v.7 n.1, p.3-28, March 2000 [doi>10.1145/344949.344959]
	47	D. J. Peuquet , Ci-Xiang Zhang, An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane, Pattern Recognition, v.20 n.1, p.65-74, 1987 [doi>10.1016/0031-3203(87)90018-5]
	48	Pullar, D. and Egenhofer, M. 1988. Toward formal definitions of topological relationships. In Proceedings of the 3rd International Symposium on Spatial Data Handling. 225--241.
	49	G. Polese , Jun Kong , Kang Zhang, Spatial graph grammars for web information transformation, Proceedings of the 2003 IEEE Symposium on Human Centric Computing Languages and Environments, p.84-91, October 28-31, 2003
	50	J. Rekers , A.. Schuerr, A graph based framework for the implementation of visual environments, Proceedings of the 1996 IEEE Symposium on Visual Languages, p.148, September 03-06, 1996
	51	Rekers, J. and Schürr, A. 1997. Defining and parsing visual languages with layered graph grammars. J. Visual Languag. Comput. 8, 1, 27--55.
	52	Révész, G. E. 1983. Introduction to Formal Languages. McGraw-Hill Inc.
	53	Grzegorz Rozenberg , Emo Welzl, Boundary NLC graph grammars--basic definitions, normal forms, and complexity, Information and Control, v.69 n.1-3, p.136-167, April/May/June 1986 [doi>10.1016/S0019-9958(86)80045-6]
	54	Grzegorz Rozenberg, Handbook of graph grammars and computing by graph transformation: volume I. foundations, World Scientific Publishing Co., Inc., River Edge, NJ, 1997
	55	Andy Schürr, Specification of Graph Translators with Triple Graph Grammars, Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science, p.151-163, June 16-18, 1994
	56	A. Schürr , A. J. Winter , A. Zündorf, The PROGRES approach: language and environment, Handbook of graph grammars and computing by graph transformation: vol. 2: applications, languages, and tools, World Scientific Publishing Co., Inc., River Edge, NJ, 1999
	57	Soffer, A. and Samet, H. 1998. Pictorial query specification for browsing through spatially-referenced image databases. J. Visual Languag. Comput. 9, 6, 567--596.
	58	Weitzman, L. and Wittenburg, K. 1993. Relational gramamrs for interactive design. In Proceedings of the IEEE Symposium on Visual Languages. 4--11.
	59	Wittenburg, K. 1992. Earley-style parsing for relational grammars. In Proceedings of the IEEE Workshop on Visual Languages. 192--199.
	60	HTML Page Analysis Based on Visual Cues, Proceedings of the Sixth International Conference on Document Analysis and Recognition, p.859, September 10-13, 2001
	61	Shipeng Yu , Deng Cai , Ji-Rong Wen , Wei-Ying Ma, Improving pseudo-relevance feedback in web information retrieval using web page segmentation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775155]
	62	Zhang, D. Q. 1998. Generation of visual programming languages, Ph.D. Thesis, Macquarie University.
	63	Zhang, D. Q., Zhang, K., and Cao, J. 2001a. A context-sensitive graph grammar formalism for the specification of visual languages. Comput. J. 44, 3, 187--200.
	64	Kang Zhang , Da-Qian Zhang , Yi Deng, Graphical Transformation of Multimedia XML Documents, Annals of Software Engineering, v.12 n.1, p.119-137, December 2001 [doi>10.1023/A:1013310705258]
	65	Kang Zhang , Da-Qian Zhang , Jiannong Cao, Design, Construction, and Application of a Generic Visual Language Generation Environment, IEEE Transactions on Software Engineering, v.27 n.4, p.289-307, April 2001 [doi>10.1109/32.917521]
	66	Ke-Bing Zhang , Kang Zhang , Mehmet A. Orgun, Grammar-Based Layout for a Visual Programming Language Generation System, Proceedings of the Second International Conference on Diagrammatic Representation and Inference, p.106-108, April 18-20, 2002
	67	Zhen Zhang , Bin He , Kevin Chen-Chuan Chang, Understanding Web query interfaces: best-effort parsing with hidden syntax, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007583]
	68	Zhang, K., Kong, J., Qiu, M. K., and Song, G. L. 2005. Multimedia layout adaptation through grammatical specifications. ACM/Springer Multimedia Syst. 10, 3, 245--260.

CITED BY 5

	Guanglei Song , Jun Kong , Kang Zhang, AutoGen: Easing model management through two levels of abstraction, Journal of Visual Languages and Computing, v.17 n.6, p.508-527, December, 2006
	Hamed Ahmadi , Jun Kong, Efficient web browsing on small screens, Proceedings of the working conference on Advanced visual interfaces, May 28-30, 2008, Napoli, Italy
	Tiago Lopes Telecken , Ethan V. Munson , José Valdeni de Lima, Applying markup language resources in the specification of visual alphabets and visual sentences, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	Chunying Zhao , Jun Kong , Jing Dong , Kang Zhang, Pattern-based design evolution using graph transformation, Journal of Visual Languages and Computing, v.18 n.4, p.378-398, August, 2007
	Jun Kong , Kang Zhang , Jing Dong , Dianxiang Xu, Specifying behavioral semantics of UML diagrams through graph transformations, Journal of Systems and Software, v.82 n.2, p.292-306, February, 2009