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.
Original language | English |
---|---|
Article number | 106332 |
Journal | Information Processing Letters |
Volume | 180 |
DOIs | |
State | Published - Feb 2023 |
Keywords
- Decidability
- Formal languages
- Macro tree transducers
- Origin equivalence