Implicit automata in λ-calculi III: affine planar string-to-string functions

Cécilia Pradic, Ian Price

We prove a characterization of first-order string-to-string transduction via $\lambda$-terms typed in non-commutative affine logic that compute with Church encoding, extending the analog…