In formal language theory, the notion of regularity is particularly robust: logic, automata, and algebra are equivalent ways to express regularity. As an example, regular word or tree languages are equivalently described by monadic second order (MSO) formulas, finite-state automata, and syntactic congruences, and this kind of correspondence extends to more complex objects, like infinite word or trace languages. This thesis aims at (1) identifying robust classes of transducers that go beyond regular transductions (equivalently, 2way or MSO transductions) by adding provenance information, and (2) studying resource problems for transductions.