The copying power of one-state tree transducers

Joost Engelfriet, Sven Skyum

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)
    62 Downloads (Pure)


    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 languageEnglish
    Pages (from-to)418-435
    JournalJournal of computer and system sciences
    Issue number3
    Publication statusPublished - 1982


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

    Cite this