Frank Drewes

- research areas -


A descriptive general headline of my research could read

Languages and Transformations of Trees, Pictures, and Graphs

since my research in theoretical computer science focusses on devices that generate and transform such objects. The techniques used stem from classical language theory, algebra, category theory, or whatever else seems appropriate and is available to me. The investigated questions cover language theoretic properties, complexity and computability problems, and implementation issues. The following four subareas (which are, however, interrelated by several crosslinks) can be identified:

(a) Tree languages and tree transductions
This research contributes to the large and vivid area of tree grammars and tree transducers which originated in the early seventies, motivated by problems in mathematical linguistics and compiler construction. Due to the fact that trees, viewed as expressions over the operation symbols of an algebra, can represent arbitrary objects, the results obtained in this area often have some impact on areas (c)-(e).

(b) Algorithmic learning
Algorithmic learning tries to derive explicit formal descriptions of concepts that are only implicitly available through examples or similar information. My research interest concerns mainly learning algorithms for tree languages and tree series, where I have made some contributions together with J. Högberg and H. Vogler.

(c) Picture languages
Pictures can be obtained by evaluating expressions in a suitable picture algebra, the benefit being that any device that generates or transforms trees (i.e., such expressions), can be viewed as a picture generator resp. transformer. Research in this area is devoted to the theoretical investigation of this generation mechanism and its properties, advantages and limitations, and its relations with other picture generating devices (such as, e.g., the picture generating devices studied in fractal geometry). Among other things, this research has resulted in a book about grammatical picture generation.

(d) Graph languages and graph transformation
Here, graph generation mechanisms (mostly context-free ones, and in particular hyperedge-replacement graph grammars) as well as rule-based graph transformation systems are studied. The latter does in particular include the transformation of hierarchical graphs by an extension of the so-called double-pushout approach to graph transformation. This yields graph transformation systems of universal computing power and is hoped to provide a suitable basis for a visual, object-oriented programming language based on graph transformation.

(e) TREEBAG
TREEBAG is a software system whose central feature is the generation and transformation of trees. These can be evaluated by associating an appropriate algebra with them (a picture algebra, for instance). The resulting objects (pictures, trees, strings, numbers, etc.) can be displayed on the screen, but also saved to a PostScript file for high-quality printouts or inclusion in text files. For more information - or in order to download a copy of the system - please consult the TREEBAG home page.


back to Frank Drewes' home page