Tree transducers, L systems, and two-way machines

Joost Engelfriet, Grzegorz Rozenberg, Giora Slutzki

    Research output: Contribution to journalArticleAcademic

    129 Citations (Scopus)
    105 Downloads (Pure)


    A relationship between parallel rewriting systems and two-way machines is investigated. Restrictions on the “copying power” of these devices endow them with rich structuring and give insight into the issues of determinism, parallelism, and copying. Among the parallel rewriting systems considered are the top-down tree transducer; the generalized syntax-directed translation scheme and the ETOL system, and among the two-way machines are the tree-walking automaton, the two-way finite-state transducer, and (generalizations of) the one-way checking stack automaton. The. relationship of these devices to macro grammars is also considered. An effort is made .to provide a systematic survey of a number of existing results.
    Original languageEnglish
    Pages (from-to)150-202
    JournalJournal of computer and system sciences
    Issue number2
    Publication statusPublished - 1980


    Dive into the research topics of 'Tree transducers, L systems, and two-way machines'. Together they form a unique fingerprint.

    Cite this