Theory and Implementation of Systems Transforming Complex Structures

Project description

1 Introduction

Theoretical computer science studies the mathematical foundations of computer science. Typical issues addressed are the exact specification of program behaviour, algorithmic complexity, and provably correct software. Being a continuation of my earlier research in this field, the project focuses on the theory and implementation of formal systems that generate and transform complex structures, most notably, trees, graphs, and pictures. Brief descriptions of the respective areas are given next; for more information, see [16] for Sects. 1.1 and 1.3, and Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1–3, World Scientific 1997–1999, for Sect. 1.2.

1.1 Tree grammars and tree transducers

Since the 1960s, this area studies abstract devices that transform (mathematical) trees. Initially, this was motivated by research on the syntax-directed translation of programming languages. However, by viewing a tree as an expression that denotes a value (obtained by evaluating the expression), techniques and results regarding tree grammars and tree transducers become useful in many other domains, an example being picture generation.

1.2 Graph transformation

This area results from a combination of two of the most central notions in computer science: graphs and rules. Being the most versatile and general data structure known, graphs can represent all kinds of system states, whereas rules describe systematic state changes (i.e., algorithms) at a high abstraction level. Their combination yields a formal theory for the description of both static and dynamic aspects of, e.g., complex software systems.

1.3 Picture generation

The great importance of pictures in applications raises the question how sets of pictures can be specified effectively. Whereas various different methods have been proposed and studied independently, many of them can be perceived as tree grammars that generate expressions denoting pictures (see Sect. 1.1). The resulting notion of tree-based picture generation [16] is probably the most important contribution of the project to the theory of picture generation thus far.

2 Aims, hypotheses, and methods

The aim of the project is to continue the work within the areas described above, with special emphasis on the practical relevance of the theoretical results. As in the past, algorithmic properties of formal systems are investigated, and implementations of the theoretical results are provided. In this way, a link between theory and practice is established. The following paragraphs, which mirror the structure of the preceding section, contain slightly more detailed information. Since the work of the project has recently led to interesting new research topics in each of the three subareas, the presentation focuses on these topics rather than attempting to give a complete picture and mentioning every ongoing research activity.

2.1 Tree grammars and tree transducers

In this area, a variety of topics are pursued in cooperation with various other researchers. An ongoing Sida/NFR project (2003–2006) in collaboration with researchers from South Africa studies tree grammars and tree transducers whose behaviours are regulated by certain types of context conditions [7, 19, 20]. Recently, this has led to a novel regulation mechanism called bag context [14, 21]. Even if no further funding can be raised after 2006, research in this area will be continued in collaboration with our South African colleagues. Another line of ongoing research concerns algorithmic learning. Traditionally, the aim is to derive an explicit grammatical description of an unknown language – in our case a tree language – from examples or similar data [8, 11, 13, 18]. In collaboration with H. Vogler (Univ. of Dresden, Germany), this has recently been generalized by developing a learning algorithm for recognizable tree series [22]. (A tree series maps trees into a semiring, thus generalizing the notion of a tree language.) This is the first time algorithmic learning of tree series has been addressed, thus opening up a new research area which provides many interesting questions. Later this year, a cooperation with S. Maneth (Univ. of Sydney, Australia) will be started. We plan to study the computational complexity of some important problems on tree transducers. These problems have recently been shown to be solvable, but the discovered algorithms are too inefficient to be of practical value.

2.2 Graph transformation

As far as this proposal is concerned, the most interesting recent developments regarding graph transformation are a new type of graph grammar called adaptive star grammar [15] and its associated notion of graph transformation. This work has been done together with researchers from Belgium (N. van Eetvelde and D. Janssens, Univ. of Antwerp) and Germany (B. Hoffmann, Univ. of Bremen, and M. Minas, Univ. of München). Adaptive star grammars are a theoretically appealing concept motivated by – but by no means restricted to – software refactoring applications. Roughly speaking, software refactoring is the semanticspreserving transformation of object-oriented programs. Such transformations are frequently needed in object-oriented software development and are often manually performed, which is both time-consuming and error-prone. By representing the structural relationships within an object-oriented program as a graph (generated by an adaptive star grammar), refactorings can be formalized as graph transformations and integrated in software-development environments. Adaptive star grammars will be part of the graph-based programming environment Diaplan mentioned in earlier applications, whose development continues.

2.3 Picture generation

The contributions to the area of picture generation will benefit from the framework of tree-based picture generation and, as far as implementations are concerned, extend the system Treebag [23]. In addition to a continued investigation of open questions in the field, one of the major goals is to establish an advanced grammatical concept for the generation of virtual realities. Rather than generating single pictures, these grammars generate so-called progressing scenes – complex three-dimensional scenes that can change over time. The idea is that a potentially large number of grammatical devices of different types cooperate in order to create a scene. The individual grammar instances may concurrently perform derivation steps, thus progressing the scene. To date, L-systems with turtle geometry interpretation [16,Chap. 2] are the only theoretical model for picture generation which is widely recognized in practice. The long-term aim of this work is to establish progressing scene grammars as a more powerful tree-based alternative. As a first step, since no other resources have been available, two master thesis projects that started in spring have been devoted to a formalization and a prototypical implementation of this concept. Papers submitted to conferences and journals (and, if funding is available, a PhD project) will follow.

References

[1] Frank Drewes, Berthold Hoffmann, and Detlef Plump. Hierarchical graph transformation. Journal of Computer and System Sciences 64:249-283, 2002.
[2] Frank Drewes, Hans-Jörg Kreowski, and Denis Lapoire. Criteria to disprove context-freeness of collage languages. Theoretical Computer Science 290:1445-1458, 2003.
[3] Frank Drewes, Berthold Hoffmann, and Mark Minas. Context-exploiting shapes for diagram transformation. Machine GRAPHICS & VISION 12:117-132, 2003.
[4] Frank Drewes, Sigrid Ewert, Renate Klempien-Hinrichs, and Hans-Jörg Kreowski. Computing raster images from grid picture grammars. Journal of Automata, Languages and Combinatorics 8:499-519, 2003.
[5] Frank Drewes, Renate Klempien-Hinrichs, and Hans-Jörg Kreowski. Table-driven and context-sensitive collage languages. Journal of Automata, Languages and Combinatorics 8:5-24, 2003.
[6] Frank Drewes and Joost Engelfriet. Branching synchronization grammars with nested tables. Journal of Computer and System Sciences 68:611-656, 2004.
[7] Frank Drewes, Sigrid Ewert, Johanna Högberg, and Brink van der Merwe, Christine du Toit, Andries P.J. van der Walt. Random Context Tree Grammars and Tree Transducers. South African Computer Journal 34:11-25, 2005.
[8] Frank Drewes and Johanna Högberg. Query Learning of Regular Tree Languages: How to Avoid Dead States. Theory of Computing Systems. To appear.
[9] Frank Drewes, Berthold Hoffmann, and Mark Minas. Constructing shapely nested graph transformations. In H.-J. Kreowski, editor, Proc. Workshop on Applied Graph Transformation, pages 107-118, 2002.
[10] Frank Drewes and Joost Engelfriet. Branching grammars: A generalization of ET0L systems. In Z. Ésik and Z. Fülöp, editors, Proc. Developments in Language Theory (DLT 2003), volume 2710 of Lecture Notes in Computer Science, pages 266-278. Springer, 2003. Full version appeared as [6].
[11] Frank Drewes and Johanna Högberg. Learning a regular tree language from a teacher. In Z. Ésik and Z. Fülöp, editors, Proc. Developments in Language Theory (DLT 2003), volume 2710 of Lecture Notes in Computer Science, pages 279-291. Springer, 2003.
[12] Frank Drewes, Berthold Hoffmann, Raimund Klein, and Mark Minas. Rule-Based Programming with Diaplan. In T. Mens, A. Schürr, G. Taentzer, editors, Proc. Workshop on Graph Based Tools (GraBaTs 2004), volume 127 of Electronic Notes in Theoretical Computer Science, pages 15-26. 2005.
[13] Frank Drewes and Johanna Högberg: Extensions of a MAT Learner for Regular Tree Languages. In M.J. Minock, P. Eklund, H. Lindgren, Proc. 23rd Annual Workshop of the Swedish Artificial Intelligence Society (SAIS 2006), pages 35-44, 2006.
[14] Frank Drewes, Sigrid Ewert, Brink van der Merwe, Christine du Toit, and Andries van der Walt. Bag Tree Grammars. In Z. Dang, O.H. Ibarra, Proc. 10th Intl. Conf. on Developments in Language Theory (DLT 2006), volume 4036 of Lecture Notes in Computer Science. Springer. To appear. Full version available as [21].
[15] Frank Drewes, Berthold Hoffmann, Dirk Janssens, Mark Minas, and Niels Van Eetvelde. Adaptive Star Grammars. In Proc. 3rd International Conference on Graph Transformation (ICGT 2006), Lecture Notes in Computer Science. Springer. To appear.
[16] Frank Drewes. Grammatical Picture Generation – A Tree-Based Approach. Texts in Theoretical Computer Science. An EATCS series. Springer, January 2006. See also the related web page http://www.cs.umu.se/ ~drewes/picgen.
[17] Frank Drewes and Joost Engelfriet. Branching Synchronization Grammars with Nested Tables. Report UMINF 02.22, Umeå University, 2002. Revised version appeared as [6].
[18] Frank Drewes and Johanna Högberg. Learning a Regular Tree Language from a Teacher even more Efficiently. Report UMINF 03.11, Umeå University, 2003. Revised version appeared as [8].
[19] Frank Drewes, Sigrid Ewert, Johanna Högberg, Brink van der Merwe, Christine du Toit, and Andries van der Walt. Random Context Tree Grammars and Tree Transducers. Report UMINF 05.02, Umeå University, 2005. Revised version appeared as [7].
[20] Frank Drewes and Brink van der Merwe. Path Languages of rpc Tree Grammars are Regular. Report UMINF 05.23, Umeå University, 2005.
[21] Frank Drewes, Sigrid Ewert, Johanna Högberg, Brink van der Merwe, Christine du Toit, and Andries van der Walt. Bag Tree Grammars. Report UMINF 06.03, Umeå University, 2006.
[22] Frank Drewes and Heiko Vogler. Learning Deterministically Recognizable Tree Series. Report UMINF 06.27, Umeå University, 2006.
[23] Frank Drewes. Treebag software. See http://www.cs.umu.se/ ~drewes/treebag.