20 citations · 89 across the 26 of their papers we have counts for
34 papers
When is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?
Sebastian Maneth, Helmut Seidl
We consider two natural subclasses of deterministic top-down tree-to-tree transducers, namely, linear and uniform-copying transducers. For both classes we show that it is decidable…
Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers
Paul Gallot, Sebastian Maneth, Keisuke Nakano +1
We present a novel normal form for (total deterministic) macro tree transducers (mtts), called depth proper normal form. If an mtt is in this normal form, then it is guaranteed tha…
Deciding whether an Attributed Translation can be realized by a Top-Down Transducer
Sebastian Maneth, Martin Vu
We prove that for a given partial functional attributed tree transducer with monadic output, it is decidable whether or not an equivalent top-down transducer (with or without look-…
Checking in Polynomial Time whether or not a Regular Tree Language is Deterministic Top-Down
Sebastian Maneth, Helmut Seidl
It is well known that for a given bottom-up tree automaton it can be decided whether or not there exists deterministic top-down tree automaton that recognized the same tree languag…
Characterizing Attributed Tree Translations in Terms of Macro Tree Transducers
Kenji Hashimoto, Sebastian Maneth
It is well known that attributed tree transducers can be equipped with "regular look-around" in order to obtain a more robust class of translations. We present two characterization…
How to decide Functionality of Compositions of Top-Down Tree Transducers
Sebastian Maneth, Helmut Seidl, Martin Vu
We prove that functionality of compositions of top-down tree transducers is decidable by reducing the problem to the functionality of one top-down tree transducer with look-ahead.