A Characterization of the Sets of Hypertrees Generated by Hyperedge-Replacement Graph Grammars |
| |
Authors: | F Drewes |
| |
Affiliation: | (1) Department of Computer Science, University of Bremen P.O. Box 33 04 40, D-28334 Bremen, Germany drewes@informatik.uni-bremen.de, DE |
| |
Abstract: | A characterization of the languages of hypertrees generated by hyperedge-replacement graph grammars is established. The characterization
says that these languages are exactly those described by sets of derivation trees which are output languages of finite-copying
top-down tree transducers. Furthermore, the statement remains valid if the tree transducers are required to generate derivation
trees in which the right-hand sides of productions are hypertrees and the nonterminal hyperedges are at most as large as the
hyperedges in the generated hypertrees. This 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.
Received August 1997, and in final form May 1998. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|