Frank Drewes
- master thesis proposals -
|
|
 |
TREEBAG
is a system in which four different types of components can be combined
interactively:
- tree grammars, which generate trees,
- tree transducers, which transform input trees into
output trees,
- algebras, which interpret trees as expressions over some
domain and evaluate them accordingly, and
- displays, which visualize the values of trees on the
screen.
Since arbitrary networks of these components can be created, several
types of string, tree, and picture grammars can be simulated in
TREEBAG. On the one hand, the interactive composition of the desired
TREEBAG components provides a maximum of flexibility. On the other
hand, even frequently used types of configurations must always be
composed of their components ``by hand''. In order to avoid this, the
idea is to introduce and implement a notion of meta components. One
type of meta component could, for instance, be ``context-free Chomsky
grammar''. Internally, such a meta component have to be composed of
ordinary TREEBAG components, but the user could directly define a
context-free Chomsky grammar.
(1 person, 20p.)
In the TREEBAG
system, trees generated by tree grammars are considered as
expressions. These expressions are evaluated by components called algebras.
Finally, the resulting objects can be displayed on the screen using
appropriate components of type display. Although, in the
TREEBAG context, a tree grammar can be any kind of device which
produces trees, trees are usually generated by applying some sort of
rules to nonterminal items in a nondeterministic manner. Unfortunately,
until now there is no way of interactively selecting rules and the
nonterminals to which they shall be applied. Basically, if the user
selects a nonterminal in the display, the system should provide a menu
showing the applicable rules, and wait for the user to select one of
them.
At first sight, this may seem to be a simple programming exercise,
but it does in fact require a nontrivial interaction model that fits
into the TREEBAG structure. This is because only the tree grammar
``knows'' what it means to apply a rule to a nonterminal, whereas the
user selects an item shown by the display. The display, however, does
not know anything about the correspondence between the object it
displays and the tree which describes it. Thus, tree grammars,
algebras, and displays must work together in order to accomplish this
interaction task. Since there are several types of grammars, algebras,
and displays which may be combined in a nearly arbitrary way, the
interaction model to be developed must be rather flexible.
(1-2 persons, 20p.)
TREEBAG
can be extended in many ways. Currently, some students in Bremen
(Germany) develop algebras and displays which make it possible to
generate and display three-dimensional pictures. (Until now, only
two-dimensinoal pictures can be generated.) Many other extensions of
this kind are possible, for example algebras and displays dealing with
graphs. Furthermore, in the theory of tree grammars and tree
transducers many classes have been defined and studied, and most of
them are more powerful than those which are currently available in
TREEBAG. Finally, there exist a number of theoretical results which
allow to modify or analyze these devices. Normally, such theoretical
considerations cannot directly be turned into practice. Design
decisions must be made which are irrelevant for the theory but
important for any practical realization, and the efficiency of
algorithms presented in the literature sometimes implies that suitable
restrictions must be found.
(typically 1 person, 20p.)
back to Frank Drewes' home page