The copying power of one-state tree transducers

Joost Engelfriet, Sven Skyum

    Research output: Contribution to journalArticleAcademicpeer-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 languageEnglish
    Pages (from-to)418-435
    JournalJournal of computer and system sciences
    Volume25
    Issue number3
    DOIs
    Publication statusPublished - 1982

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

  • Cite this