|
Abstract : |
Abstract. A characterization of the sets of hypertrees generated by hyperedgereplacement graph grammars is given. The characterization says that these sets are exactly those which have the form val(T), where T, a set of terms over hyperedgereplacement operations, is the output language of a finite-copying top-down tree transducer. Furthermore, the terms in T may be required to consist of hyperedgereplacement operations whose underlying hypergraphs are hypertrees. The result is closely related to a similar characterization that was obtained for the case of string graphs by Engelfriet and Heyker some years ago. In fact, the results of this paper also yield a new proof for the characterization by Engelfriet and Heyker. 1, |
