Tags:Infinitary term rewriting, Rational terms, Term rewriting systems and Top-down tree transducers
Abstract:
In the basic formalism of term rewriting, targets of rewriting are finite terms. On the other hand, in infinitary rewriting, we may consider rewriting of (possibly) infinite terms. Top-down tree transducers, as well as term rewriting, usually deal with transformations of finite terms; we can naturally consider transformations for infinitary terms. We discuss preservation of rationality by top-down tree transducers, namely the problem whether infinite terms reachable by top-down tree transducers from rational terms are rational.
Preservation of Rationality in Infinitary Rewriting by Top-down Tree Transducers