Abstract
We consider a notion of origin for deterministic macro tree transducers with look-ahead which records for each output node, the corresponding input node for which a rule-application generated that output node. With respect to this natural notion, we show that “origin equivalence” is decidable — whenever the transducers are weakly self-nesting. The latter means that whenever two nested calls on the same input node occur, then there must be at least one other node (a terminal output node or a call on another input node) in between these nested calls. Besides origin equivalence we are also able to decide “origin injectivity” for such transducers.
Originalsprache | Englisch |
---|---|
Aufsatznummer | 106332 |
Fachzeitschrift | Information Processing Letters |
Jahrgang | 180 |
DOIs | |
Publikationsstatus | Veröffentlicht - Feb. 2023 |