The question was asked by a Computer Scientist and is closely related to parallel computing. But it is clearly of algebraic nature, so I decided to post it here. 


Let $X$ be a set and $\bar X$ be the union of all Cartesian powers $X^n$.
Let $f$ be a function from $\bar X$ to $X$. We say that $f$ is *inductive* if
there exists a binary operation $F\colon X\times X \to X$ such that for
every $x\_1,...,x\_n \in X$, $n>1$, we have
$f(x\_1,...,x\_n)=F(f(x\_1,...,x\_{n-1}), x\_n)$. If, in addition, $F$ is
associative and $(X,F)$ is a monoid (has the identity element), then $f$
is called *reducible*. For example, if $X$ is the set of all natural
numbers, $f$ is the max function on $\bar X$, then we can take
$F(x,y)=\max(x,y)$. So $f$ is reducible.


We say that $(X,f)$ has an *inductive (resp. reducible) extension* if
there exists a set $Y$ containing $X$ with a function $g$ from $\bar Y$ to $Y$
and a projection function $p: Y\to X$ such that $$p(g(x\_1,...,x\_n))=f(x\_1,...,x\_n)$$ for
all $x\_1,...,x\_n$ in $X$ and $(Y, g)$ is inductive (resp. reducible).


**Question:** 1) What is known about the set of functions $f$ with inductive
(reducible) extensions? 2) In particular, does every function $f$ admit an 
inductive (reducible) extension?



Inductive and reducible functions
I assume that $\bar X$ also contains $\varnothing$ as the Cartesian product of 0 copies of $X$.


Set $Y=\bar X$. If $y\_i=(x\_{i,1},\dots,x\_{i,k\_i})\in X^{k\_i}$ with $i=1,\dots,\ell$, set
$$
 g(y\_1,\dots,y\_\ell)=(x\_{1,1},\dots,x\_{1,k\_1},x\_{2,1},\dots,x\_{2,k\_2},\dots)\in X^{k\_1+k\_2+\dots}\subset Y
$$
(so $g$ is simply the concatenation). Clearly, $g$ is reducible (with $F$ being a binary concatenation; we get a monoid, since we added $\varnothing$). Finally, for $y=(x\_1,\dots,x\_k)$ define 
$$
 p(y)=f(x\_1,\dots,x\_k)
$$
(we can define $p(\varnothing)$ arbitrarily; on the other elements, $p$ does all the job).
Thus we obtain a reducible extension of $f$.


So, each function $f$ indeed has a reducible extension.


