数理解析研究所講究録
第 1744 巻 2011 年 137-143

137

2010 年度冬の LA シンポジウム [27]Local Composition of Cellular Automata via Hit-or-MissTransform
Mitsuhiko Fujio *Abstract$\sigma_{c}:V\ni varrow v^{-1}c\cap W\in 2^{W}$

The notion of local composition of cellular automata
was introduced in [1] as an operator over local
transition rules compatible with the composition of
global transitions. A Mathematical morphologicalinterpretation of local composition was given in [2]in terms of excitation patterns of local transition
rules. In this article, by going ahead Mathematicalmorphological analysis, we describe the local composition via hit-or-miss transform which is known
as a pattem detecting tool in Mathematical morphology [9, 11].

$\mathcal{L}0$on$=\{c\in 2^{VW}|\sigma_{c}^{-1}(\mathfrak{M})\in L\}$

,

where
and $W$ are respectively the supports ofthe composed rules and .
In the previous work [2], to clarify this description, the author rewrote the condition(SM)in terms of Mathematical morphological (MMfor short) operators concerning the mapping.
Namely, for any local pattem on $VOW$ ,
$V$

$C$

$\mathfrak{M}$$\sigma_{c}^{-1}$

$\in$

$L$

$\sigma_{c}$$c$$\sigma_{c}^{-1}(\mathfrak{M})\in,C\Leftrightarrow$$\exists L\in \mathcal{L}$1assuch that,$\delta_{{}^{t}\sigma_{e}}(L)\subseteq \mathfrak{M}\subseteq\epsilon_{t}\sigma_{c}(L)$

where
and
respectively denote thedilation and the erosion of by the transpositionof the local mapping
regarded as a correspondence. A general frame-work of MM analysis
for correspondences will be given in \S 3.
In this article, we give a more direct interpretaby using hit-or-miss transform astion offollows. The hit-or-miss transform of a set by apair of sets $B$ and $B’$ is defined byIntroduction$\delta_{{}^{t}\sigma_{c}}(L)$$\xi t\sigma_{c}(L)$$L$

A cellular automaton (CA for short) is a discrete
dynamical system characterized by its locality andhomogenuity. In fact, for every CA, its transition
funciton over configurations is defined by a local
transition
so as to be translation invariant.
Such a formalism of CA requires a group structure on the set of sites on which configurations aie
defined. CA thus defined are completely deter(1)O$ $(B, B’)=\epsilon_{B}(A)\cap\epsilon_{B’}(A^{C})$ .
mined by their local transition rules. In particular,
any properties of CA , in principle, should be de- The resulting set $AO(B, B’)$ consists of those points
scribed in terms of their local transition rules.
for which $B$ fits in the forground and $B’$ fits in theIn [1], the author introduced the notion of local backgroound . Consequently, if $B\cap B’\neq\emptyset$ thencompositon of local transition mles and showed that A $O*(B, B’)=\emptyset$ . By using hit-or-miss transform,
the transition function corresponding to the local$W-$
can be rewritten ascomposition coincides with the composition of the $M)$ and hence we havetransition funcitons corresponding to the composed.
local transition rules (more precisely, see Theorem
3 . The description of local composition for 10cal transition rules
given in [1] is in a This means that the local compositionandEM conconotative form for local patterns on the com- sists of those local patterns for which the neighposed support $VOW$ by using of the mapping bourhood at each point in $W$ , both positively and*Deptartment of Systems Design and Informatics, negatively, fits some pattem in SM form a pattern
Kyushu Institute of Technology
in .
${}^{t}\sigma_{c}$$\sigma_{c}$$\sigma_{c}^{-1}(\mathfrak{M})$$r^{V}ules$

$A$

$s$

$A$

$s$

$A$

$A^{C}$$\sigma_{c}^{-1}(\mathfrak{M})$$\bigcup_{M\in \mathfrak{M}}cO*(M,$$\sigma_{c}^{-1}(\mathfrak{M})\in \mathcal{L}\Leftrightarrow M\in \mathfrak{M}^{C}uo(M, W-M)\in,C$

$)$

$L$

$\mathfrak{M}$$\mathcal{L}0$

$c$

$c$

$\mathcal{L}$138
2

Cellular automata

In case $B=2$ , the Boolean algebra structure,ofcoincides with that of set lattice andIn what follows, we denote by 2 the Boolean algebra
and , respectively become union, intersection,
consisting of two constants and 1.
complementation and inclusion. The setof alltransition functions on
is a subalgebra of theBoolean algebra $[2^{G}arrow 2^{G}]=(2^{G})^{(2^{G})}$ . On the
2.1 Cellular automata on groups
other hand, the set $\mathcal{L}_{V}=[2^{V}arrow 2]$ of all local
Notion of CA on groups was first treated as special transition rules with the support is regarded ascases for CA on graphs named Caylay graphs which a Boolean algebra as. All ofandrepresent groups [8, 7, 12]. General approaches arecomplete.
arefound in [1], [6] and [13]. Here we follow our previ, by virture
For any pair of subsets
ous investigation [1].
ofcan be naturally regarded as a
Let be a group. By regarding its power set. We remark that the complemensublattice ofas the configumtion space, a local transition rule tation depends on the algebra to which the elementwith the support
is defined as a family of
belongs. When the support should be explicitely
subsets of . The role of is explained as follows. indicated,(see also the remark at
we write asLet.
be the evolution of a configuration
the
of
end
\S 2.3).
Then the state at any site $g\in c’$ is determined
Algebraic properties of CA’s on groups are invesaccording to whether the state pattern of aroundtigated in [1] and [6].
translated onto around the unit element by
is in or not. More explicitly,$B^{X}$$A$$\vee,$$\neg$$\leq$$0$$\mathcal{T}_{G}$

$G$

$V$

$2^{(2^{V})}$$X^{B},$$\mathcal{L}_{V}$$\mathcal{T}_{G}$$V\subseteq W\subseteq G$$2^{V}\subseteq 2^{W},$$G$$\mathcal{L}_{V}$$\mathscr{C}=$$\mathcal{L}_{W}$$2^{G}$$V\subseteq G$$V$$\mathcal{L}$$\mathcal{L}$$\neg V$$c’$$c\in \mathscr{C}$

$c$

$V$

$g$

$g^{-1}$$e$$\mathcal{L}$

$c$

2.3

c’ $=\{g\in G|g^{-1}c\cap V\in \mathcal{L}\}$ .

$\mapsto$

Correspondence between local
transition rules and transition
functions

Such a transition function is characterized as atranformation :commutes with the G- For a transition rulewith the support
action:we define a transition function on by$T$$\mathscr{C}arrow \mathscr{C}$$\mathcal{L}\in \mathcal{L}_{V}$

$V$

,

$G$

$T(ac)$$=$$a(T(c))$ ,$(a\in G, c\in \mathscr{C})$,$T_{L}(c)$$\{g\in G|g^{-1}c\cap V\in \mathcal{L}\}$$=$$(c\in \mathscr{C})$.

where the action of $a\in G$ on a configuration
It can be easily verified that
commutes with theis given by $ac=\{ag|g\in c\}$ . The usual infi- G-action.
nite (resp. periodic with the size $N$ ) l-dimensional
To consider the converse correspondence, we inCA is obtained by considering a symmetric interval troduce for transition functions a notion corre: sponding to that of supports of local transition(resp.
$V=[-r, r]$ in the Abelian groupthe residue ring modulo $N$ ).
:be a transition function
rules. Let. We say that is local at a site $g\in G$
and
on if
2.2 Algebraic structure$c\in \mathscr{C}$$T_{L}$$G=\mathbb{Z}$$\mathbb{Z}_{N}$$T$$\mathscr{C}arrow \mathscr{C}$$T$$V\subseteq G$$V$

For a given set $X$ and a Boolean algebra $B$ we$c\cap V=c’\cap V$$g\in T(c)$ iff $g\in T$ (c’)
consider the pointwise Boolean algebra structureon the setof all B-valued functions defined on is satisfied for any configurations. We
X. Namely, it is defined bya domain of locality of at . We denotecallby
the set of all transition functions local at$(fvg)(x):=f(x)vg(x)$ ,
by
site
on
.
is a complete Booleana$(f_{A}g)(x):=f(x)\wedge g(x)$ ,subalgebra of .
For simplicity, we denote byinstead of$(\neg f)(x):=\neg(f(x))$
for the unit element . Then it can be easily shown.
thatfor $f,$ $g\in B^{X}$ and $x\in X$ . Then we have
Now we assign a local transition function$f\leq g$$f(x)\leq g(x)$.
with the support to each transition function$\Rightarrow$$B^{X}$

$c,$

$V$

$T$

$c’\in \mathscr{C}$$g$$\mathcal{T}_{g,V}$

$g$

$V$

$\mathcal{T}_{g,V}$$\mathcal{T}_{g,V}$$\mathcal{T}_{G}$$\mathcal{T}_{V}$$\mathcal{T}_{e,V}$$e$$\mathcal{T}_{V}=\mathcal{T}_{g,gV}$$\mathcal{L}_{T}\in$$\Leftrightarrow$$(\forall x\in X)$$\mathcal{L}_{V}$

$V$

139
$T\in \mathcal{T}_{V}$by. Then thecomposition
of
is
and
the unique transition function that is local at on$VW$ satisfying
Theorem 3 Let$L_{T}$$\{c\in 2^{V}|e\in T(c)\}$$=$.

$\mathcal{L}\in \mathcal{L}_{V},$$T_{\mathcal{L}}\circ T_{\mathfrak{M}}$$\mathfrak{M}\in \mathcal{L}_{W}$$T_{\mathfrak{M}}\in \mathcal{T}_{W}$$T_{\mathcal{L}}\in \mathcal{T}_{V}$$e$By virtue of commutativity of$=$$\mathcal{L}_{T}$$T$

with G-action,$\{g^{-1}c\in \mathscr{C}|c\in 2^{gV}, g\in T(c)\}$$T_{L}oT_{\mathfrak{M}}$$=$$T_{\mathcal{L}\sim \mathfrak{M}}$.

holds for an arbitrary.
Then we have the following theorem and proposition.
$g\in G$

3 Mathematical morphology
Theorem 1 Both of the mappings
andare isomorphisms of Boolean algebrals and each of them is MM was first introduced as an analyzing tool ofimage processing by shape and has been developed
the inverse of each other.
as a systematic non-linear analysis methodology
Proposition 2 Let.
[9, 10]. Theoretically, it is founded on complete lat1.
, i. e.,is an ideal ofis a sublattice tices [10, 5] and its methodology has been extended
ifthen there [4].
In this section, we recall minimal requisites for
MM. For precise description and general references,2.
is a Boolean subalgebra of, i. e.,is readers should see [10], [4]a sublattice ofand ifthen $\neg VT=$$\mathcal{T}_{V}\ni T\mapsto$$L_{T}\in \mathcal{L}_{V}$$\mathcal{L}_{V}\ni \mathcal{L}$$\mapsto$$T_{\mathcal{L}}\in \mathcal{T}_{V}$$V\subseteq W\subseteq G$$\mathcal{L}_{V}$$\mathcal{L}_{W}$$\mathcal{L}_{V}$$\mathfrak{M}\subseteq \mathcal{L}(L\in \mathcal{L}_{V}, \mathfrak{M}\in \mathcal{L}_{W})$$\mathfrak{M}\in \mathcal{L}_{V}of\mathcal{L}_{W}and$$\mathcal{T}_{V}$$\mathcal{L}_{V}$$\mathcal{T}_{W}$$T\in \mathcal{T}_{V}$$\mathcal{L}_{W}$$\neg WT$.

It follows from this proposition that the two embeddings
andare not compatible with the isomorphisms
andestablished by Theoreml. For more precise, see [1].
Readers also find a proof of Theoreml there.
$\mathcal{L}_{V}\subseteq \mathcal{L}_{W}$$T_{V}\subseteq \mathcal{T}_{W}$$\mathcal{L}_{V}\cong \mathcal{T}_{V}$2.4

Binary relations and correspondences

3.1$\mathcal{L}_{W}\cong \mathcal{T}_{V}$In what follows, we regard a binary relation$X\cross A$ as a correspondence of $X$ intoby$R\subseteq$

$A$

$R$

: $X\ni x\mapsto\{a\in A|(x, a)\in R\}\subseteq A$

Local composition of local tran- and vise versa. The tmnspose of is given bysition rules${}^{t}R=\{(a, x)|a\in A, x\in X, (x, a)\in R\}\subseteq A\cross X$${}^{t}R$

We define the Mikowski product of $V,$
$VOW$

$W\subseteq G$

by$\{vw\in G|v\in V, w\in W\}$ .

$=$

$R$

or, in terms of correspondence,: $A\ni a\mapsto\{x\in X|(x, a)\in R\}\subseteq X$ .
This is a non-commutative version of Minkowski
addition for Abelian groups [4]. Then we define As well as for ordinary mappings, we denote thethe local composition ofby
and
by $R(x)$ andimage of an element $x\in X$ under$Y\subseteq X$ by $R( Y)=\bigcup_{y\in Y}R(y)$ .
a
that
of
subset.
(2)
The usual set theoretical inverse image of a subset
Here $\sigma_{c}:Varrow 2^{W}$ is the mapping defined bycan be expressed as $R^{-1}(B)={}^{t}R(B)$ in our$\sigma_{c}(v)=v^{-1}c\cap W$(3) notation.
${}^{t}R$$\oplus$$\mathcal{L}\in \mathcal{L}_{V}$$M\in \mathcal{L}_{W}$$R$$Ce\mathfrak{M}=\{c\in 2^{VW}|\sigma_{c}^{-1}(\mathfrak{M})\in \mathcal{L}\}$$B\subseteq A$

for $c\in 2^{VW}$ anddenotes the inverse image of the set
with respect to this mapping. Finally,is the set of all $confi_{o}urationsc$
such that this inverse image coincides with a member of L. By definition,.
The following theorem ensures us to call this as
local composition[l]:$\sigma_{c}^{-1}(\mathfrak{M})$$\mathfrak{M}\subseteq 2^{W}$$L*\mathfrak{M}$$\mathcal{L}*\mathfrak{M}\in \mathcal{L}_{VW}$

3.2

Dilation and erosion

Dilation and erosion are the fundamental operators
in MM. Notions of dilation and erosion were extended to complete lattices and general properties
are investigated [10, 5, 4]. Here we adopt a slightly
general definition[3].

140
Let $X,$be partially ordered sets. A mapping : $Xarrow A$ is called an algebraic dilation orfor short, a dilation iff for any family
in $X$ , the famwhich admits the supremum
in
ilyalso admits the supremum
is satisfied. Namely,
andevery dilation preserves supremum. Dually, a mapping : $Xarrow A$ is called an algebmic erosion orfor short, an erosion iff for any family, the family
which admits the infimum
also admits the infimum andis satisfied. Dually to dilation, every
erosion preserves infimum.
$A$$\psi(x)\in B\Leftrightarrow\{\psi(x)\}\subseteq B$

for $B\in 2^{A}$ . Hence$\delta$$\delta_{\psi}(B)=\epsilon_{\psi}(B)=\psi^{-1}(B)$$\{x_{\lambda}\}\subseteq X$$_{\lambda}x_{\lambda}$$_{\lambda}\delta(x_{\lambda})$$\{\delta(x_{\lambda})\}$$A$$_{\lambda}\delta(x_{\lambda})=\delta(_{\lambda}x_{\lambda})$.

(6)

On the other hand, since its transposeis
as a biary relation of$\{x\in X|a=\psi(x)\}=\psi^{-1}(\{a\})$ , its dilation anderosion are respectively expressed as$\iota\psi(a)$

$a$

$\in$

$A$

$\psi(a)$$=$$\epsilon$$\{x_{\lambda}\}\subseteq X$$(7)$$\delta_{\psi}\ell(Y)=\{a\in A|\exists y\in Y, \psi(y)=a\}=\psi(Y)$$\bigwedge_{\lambda}x_{\lambda}\in X$$\bigwedge_{\lambda}\epsilon(x_{\lambda})=$$\{\epsilon(x_{\lambda})\}$

and$\epsilon(\bigwedge_{\lambda}x_{\lambda})$$\epsilon_{\psi}t(Y)=\{a\in A|\psi^{-1}(a)\subseteq Y\}=\overline{\psi}(Y)$

.

(8)

be a
Example 3.2 (MM on groups) Let, the symmetry of $H$ is definedgroup. For
by $\tilde{H}=\{g\in G|g^{-1}\in H\}$ .
The set dilation and the set erosion defined by
the binary relation$G$

Proposition 4 Every dilation or erosion is monotone.
Example 3.1 (MM of set lattices) Let$X\cross A$ be a binary relation.
We define the fol(notice thatintolowing set operators ffom
the direction is opposed):$R$$\subseteq$$H\subseteq G$$R_{H}=\{(g, g’)\in GxG|g^{-1}g’\in H\}$

$2^{X}$$2^{A}$$\delta_{R}(B)=\{x\in X|R(x)\cap B\neq\emptyset\}$

,

(4)

(5)

$\epsilon_{R}(B)=\{x\in X|R(x)\subseteq B\}$

: $2^{A}arrow 2^{X}$ is a dilation andfor $B\in 2^{A}$ . Then
$2^{A}arrow 2^{X}$
and:is an erosion. We callthe set dilation and the set erosion defined byrespectively.
By considering the transpose
of $R$ , we also.
obtain operators
We note that any dilation and erosion between
set lattices are obtained in this way. In fact, forany dilation : $2^{X}arrow 2^{A}$ , since any set lattice is“atomid’ and preserves supremum by definition,. Thuswe have$Y\subseteq
X$
is determinedthe effect of on any set
by its effect on each singleton. By taking the correspondence: $X\ni x\mapsto\delta(\{x\})\subseteq A$ , we have
. For any erosion $E$ : $2^{X}arrow 2^{A}$ , since its
dual
is a dilation, there exists a. Then it canbinary relation $R$ such that.
be verified that
Relationships among “duality”, “transposition“and ”adjunction” will be investigated in \S 3.4.
As a special case, consider a mapping : $Xarrow$. In this case, since the image of $x\in X$ by is, we havea singleton$\tilde{H}$are respectively called the dilation and the erosion. We note that for $a\in G,$ $R_{H}(a)=$by $H$ on the$r\dot{v}ght$

and hence$aH$$\delta_{R_{H}}(K)=\bigcup_{h\in H}Kh^{-1}$,$\epsilon_{R_{H}}(K)=\bigcap_{h\in H}Kh^{-1}$.

$\delta_{R}$$\delta_{R}$$\epsilon_{R}$$\epsilon_{R}$$R$${}^{t}R$$\delta_{l}R:2^{X}arrow 2^{A},$$\epsilon_{R}t:2^{X}arrow 2^{A}$$\delta$$\delta$of $K$ by $H$ on the right coinThe dilation
cides with the Minkowski product $K\tilde{H}$ of $K$ andof $K$ by. On the other hand, the erosion$H$ on the right is denoted byand called theon the right. lfurMinkowski quotient of $K$ by, we havethermore, since.
andSimlarly, by considering the binary relation$\delta_{R_{H}}(K)$$\tilde{H}$$\epsilon_{R_{H}}(K)$$K\copyright\tilde{H}$$\tilde{H}$${}^{t}R_{H}=R_{\tilde{H}}$$\delta_{{}^{t}R_{H}}=\delta_{R_{E}}$$\epsilon tR_{H}=\epsilon_{R_{H}}$$\delta(Y)=\delta(\bigcup_{y\in Y}\{y\})=\bigcup_{y\in Y}\delta(\{y\})$$L_{H}=\{(g, g’)\in G\cross G|g’g^{-1}\in H\}$$\delta$$R$$\delta=\delta_{{}^{t}R}$$\overline{\epsilon}(Y)=(\epsilon(Y^{0}))^{c}$$\overline{\epsilon}=\cdot\delta_{{}^{t}R}$$\epsilon=\overline{\delta_{{}^{t}R}}=\epsilon\iota R$$\psi$$A$$\psi$$\{\psi(x)\}$$\{\psi(x)\}\cap B\neq\emptyset\Leftrightarrow$by
we obtain the dilationand the erosion$H$ on the left. Notice that the dilationof$K$ by $H$ is equal to $\tilde{H}K$ . On the other hand, theof $K$ by $H$ on the left is denoted
erosionby \copyright K and called the Minkowski quotient of $K$byon the left.
$\delta_{L_{H}}$$\epsilon_{L_{H}}$$\delta_{L_{H}}(K)$$\epsilon_{L_{H}}(K)$$\tilde{H}$$\tilde{H}$3.3

Adjoint

The notion of adjoint plays the fundamental roll in
MM analysis. It is defined as follows. Let $X,$ be
$A$

141
partially ordered sets and : $Xarrow A,$ $g:Aarrow X$ and is one of these three transformations thenbe mappings. The pair $(f, g)$ is called an adjoint of $\tau(\tau(\mu))=\mu$ is satisfied.
into iff for
Let $X,$
be Boolean lattices and : $Xarrow A$
beadilation.
Then its dual 6 : $Xarrow A$ , tmnspose$f(x)\leq a\Leftrightarrow x\leq g(a)$(9)
and adjoint: $Aarrow X$ are respectively
is satisfied. Then is called the lower adjoint ofdefined byand is called the upper adjoint of .
$(x\in X)$ ,Relations between MM operators and adjoint$a\wedge\delta(x)=0$$(x\in X, a\in A)$ ,pairs are given by the following two propositions.
$(x\in X, a\in A)$ .
Proposition 5 Let $X,$ be partially ordered sets
and $(f, g)$ be an adjoint of $X$ into . Then is a Although transpose and adjoint are implicitly
fined, they are uniquely determined if they exist for
dilation and is an erosion.
a given dilation.
The converse of Proposition 5 holds under the
Similarly, for an erosion: $Xarrow A$ , its dual
assumtpions of completeness:: $Xarrow A$ , tmnspose: $Aarrow X$ and
Proposition 6 Let $X,$ be partially ordered sets.
are respectively defined by
1. Whenis a complete -semi lattice, for a$(x\in X)(x\in X,a\in A)$
mapping : $Xarrow A$ to be a dilation, it is nec$t_{\in(a)x=}1$,
essary and sufficient that is monotone and$(x\in X, a\in A)$ .
the pair $(f, g)$ is an adjoint for the mapping
Proposition 7 Let $X,$ be Boolean lattices.
defined by $g(a)=f^{-1}\{b\in A|b\leq a\}$ .
$f$

$X$

$A$

$\forall x\in X,$$\tau$$\forall a\in A$$A$$\delta$${}^{t}\delta:Aarrow X$$f$$\delta^{*}$

$g$

$f$

$g$

$\overline{\delta}(x)$$t_{\tilde{\delta}(a)}\wedge x=0$

$x\leq\delta^{*}(a)$$\neg(\delta(\neg x))$$=$$\Leftrightarrow$$\delta(x)\leq a$$\Leftrightarrow$

$A$

$A$

$dearrow$

$f$

$g$

$\epsilon$$t_{\xi}$$\overline{\epsilon}$$A$$ad_{J}\acute{o}int$$\epsilon^{*}:Aarrow X$$A$$\vee$$\overline{\epsilon}(x)$$=$$a\epsilon(x)=1\neg(\epsilon(\neg x))$$f$$\Leftrightarrow$$f$$\epsilon^{*}(a)\leq x$$a\leq\epsilon(x)$$\Leftrightarrow$$A$

1. For a dilation : $Xarrow A$ it has an adjoint
iff it has a transpose .

2. When $X$ is a complete -semi lattice, for a
mapping: $Aarrow X$ to be an erosion, it isnecessary and sufficient that is monotone and${}^{t}\delta$$g$

2. For an erosion : $Xarrow A$ it has an adjoint
ifi it has a transpose .

$g$$\epsilon$

the pair $(f, g)$ is an adjoint for the mapping
defined by $f(x)=\wedge g^{-1}\{y\in X|x\leq y\}$ .

$(\delta_{{}^{t}R}, \epsilon_{R})$Proposition 8 Let $X,$.

${}^{t}\delta$

2. For an erosion
adjoint
an erosion.

$\forall x\in X(x\in Y\Rightarrow(a\in R(x)\Rightarrow a\in B))$

Similarly, the pair$(\delta_{R}, \epsilon_{t}R)$

is an adjoint of

In particular, for a group$G$.

, we have for $H,$

$J$,

$K\in 2^{G}$$H\subseteq\tilde{J}\copyright K\Leftrightarrow JH\subseteq K\Leftrightarrow J\subseteq K\emptyset\tilde{H}$.

3.4

Involutions in Boolean lattices

3.4.1

Duality, transposition and adjunction

For dilations and erosions of Boolean lattices, there
are three sorts of involutive transformations of operators, namely, duality, transposition and adjunction [10, 4]. More precisely, if is an MM operator
$\mu$

3.4.2

into

$2^{A}$

be Boolean lattices.

$\delta^{*}$$\epsilon$$2^{X}$$A$

1. For a dilation : $Xarrow A$ , the dua16 and the
adjoint
are erosions and the transpose isa dilation.

$2^{A}$$\Leftrightarrow Y\subseteq\epsilon_{R}(B)$“$\delta$$\delta_{{}^{t}R}(Y)\subseteq B$$\Leftrightarrow\forall a\in A,$$\epsilon$$\iota_{\epsilon}$

Example 3.3 (Adjoint of set lattices) Let$R\subseteq X\cross A$ bea binary relation. Then the pairis an adjoint of. In fact, for
into$Y\in 2^{X},$ $B\in 2^{A}$ ,$2^{X}$$\delta^{*}$$\delta$$\wedge$‘: $Xarrow A$ , the dual and theare dilations and the transpose is$\overline{\epsilon}$$\epsilon$${}^{t}\epsilon$

Interrelations among involutions

All of the operator transformations defined above

are involutive. On the other hand, successive applications of operators are independent of order. For
example,andcoincide and are equal to ‘and so on.
$\overline{({}^{t}\delta)}$$\delta$$t\cap\delta$

Example 3.4 (Involutions of set lattices)$[n$case of a binary relation $R$ , for the operators, the results of involutions areandexpressed in more explicit forms:$\delta=\delta_{R}$$\epsilon=\epsilon_{R}$$($$\overline{\delta_{R}}=\epsilon_{R}$$\overline{\epsilon_{R}}=\delta_{R}$,${}^{t}\delta_{R}=\delta_{\ell}R$,$(\delta_{R})^{*}=\epsilon eR$,,${}^{t}\epsilon_{R}=\epsilon_{t}R$,$(\epsilon_{R})^{*}=\delta_{{}^{t}R}$.

142
By virtue of these equalities, we only have to em- Now we decompose the condition $v^{-1}c\cap W=M$
, into two partsploy 4 operators among them, for example
diagrammatically. The relations areand$v^{-1}c\cap W\subseteq M$ .
$M\subseteq v^{-1}c\cap W$(14).
represented as follows:$\delta_{R},$$\delta_{{}^{t}R}$$\epsilon_{R}$$\epsilon_{t}R$$\delta_{R^{-}}^{-}\epsilon_{R}$By noticing that $M\subseteq W$ ,1st part of (14)$\Leftrightarrow M\subseteq v^{-1}c$$\Leftrightarrow vM\subseteq c$$\Leftrightarrow\{v\}\subseteq c\emptyset\tilde{M}$$\delta_{{}^{t}R}--\epsilon_{\ell}R$

Figure 1: Rerations among involutive operations
on set lattice morphologies

Hence the 1st part of (14) is equivalent to that
. On the other hand, by using the adjunction,$v\in$$c\copyright\tilde{M}$$X\cap Y\subseteq Z\Leftrightarrow X\subseteq Z_{\cup}Y^{C}$$2^{nd}$$4$.

part of (14) $\Leftrightarrow v^{-1}c\subseteq MuW^{C}=(W-M)^{c}$

Main result–$c$$\Leftrightarrow\tilde{c}v\subseteq(W-M)$

As an MM interpretation of local composition, thefollowing theorem is obtained in [2].
Theorem 9 For $c\in 2^{V\cdot W},$
exists a $L_{c}\in L$ such that$c\in \mathcal{L}0\mathfrak{M}$$\Leftrightarrow\{v\}\subset c$\copyright $((W–M)^{c})$ .

iff there By using dualities,$\delta_{{}^{t}\sigma_{c}}(L_{c})\subseteq \mathfrak{M}\subseteq\epsilon e_{\sigma_{c}}(L_{c})$

(10)

$c$

\copyright $((W–M)^{c})=(c(W^{-}-M))^{c}$

To give a further interpretation of local composition, we consider the hit-or-miss transform on .
Thus theOn $G,$ (1) can be expressed as$=c^{C}$\copyright (W-M)--.

$G$

part of (14) is equivalent to that $v\in$\copyright (W-M)--. By combining these results, thecondition $v^{-1}c\cap W=M$ is equivalent to$2^{nd}$$c^{C}$$XO(B, B’)=(X\emptyset\tilde{B})\cap(X^{c}\copyright\tilde{B’})$(11)

Here we consider the morphology on the right.
Then our main result can be stated as
Theorem 10 (Main result) For$\mathcal{L}\sim$

sn iff$c\in 2^{V\cdot W},$$\cup cO(M, W-M)\in L$ .

$v\in(c\copyright\tilde{M})\cap(c^{C}\copyright(W^{-}-M))$$=c@(M, W-M)$ .

$c\in$

q. e. d.

This establishes the theorem.
(12)

By this theorem, the local composition
contains the all local patterns consisting of thosefits somepoints where $M$ fits and $W-M$ fits
Proof. By virtue of (2), it suffices to show that$M$.
inpatternpatterninform ais straightfowardly appliedThe
main
theorem(13).
$\cup cO(M, W-M)$
to the local decomposition problem. Namely, forand A
given local transition rules EM.
Since is a mapping of into
for some, when is .A decomposed into
Furthermore, by the definition of inverse image, for? From main theorem, it follows that$v\in V$ ,$\bigcup_{M\in \mathfrak{M}}KO*(M, W-M)$ must be a member offoreach $K\in$ A and such subsets constitute . Noticethat $\bigcup_{M\in \mathfrak{M}}KO(M, W-M)$ may not be included$v^{-1}c\cap
W=M$.
in . Thus we havesuch that$\mathcal{L}oSPt$$M\in \mathfrak{B}t$$c$$c^{C}$$c$$\mathfrak{M}$$\mathcal{L}$$\sigma_{c}^{-1}(\mathfrak{M})=$$M\in \mathfrak{M}$$\in \mathcal{L}_{W}$$\sigma_{c}$$V$$2^{W},$ $\sigma_{c}^{-1}(M)\subseteq V$$\mathcal{L}_{VW}$$\in$$L\sim \mathfrak{M}$$\mathcal{L}\in \mathcal{L}_{V}$$\mathcal{L}$$\mathcal{L}$$v\in\sigma_{c}1(\mathfrak{M})\Leftrightarrow\sigma_{c}(v)\in Wt$$\Leftrightarrow\exists M\in \mathfrak{M}$

$V$

143
Cororally 11 Let
andto be equal tofor some$M\in \mathcal{L}_{W}$$\mathcal{L}\theta M$$A\in \mathcal{L}_{VW}$$\mathcal{L}\in \mathcal{L}_{V}$and sufficient that$\bigcup_{M\in\alpha\pi}KO(M, W-M)\subseteq V$

for all$K\in$

A. Then the left factor$\mathcal{L}$$\mathcal{L}=\{\bigcup_{M\in im}KO*(M, W-M)$. For A [7] E. R\’emila, “An Introduction to Automata
on Graphs.” M. Delorme and J. Mazoyer,
Eds., Cellular Automata, A Pamllel Model,
Kluwer Academic Publishers, Dordrecht, 345352, 1998.

, it is neccesaryis given by$K\in A\}$.

[S] Zs. R\’oka, “One.way cellular automata on cayley graphs,” \’Ecole Normale Sup\’erieure de Lyon,
Research Report $N^{o}93-07$ , 1993[9] J. Serra, Image Analysis and Mathematical
Morphology. Academic Press, London, 1982.
Notice that the notion of local decomposition
should be defined modulo equivalence. That is, twolocal transition rules A and $A’$ may define the same [10] J. Serra, Ed., Image Analysis and Mathematical Morphology, Part II: Theoretical Advances.
transition function. In this case, we call
Academic Press, London, 1988.
A is equivalent to $A’$ and denote by $A\sim A’$ . For
this reason, we say thatis a local decmopo- [11] H. J. A. M. Heijmans, Morphological Image
sition of .A iff. The cororally gives a
Opemtors. Academic Press, Boston, 1994.
sufficient condition for A to be locally decmoposed[12] S. Yukita, “Dynamics of cellular automata on
into.
groups.” IEICE Trans. Inf. Eli Syst., vol.E82$D(10),$ 1316-1323, 1999.
$T_{R}=T_{R^{l}}$$\mathcal{L}0\mathfrak{M}$$A\sim\epsilon_{\phi}\infty$$\mathcal{L}\phi \mathfrak{M}$References[1] M. Ifujio, “XOR2 $=90$ -graded algebra structure of the boolean algebra of local transition
rules-,, , IN RIMS k\^oky\^uroku, vol. 1599, 97-102,

2008.

[2] M. Fujio, “Morphological Interpretation of
Local Composition of Cellular Automata on
Groups,” Pmc. of
Intemational Symposium on Communications Infomation Technologies, pp. 133-136, 2010.
$10^{th}$[3] M. Fujio and I. Bloch, ”Non-classical logic
via mathematical morphology,”
NationaleSup\’erieure des T\’el\’ecommunications, Technical
Report ENST 2004DOlO, 2004.
$\mathscr{D}_{cole}$[4] H. J. A. M. Heijmans, Morphological Image Opemtors. Academic Press, Boston, 1994.

[5] H. J. A. M. Heijmans and C. Ronse, “The algebraic basis of mathematical morphology. i. dilations and erosions,” Computer Vision Graphics
Image Processing, vol. 50, pp. 245-295, 1990.
[6] T. Ito, M. FUjio, S. Inokuchi and Y. Mizoguchi,“Composition, union and division of cellular automata on groups,” Proc. of
Intemational
Workshop on Cellular Automata and DiscreteComplex Systems, pp. 255-264, 2010.
$16^{th}$[13] T. Ceccherini-Silberstein and M. Coornaert,
Cellular Automata and Groups.
SpringerVerlag, Berlin Heidelberg, 2010.