The copying power of one-state tree transducers

TY - JOUR

T1 - The copying power of one-state tree transducers

AU - Engelfriet, Joost

AU - Skyum, Sven

PY - 1982

Y1 - 1982

N2 - 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) short parallel w ε L, f(n) greater-or-equal, slanted 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.

AB - 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) short parallel w ε L, f(n) greater-or-equal, slanted 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.

U2 - 10.1016/0022-0000(82)90019-8

DO - 10.1016/0022-0000(82)90019-8

M3 - Journal article

SN - 0022-0000

VL - 25

SP - 418

EP - 435

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -