TCS / Research / Publications / A Tree Expansion Formalism for Generative String Rewriting
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

A Tree Expansion Formalism for Generative String Rewriting


Eero Lassila. A tree expansion formalism for generative string rewriting. Technical Report B20, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, June 2001.


An abstract generative string rewriting device is introduced for modeling such practical program generation and optimization tools as macro processors. The novel device is called a monosystem, and it differs from such classical abstract generative devices as Chomsky grammars (which have more applications in program analysis than in program generation) by being able to operate on an infinite alphabet and by being sensitive to an unbounded two-sided context. The infinite alphabet makes it conceptually simple to deal with structured symbols (such as macro calls), and the unbounded context-sensitivity promotes optimization. An extension (called a trisystem) of the basic monosystem model is capable of emulating both type-1 Chomsky grammars and a variety of Lindenmayer systems. A monosystem divides into a rule base and a separate control mechanism. The whole rule base is represented as a single function called a letter-refiner, which is capable of replacing any symbol occurrence in any context with an appropriate new substring. Since only one symbol occurrence is thus rewritten at a time, it is natural to record the rewriting history in a tree form. The rewriting context for each tree leaf is extracted from some cross section of the same tree. The actual cross section is determined by a function called a belt-selector, which is the single user-adjustable parameter of the control mechanism. The central problem with monosystems is to guarantee that the output has the intended semantics. If nothing else is known about the letter-refiner than that it is semantics-preserving, the belt-selector must not allow parallelism (and more specifically, the rewriting context of any tree leaf must equal the tree frontier, that is, the set of all the contemporary leaves). When the letter-refiner fulfills a sufficiently strong additional constraint, synchronous and even asynchronous parallelism become possible. Moreover, it then becomes possible to switch between sequential and parallel rewriting (and even between various subtypes of either one), without any need to modify the letter-refiner. These switches may change the structure but not the semantics of the output. This preliminary report is best seen as a tutorial. However, a self-contained formalization of the monosystem model and its properties is included as a set of appendices. As yet, the main emphasis is on definitions rather than on theorems, and all proofs are accordingly omitted.


generative string rewriting

Suggested BibTeX entry:

    address = {Espoo, Finland},
    author = {Eero Lassila},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {June},
    number = {B20},
    pages = {70},
    title = {A Tree Expansion Formalism for Generative String Rewriting},
    type = {Technical Report},
    year = {2001},

PostScript (3 MB)
GZipped PostScript (1 MB)
PDF (656 kB)

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.