This thread is about the concept of synchronizability. It's a concept I tried to formalize in its most general sense but without success. The goal of this thread is therefore to try to formalize it in its most general sense : I don't know if this is legit to ask that there, but I didn't find anything against that on meta.
Motivation: In logic or computer science, the concept of substitution is extensively used. To fix notations, let $A$ be some set of generators (say, an alphabet, finite or not), and let $M(A)$ be the free monoid over $A$ with concatenation as binary law and the empty word $(-)$ as neutral element. Define an elementary substitution to be any map $A$ to $M(A)$ with a unique non fixed points. If $A = \{a,b,c, \ldots\}$ write $a \rightarrow bcd, d \rightarrow a$ the map that substitutes simultaneously $bcd$ to $a$ and $a$ to $d$ and fix all the other points.
We define the action of any substitution on $M(A)$ canonically, that is, by substituting simultaneously the letter of the word by the non fixed point image of the elementary substitutions. Example: Let $a \rightarrow b, b\rightarrow c$ be the substitution acting on $abc$, then the resulting word is nothing else than $bcc$
Note that we could also make sense of composition of elementary substitutions, which is nothing else than a successive action. Example: Let $b \rightarrow c \circ a\rightarrow b$ be the successive action of $a \rightarrow b$ and $b\rightarrow c$ on $abc$, then the result is $ccc$. (First apply $a\rightarrow b$ and then $b\rightarrow c$. Note that $a\rightarrow b \circ b\rightarrow c$ gives $bcc$, which is the same thing as its simultaneous substitution)
Notice that the simultaneous action is different from the succesive action, and that the successive action does not necessarily commutes. We want to make sense of the fact that, sometimes, the successive action of some elementary substitution coincides with its simultaneous action (obviously, this would only hold on a given word or set of words).
We define the following concepts in this respect. A finite sequence $(f_n)_n$ of elementary substitutions is said to be compatible iff the non fixed points of all $f_n$ are disjoints. Let $f = f_1, f_2, \ldots f_n$ be the substitution associated with such compatible sequence $(f_n)_n$. We say that the sequence $(f_n)_n$ is synchronizable on a word $w$ iff $f(w) = f_n \circ f_{n-1} \circ \ldots \circ f_1(w)$. That is, if the simultaneous action of $f$ on $w$ gives the same result as its successive substitution (in the order of the sequence) on $w$.
Note that it is not necessarily that the elementary substitutions $f_n$ commutes pairwise for them to be synchronizable on some word (cf my example above). It looks like that a sufficient condition for a compatible sequence $(f_n)_n$ to be synchronizable is that, for all $m < n$ the image of $f_m$ is not contained in the domain of points not fixed by $f_n$ for $n >m$. Can we say more ? (Clearly, if $(f_n)_n$ is a compatible sequence such that all elementary substitution pairwise commutes on $w$, then it is synchronizable on $w$)
Now, let me add that there are many more example where some ``transformations'' are not synchronizable.
in probability theory, there's a huge difference between picking some balls simultaneously or successively,
in Chemistry (or say, cooking), it is clear that adding ingredients successively is not at all the same thing as adding them instantaneously,
The same happens in quantum mechanics when we speak about measuring a state,
$\ldots$
Does anyone have any idea about how to formalize this concept of synchronizability in its most general sense? That is, such that it encompasses many example and not only substitutions?
EDIT: Let $f$ be some substitution. We say that $f$ is desynchronisable on a word $w$ if there exists a compatible sequence of elementary substitutions $(f_n)_n$, such that $f(w) = f_n \circ \ldots \circ f_1(w)$. Example: Let $w = ab$ and $f = a \rightarrow b, b \rightarrow a$, then clearly $f(w) = ba$ is non desynchronisable. Given a word $w$, what can we say about $Syn(w) = \{ (f_n)_n$ such that $(f_n)_n$ is synchronisable on $w \}$, $\neg Syn(w) = \{ (f_n)_n$ such that $(f_n)_n$ is non synchronizable on $w\}$, $Des(w)=\{ f$ such that $f$ is desynchronisable on $w\}$ and $\neg Des(w)=\{ f$ such that $f$ is not desynchronisable on $w\}$ ? (Clearly, the permutations, but the identity, of a word $w$ belongs to $\neg Des(w)$)
EDIT2: Call elementary map, any $f : X \rightarrow Y$ such that $X \subset Y$ and that $f$ admits at most one non fixed point. Let $Sets$ be the category of sets, and let $\alpha > 0$ be some ordinal seen as a poset category, with $0$ as initial object. Let $F : \alpha \rightarrow Sets$ be a diagram such that:
1) $F(0) = X$,
2) $F$ takes all sucessor morphisms to an elementary morphism in Sets,
3) $F$ is continuous in the sense of http://ncatlab.org/nlab/show/transfinite+composition
We say that a map $f : X \rightarrow colim F$ that is non constant only on a subset $X'$ of $X$ of cardinality $|\alpha|$ is desynchronizable if it is a transfinite morphism of the diagram $F$ in the above sense. This seems to be a way to define desynchronizability in the case of endotransformations (substitutions could work if we see them as maps from $M(A)$ to itself that are elementary on $A$ I suppose ?)
