On the classification of visual languages by grammar hierarchies

被引:25
作者
Marriott, K [1 ]
Meyer, B [1 ]
机构
[1] UNIV COLORADO,DEPT COMP ENGN,BOULDER,CO 80303
关键词
D O I
10.1006/jvlc.1997.0053
中图分类号
TP31 [计算机软件];
学科分类号
081202 [计算机软件与理论]; 0835 [软件工程];
摘要
Visual language specification has been investigated for more than two decades now and many different formalisms for specifying and parsing visual languages have been invented. However, there has been little attempt to develop a systematic and comprehensive hierarchy of visual languages based on their formal properties. Given the importance of the Chomsky hierarchy for the theory of textual languages and the difficulty of comparing these many different visual language formalisms, it is clear that there is a need for such a hierarchy. We develop a hierarchy for visual languages and investigate the expressiveness and cost of parsing for classes defined therein. Although the hierarchy is based on the constraint multiset grammar formalism, we sketch how other visual language specification formalisms can be mapped into constraint multiset grammars so that a comparison is made possible. One consequence of our work is that a large class of 'naturally occurring' visual languages are inherently context-sensitive, so that the core of such a hierarchy has to be built around different forms of context-sensitivity. (C) 1997 Academic Press Limited.
引用
收藏
页码:375 / 402
页数:28
相关论文
共 20 条
[1]
ABE N, 1973, J COMPUTER SYSTEM SC, V7
[2]
CHOCK SS, 1995, IEEE S VISUAL LANGUA, P242
[3]
COSTAGLIOLA G, 1993, IEEE S VISUAL LANGUA, P306
[4]
Courcelle B., 1990, HDB THEORETICAL COMP, VB
[5]
FERRUCCI F, 1994, IEEE S VISUAL LANGUA, P245
[6]
GIPS J, 1974, THESIS STANFORD U
[7]
GOLIN E, 1989, IEEE S VISUAL LANGUA, P105
[8]
GOLIN EA, 1991, THESIS BROWN U
[9]
HAARSLEV V, 1995, IEEE S VIS LANG, P156
[10]
HELM R, 1991, ACM C HUM FACT COMP, P105