Skip to main content
4 of 9
edited tags
Emil Jeřábek
  • 47.4k
  • 4
  • 150
  • 209

What is the real name of this relation and operation on a particular set of maps between cancellative monoids?

Let $A,B$ be cancellative monoids and define a transducer as a map $f\colon A \rightarrow B$ such that $f(1)=1$ and for all $a_1 ,a_2 \in A$, there exists a $b \in B$ such that $f(a_1 a_2)=f(a_1) b$. Define the prefix ordering on $A,B$ by $a_1 \leq a_2$ iff there exists $a' \in A$ such that $a_2 = a_1 a'$. Define the same notion of prefix ordering on $B$. (Any cancellative monoid can be made into a partially ordered set this way.)

Define the bikernel of a transducer $f\colon A\rightarrow B$ to be $\{(a_1,a_2) \colon a_1,a_2 \in A \wedge a_1 \leq a_2 \wedge f(a_1)=f(a_2)\}$. Define a prefix chain in $A$ to be a subset of $A$ that is a totally ordered set under the prefix ordering. Define $A^2_\leq = \{ (a_1,a_2) : a_1,a_2 \in A \land a_2=a_1 a' \mathrm{\ for\ some\ } a' \in A\}$ which is also the explicit set-theoretic definition of the prefix relation. Define a link of a finite chain $\bar a = (a_0, a_1, \ldots, a_n)$ to be a pair $(a_{i-1},a_i)$ for $i=1,\ldots,n$. Define the differential $d f$ of a transducer $f\colon A \rightarrow B$ to be the function $d f\colon A^2_\leq \rightarrow B$ such that $b=d f(a_1,a_2)$ satisfies $f(a_1)b=f(a_2)$. By cancellative property, this $b$ is unique, so the differential is a well-defined function.

Let $f,g\colon A \rightarrow B$ be two transducers such that for all $a\in A$, there exists a finite chain $\bar a = (a_0,\ldots,a_n)$ in $A$ such that $a_0=1$, $a_n=a$, and every link $(a_{i-1},a_i)$ of $\bar a$ is either in the bikernel of $f$ or the bikernel of $g$. Define the following "independent sum relation for $f,g$" as the set $I_{f,g}$ of all pairs $(a,b) \in A \times B$ such that there exists a finite chain $\bar a$ in $A$ such that $a_0=1$, $a_n=a$, every link of $\bar a$ is either in the bikernel of $f$ or the bikernel of $g$, and $b=d f(a_0,a_1) d g(a_0,a_1) d f(a_1,a_2) d g(a_1,a_2) \cdots d f(a_{n-1},a_n) d g(a_{n-1},a_n)$. If $I_{f,g}$ is in fact a function from $A$ to $B$ (this is a form of path independence) then define $f,g$ to be independently summable and define $I_{f,g}\colon A \rightarrow B$ to be the independent sum of $f$ and $g$.

If it has been published before (???) I am looking for the name of this relation "independently summable" and the operation "independent sum". The concept can be extended to arbitrarily many terms (all links in the chain must be in all or all but one of the bikernels of the terms). I believe there is a nontrivial decomposition theorem for transducers that allows a transducer (with some conditions) to be written as an independent sum of terms; the operation is commutative, associative, and independent of grouping; and the operation of independent sum distributes over composition with a transducer on the left or right sides, in other words $I_{f,g} h = I_{f h, g h}$ and $h I_{f,g}=I_{h f, h g}$. Has any of this been published? Where can I find more information about this subject?

On another note, has this category been studied? The category of transducers consists of objects: triples $(A,f,B)$ such that $A,B$ are cancellative monoids, $f\colon A\rightarrow B$ is a transducer; for objects $(A_1,f_1,B_1)$ and $(A_2,f_2,B_2)$ there is an arrow or morphism $(\phi,\theta)$ when $\phi \colon A_1 \rightarrow A_2$ and $\theta \colon B_1 \rightarrow B_2$ are homomorphisms of cancellative monoids that make the diagram $(f_1,f_2,\phi,\theta)$ commutative.