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?