W-transformations -- definitions

We will consider a class called finite window transformations $\ T:C^\mathbb Z\rightarrow C^\mathbb Z\ $ defined a paragraph below; $\ \mathbb Z\ $ is the ring of integers, and $\ C\ $ stands for an arbitrary finite set of cardinality $\ |C|>1$,   where $\ C\ $ is called a set of colors.

Let any non-empty finite set $\ W\subseteq \mathbb Z\ $ be called a window; set its diameter as

$$\ \delta(W):=1+\max W-\min W$$

Mappings $\ F: C^W\rightarrow C\ $ are called $W$-functionals or simply functionals. Define the induced transformation $\ T_F:C^\mathbb Z\rightarrow C^\mathbb Z\ $ by formula:

$$ (T_F(f))(p)\ :=\ F((f\circ S_p)|W)$$

for every $\ f\in C^\mathbb Z\ $ (i.e. $\ f:\mathbb Z\rightarrow C$)   and $\ p\in \mathbb Z$,   where the shift $\ S_p :\mathbb Z\rightarrow \mathbb Z\ $ is given by:

$$ \forall_{z\in\mathbb Z}\quad S_p(z) := p+z $$

That's what finite window transformations are, or $W$-transformations for any particular window $\ W$.

M.Nasu's Theorem

The following indecomposability theorem was proved by M.Nasu:

THEOREM (M.Nasu)   Let $\ C\ $ be an arbitrary finite set such that $\ |C|>1$.   Let $\ d\ $ be an arbitrary natural number ($\ n=1\ 2\ \ldots$). Then there exists a $\ W$-transformation $\ T\ $ of diameter $\ \delta(W)=d\ $ such that there does not exist any finite sequence of window transformations $\ T_1\ldots T_n\ $ such that

$$ T\ =\ T_n\circ\ldots\circ T_1$$

and the diameters of transformations $\ T_k\ $ are smaller than $\ d\ $ for every $\ k=1\ldots n\ $ and $\ n=1\ 2\ \ldots$.

Questions--concept: allow for memory.

Let's continue to assume that $\ C\ $ is an arbitrary finite set (of colors) such that $\ |C|>1$. Let $\ D:=A\times C\ $ where $\ A\ $ is another finite set. We obtain an open problem below for each $\ A\ $ such that

$$ 2\ \le\ |A|\ <\ 2\times |C|$$

Consider the cartesian projection $\ \pi_C: D\rightarrow C$.   First let's define processing of an image transformation $\ T:C^{\mathbb Z}\rightarrow C^{\mathbb Z}$.   It is a sequence $\ T_k:D^{\mathbb Z}\rightarrow D^{\mathbb Z}\ $ for a natural $\ n$,   and $\ k=1\ldots n$,   such that for every $\ f:\mathbb Z\rightarrow C\ $ and $\ g:\mathbb Z\rightarrow D\ $ subjected to $\ \pi_C\circ g = f\ $ the following holds:

$$ \pi_C\circ ((T_n\circ\ldots\circ T_1)(g))\ =\ T(f)$$

PROBLEM   Let $\ d\ $ be an arbitrary natural number $\ 1\ 2\ \ldots$. Show that there exists a $\ W$-transformation $ T:C^{\mathbb Z}\rightarrow C^{\mathbb Z}\ $ of diameter $\ \delta(W)=d\ $ such that there does not exist any sequence of window transformations $\ T_k:D^{\mathbb Z}\rightarrow D^{\mathbb Z}\ $ which processes transformation $\ T$, with all diameters of the mentioned sequence transformations smaller than $\ d$.

  • $\begingroup$ I've formulated and proved the existence of the decomposition (in an extra strong sense) when $\ |A| \ge 2\times|C|\ $ in the "digital" case, when the cardinality of $\ C\ $ is a power of $\ 2$. The "non-digital" case may be fun but is not too important to computers. (My theorem was simple). The two theorems, Nasu's theorem (hard) and my own, set the scope of the problem. $\endgroup$ – Włodzimierz Holsztyński Sep 23 '13 at 2:34
  • $\begingroup$ I tried to bend my problem close toward the Nasu's theorem. Thus I gave up on a more conceptual and complete formulation. The above formulation is already a bit long. $\endgroup$ – Włodzimierz Holsztyński Sep 23 '13 at 2:41
  • $\begingroup$ Why should this be true? Doesn't the memory mean you can hold both the values of the current location and some neighboring values in the current location? It seems like this should be false for $|C|=2, |A|=2, d\gt 1$. $\endgroup$ – Douglas Zare Sep 23 '13 at 5:14
  • $\begingroup$ First, the case $\ d=2\ $ holds trivially (as you get only windows of size 1 for your output; each pixel is computed independently as in an associative memory modulo total shifts, which here are harmless). More about the non-trivial case in a next comment. $\endgroup$ – Włodzimierz Holsztyński Sep 23 '13 at 16:12
  • $\begingroup$ Decomposability for |A|=|C| is the hardest to prove, the easiest the disprove. I still conjecture that it holds. Thus decomposability would be the easiest to prove here, and the case of |A|=|C|=2 and d=3 would be the simplest. I doubt it. Decomposing CARRY would already be a challenge. Actually possibly the hardest indecomposable example would be provided by the periodic maximal shift registers. Yes, there is extra memory provided here but most likely not enough. $\endgroup$ – Włodzimierz Holsztyński Sep 23 '13 at 16:19

Your Answer

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

Browse other questions tagged or ask your own question.