The copying power of one-state tree transducers


Engelfriet, Joost and Skyum, Sven (1982) The copying power of one-state tree transducers. Journal of computer and system sciences, 25 (3). pp. 418-435. ISSN 0022-0000

open access
Abstract:One-state deterministic top-down tree transducers (or, tree homomorphisms) cannot handle "prime copying," i.e., their class of output (string) languages is not closed under the operation L → {$(w$)f(n)  w ε L, f(n) ≥ 1}, where f is any integer function whose range contains numbers with arbitrarily large prime factors (such as a polynomial). The exact amount of nonclosure under these copying operations is established for several classes of input (tree) languages. These results are relevant to the extended definable (or, restricted parallel level) languages, to the syntax-directed translation of context-free languages, and to the tree transducer hierarchy.

Item Type:Article
Copyright:© 1982 Elsevier Science
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page