The copying power of one-state tree transducers

Joost Engelfriet; Sven Skyum

doi:10.1016/0022-0000(82)90019-8

The copying power of one-state tree transducers

Joost Engelfriet, Sven Skyum

Research output: Contribution to journal › Article › Academic › peer-review

5 Citations (Scopus)

46 Downloads (Pure)

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.

Original language	English
Pages (from-to)	418-435
Journal	Journal of computer and system sciences
Volume	25
Issue number	3
DOIs	https://doi.org/10.1016/0022-0000(82)90019-8
Publication status	Published - 1982

Access to Document

10.1016/0022-0000(82)90019-8Licence: Other

Engelfriet82copying
open
Final published version, 1.14 MBLicence: Other

Fingerprint Dive into the research topics of 'The copying power of one-state tree transducers'. Together they form a unique fingerprint.

Cite this

Engelfriet, J., & Skyum, S. (1982). The copying power of one-state tree transducers. Journal of computer and system sciences, 25(3), 418-435. https://doi.org/10.1016/0022-0000(82)90019-8

@article{97d07b9bcf374452bac1dda2ae5ca02e,

title = "The copying power of one-state tree transducers",

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.",

author = "Joost Engelfriet and Sven Skyum",

year = "1982",

doi = "10.1016/0022-0000(82)90019-8",

language = "English",

volume = "25",

pages = "418--435",

journal = "Journal of computer and system sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "3",

}

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 -