Deciding origin equivalence of weakly self-nesting macro tree transducers

Sebastian Maneth, Helmut Seidl

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

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.

OriginalspracheEnglisch
Aufsatznummer106332
FachzeitschriftInformation Processing Letters
Jahrgang180
DOIs
PublikationsstatusVeröffentlicht - Feb. 2023

Fingerprint

Untersuchen Sie die Forschungsthemen von „Deciding origin equivalence of weakly self-nesting macro tree transducers“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren