Zegel Leiden University
Theoretical Computer Science		 Toren Academiegebouw
Theoretische Informatica Club
* index
* Universiteit Leiden
* Leiden Institute for Advanced Computer Science
* Theoretical Computer Science

Schema 2001

5 July Hendrik Jan Hoogeboom Context-Free Valence Grammars -- Revisited
5 July Sebastian Maneth Hierarchies of String Languages Generated by Deterministic Tree Transducers

Hendrik Jan Hoogeboom: Context-Free Valence Grammars -- Revisited

Context-free valence languages (over Z^k) are shown to be codings of the intersection of a context-free language and a blind k-counter language. This AFL-style characterization allows one to infer some of the properties of the family of valence languages, in particular the lambda-free normal form proved by Fernau and Stiebe.

Sebastian Maneth: Hierarchies of String Languages Generated by Deterministic Tree Transducers

The EDT0L-hierarchy is obtained by iterating the control of EDT0L systems (the deterministic variant of ET0L systems). It is shown that this hierarchy is proper at every step, and that there are context-free languages not in the EDT0L-hierarchy. The proof is based on a bridge theorem which can also be used to prove that the composition of attribute grammars and of macro tree transducers yield proper hierarchies.
2001 (MtB)