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 relation, a partial preordering on $A$, by $a_1 \leq a_2$ iff there exists $a' \in A$ such that $a_2 = a_1 a'$, and on $B$ as well. The prefix relation turns any cancellative monoid into a partially preordered set.

[See correction below] 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}$.

Correction: the definition of bikernel should be strengthened so that $(a_1,a_2) \in A \times A$ is in the bikernel of $f$ iff $a_1 \leq a_2$ and $f(a_1 a) = f(a_2 a)$ for all $a \in A$.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.