English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We characterize regular string transductions as programs in a linear$\lambda$-calculus with additives. One direction of this equivalence is provedby encoding copyless streaming string transducers (SSTs), which compute regularfunctions, into our $\lambda$-calculus. For the converse, we consider acategorical framework for defining automata and transducers over words, whichallows us to relate register updates in SSTs to the semantics of the linear$\lambda$-calculus in a suitable monoidal closed category. To illustrate therelevance of monoidal closure to automata theory, we also leverage this notionto give abstract generalizations of the arguments showing that copyless SSTsmay be determinized and that the composition of two regular functions may beimplemented by a copyless SST. Our main result is then generalized from stringsto trees using a similar approach. In doing so, we exhibit a connection betweena feature of streaming tree transducers and the multiplicative/additivedistinction of linear logic.  Keywords: MSO transductions, implicit complexity, Dialectica categories,Church encodings

Implicit automata in typed $\lambda$-calculi II: streaming transducers vs categorical semantics