next up previous
Next: Related Work Up: No Title Previous: Theoretical Foundation




Figure 4: GenEd: petri net for reader-writer problem (simplified) (full image)

Figure 4 shows the user interface in detail. The workspace window displays a fully classified petri net example (see Section 3.3.1 for explanations). The next sections describe GenEd's user interface, its implementation, and two example applications.

User Interface

Figure 5: GenEd: magnified selection of petri net

The user interface contains several (scrollable) panes and a menu bar at the top. The three horizontal panes below the menu bar offer the selection of object types and the setting of drawing attributes for elements and text. The left vertical pane shows a variety of modifiable parameters for controlling display options and scaling factors. The center pane (workspace) contains a petri net for the reader-writer problem. It displays the petri net elements (place as circle, transition as rectangle, edge as (spline) arrow, token as bullet, capacity label as gray number). The elements are also labeled with the concept names as computed by the classification phase of the spatial parser. The right pane is used to inform the user about computed concept memberships, role fillers, etc. The horizontal pane below the three vertical panes is the command pane. Users have the choice whether they enter commands as gestures (mouse movement, clicks) or as text commands. The pane at the bottom always shows object-sensitive documentation about available gestures.

Users can always select a collection of elements in the workspace with an enclosing bounding box and aggregate them into a composition object. The contents of the workspace can be zoomed in or out (see Figure 5 for a magnified selection of the petri net). In general, GenEd offers many operations on objects that are also available in commercial graphic editors (create, delete, copy, move, scale, rotate, hide, show, inspect, arrangement, save, restore, undo list).

Figure 6: Library menu with submenu for places.

It is worth to note that special handles might be attached to arbitrary objects. These handles can be used to fix relative positions between objects or to define stretchable lines whose end points might be fixed at objects. Primitive and composition objects may be stored in and retrieved from a user-defined library. Figure 6 shows a submenu displaying visualizations of petri net places stored in the library. The workspace can be saved in and loaded from a file.


GenEd is implemented in Common Lisp using the Common Lisp Object System (CLOS) and the Common Lisp Interface Manager (CLIM) as interface toolkit. The classification of concepts and the parsing of actual drawings take place by using CLASSIC [9,10] as DL system. CLASSIC is also implemented in Common Lisp. GenEd consists of 28 modules with a total of about 300 KB source code (without CLIM, CLOS, and CLASSIC). GenEd is fully implemented with the features described in this paper.

Example Session

We demonstrate two visual notations whose specifications were created with GenEd. The first notation describes place-transition petri nets. The second notation defines entity-relationship (ER) diagrams.

Petri Nets


A petri net is a triple with a set of places, a set of transitions, and a relation representing edges.

A tuple defines a place-transition net if the following conditions hold. The tuple is a petri net with places and transitions . defines a capacity for each place. specifies the weight of every edge. , defines the initial marking.

The complete specification of place-transition nets is out of scope of this paper. We already proved in [1] with Pictorial Janus that our approach can handle complex visual notations. We only outline the design of the specification for place-transition nets. We define concepts representing legal constellations for places, transitions, and edges. A petri net is specified as a composite object consisting of at least 5 parts. Primitive concepts are typeset in a slanted style.

Petri nets are specialized to place-transitions nets after defining capacity labels, places with capacity, token, places with tokens, edges with capacity, and active transitions.

An interesting special case of place-transition nets is a predicate-event net. All places and edges have a maximal capacity of 1.

The definition of predicate-event places and transitions are omitted. There are still other interesting concepts characterizing special petri net elements that are left out due to lack of space. However, the next section discusses entity-relationship diagrams which are specified in almost full detail.

Entity-Relationship Diagrams

Figure 7: An ER diagram modelling airlines (full image)

Figure 8: A simple entity-relationship diagram

Our definition of a subset of entity-relationship (ER) diagrams was inspired by [11]. We present this example in order to demonstrate the expressiveness of our specification language and the reasoning capabilities of GenEd. Due to space constraints we show only a screen shot of GenEd (see Figure 7) displaying a subpart of a larger example modelling relationships in an airline company. Figure 8 shows a simple ER diagram specifying a relationship between a pilot and an aircraft. The design and evaluation of the specification for this simplified type of ER diagrams took about half an hour for an experienced user of GenEd. We assume a few primitive concepts and spatial relations representing geometrical objects (rectangle, circle, diamond, line, text) used in our ER diagram language.


A relationship-entity connection is a line that touches exactly one text label (expressing cardinality) and two other regions (rectangle or diamond). A cardinality is a text string with values chosen from the set .

An attribute-entity connection is a line that touches only two regions (circle or rectangle) and no text string.


An entity is a rectangle that contains its name. It touches at least one relationship-entity and optionally some attribute-entity connectors. It is linked with at least one diamond.


A relationship is a diamond that contains its name. It touches one relationship-entity and optionally some attribute-entity connectors. It is linked with two entities.


An attribute is a circle that contains its name. It touches one attribute-entity connector and is linked with an entity.

Geographic Information Systems

The last example suggests that our approach might also be usable in the domain of geographic information systems (GIS). This example demonstrates the advantages of a forward-chaining parser and the necessity for non-monotonic reasoning. In the context of an aerial image interpretation system we assume that there exists a two-dimensional model of a geographic scene stored in a GIS. In this system multi-spectral images are interpreted, for example, in order to detect changes in the scene. To speak of an interpretation of an image, e.g. a change has to be described not only at the geometrical level but also at the conceptual level. We use GenEd to create a model of an example world. This small example consists of two primitive objects (water surface and house) that can be easily detected in aerial images by using spectral analysis. We assume a symmetric relation `near' that may hold for objects if they are located next to each other.

Figure 9: Sketches of the villa example.

A swimming pool is a water surface with at least one house in its neighborhood (relation `near'). A villa is a house with at least one swimming pool in its neighborhood. The left part of Figure 9 sketches an image of a scene with several houses along a street. In this scene no villa has been recognized since there exists no water surface next to a house. It is important to note that each house could still incrementally be classified as villa provided a water surface is found in the neighborhood. This is visualized in the right part of Figure 9. This particular house is now classified as villa and the water surface as swimming pool. This reclassification is triggered by the newly added water surface and affects only houses in the neighborhood of this water surface. It is automatically performed by the forward-chaining parser and always results in the most-specialized classification (that is what we are interested in). A backward-chaining parser would be inadequate if we imagine a scene with a large amount of houses and only a small number of water surfaces since we usually do not know in advance where a water surface might be detected. Thus, it is also not acceptable to query the state of all houses. This scenario illustrates that GenEd might also be a suitable query interface for a GIS.

next up previous
Next: Related Work Up: No Title Previous: Theoretical Foundation

Volker Haarslev
Fri May 24 16:47:01 MET DST 1996