Abstract
Original language | English |
---|---|
Pages (from-to) | 418-435 |
Journal | Journal of computer and system sciences |
Volume | 25 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1982 |
Fingerprint
Cite this
}
The copying power of one-state tree transducers. / Engelfriet, Joost; Skyum, Sven.
In: Journal of computer and system sciences, Vol. 25, No. 3, 1982, p. 418-435.Research output: Contribution to journal › Article › Academic › peer-review
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) 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.
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) 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.
U2 - 10.1016/0022-0000(82)90019-8
DO - 10.1016/0022-0000(82)90019-8
M3 - Article
VL - 25
SP - 418
EP - 435
JO - Journal of computer and system sciences
JF - Journal of computer and system sciences
SN - 0022-0000
IS - 3
ER -