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 ?)

  • $\begingroup$ You might be interested in the Henkin quantifier (see en.wikipedia.org/wiki/Branching_quantifier), which is an instance of simultaneity in first-order logic: for every $a$ there is $b$, and simultaneously, for every $c$ there is $d$ (that is, depending only on $c$), such that $\phi(a,b,c,d)$. $\endgroup$ – Joel David Hamkins Oct 29 '14 at 12:01
  • $\begingroup$ Sounds interesting, so you might be able to speak about simultaneous transformation by formulating a concept of "simultaneous function", which would be parallel functions respecting some conditions (the same I described about fixed points I suppose). $\endgroup$ – sure Oct 29 '14 at 12:23
  • $\begingroup$ More generally, Jouko Vaananen and others have done extensive work on "(In)Dependence Logic" (see arxiv.org/pdf/1305.5948v1.pdf) which may interest you. $\endgroup$ – Noah Schweber Oct 29 '14 at 17:10

This doesn't really answer your question, but maybe it will help.

  1. I find it slightly unintuitive that your concept of synchronizability of substitutions applies to sequences of substitutions rather than sets of substitutions. (I would have guessed the concept might be some sequence, or perhaps every sequence, is equivalent to the simultaneous substitution. Or it could be even be that the different sequences are all equivalent, but you don't allow simultaneous substitutions. Or just have a preorder on substitutions (so arbitrary subsets can fire simultaneously).)

  2. Perhaps another example in the spirit of the question is the "hitman party." It starts with a set of hitmen meeting at a house to have a party. Each hitman kills all the people at the party who are on his hit list and then phones a bunch of his hitman friends to come join the party. Then he gets drunk and doesn't kill anyone more but stays to enjoy the party. You may also consider that hitmen could stab the people on their list one by one, or they could all always use the same trick of getting everyone on their list to go look at the art in the bathroom and then detonating a grenade in the bathroom. (And there are further issues to settle, like whether two hitmen might stab each other, or get each other to go look at the art in the bathroom.) A general area you might look at is the study of concurrency in computer science.

  • $\begingroup$ Your 1. is a pretty good point. I guess its indeed better to say that a set of compatible elementary substitutions is synchronizable if there exists some way to compose them (and all of them) such that it gives the same result as its associated simultaneous substitution. The concept of desynchronization sounds more logical then. Can I edit the thread and change this everywhere, or is it better to do an answer ? $\endgroup$ – sure Oct 31 '14 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.