Deciding origin equivalence of weakly self-nesting macro tree transducers

Sebastian Maneth, Helmut Seidl

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number106332
JournalInformation Processing Letters
Volume180
DOIs
StatePublished - Feb 2023

Keywords

  • Decidability
  • Formal languages
  • Macro tree transducers
  • Origin equivalence

Fingerprint

Dive into the research topics of 'Deciding origin equivalence of weakly self-nesting macro tree transducers'. Together they form a unique fingerprint.

Cite this