  We propose to use Church encodings in typed lambda-calculi as the basis for
an automata-theoretic counterpart of implicit computational complexity, in the
same way that monadic second-order logic provides a counterpart to descriptive
complexity. Specifically, we look at transductions i.e. string-to-string (or
tree-to-tree) functions - in particular those with superlinear growth, such as
polyregular functions, HDT0L transductions and S\'enizergues's "k-computable
mappings".
  Our first results towards this aim consist showing the inclusion of some
transduction classes in some classes defined by lambda-calculi. In particular,
this sheds light on a basic open question on the expressivity of the simply
typed lambda-calculus. We also encode regular functions (and, by changing the
type of programs considered, we get a larger subclass of polyregular functions)
in the elementary affine lambda-calculus, a variant of linear logic originally
designed for implicit computational complexity.
