Two-dimensional transducers

Abstract

We define a bicategory $2TDX$ whose 1-cells provide a categorification of transducers, computational devices extending finite-state automata with output capabilities. This bicategory is a mathematically interesting object: its objects are categories $\mathcal{A},\mathcal{B},\dots$ and its 1-cells $(\mathcal{Q},t):\mathcal{A}\to \mathcal{B}$ consist of a category $\mathcal{Q}$ of `states', and a profunctor $$t:\mathcal{A}\times {\mathcal{Q}}^{\text{op}}\times \mathcal{Q}\times ({\mathcal{B}}^{\ast }{)}^{\text{op}}\to \mathbf{Set}$$ where ${\mathcal{B}}^{\ast }$ denotes the free monoidal category over $\mathcal{B}$. Extending $t$ to ${\mathcal{A}}^{\ast }$ in a canonical way, to each `word' $\underline{a}$ in ${\mathcal{A}}^{\ast }$ one attaches an endoprofunctor over the category $\mathcal{Q}$ of states, enriched over presheaves on ${\mathcal{B}}^{\ast }$. We discuss a number of other characterizations of the hom-category $2TDX(\mathcal{A},\mathcal{B})$; we establish a Kleisli-like universal property for $2TDX(\mathcal{A},\mathcal{B})$ and explore the connection of $2TDX$ to other bicategories of computational models, such as Bob Walters' bicategory of `circuits'; it is convenient to regard $2TDX$ as the loose bicategory of a double category $\mathbb{D}\mathbf{TDX}$: the bicategory (resp., double category) of profunctors is naturally contained in the bicategory (resp., double category) $2TDX$ (resp., $\mathbb{D}\mathbf{TDX}$); we study the completeness and cocompleteness properties of $\mathbb{D}\mathbf{TDX}$, the existence of companions and conjoints, and we sketch how monads, adjunctions, and other structures/properties that naturally arise from the definition work in $\mathbb{D}\mathbf{TDX}$.

Dedicated to Bob Paré, on the occasion of his 80th birthday