as pmf) p is such that !m∈M . p (m) = 1. Also, let i ∈ Q be an
ll
interior node with children i ,…, i . Then i has an associated
14
superposition distribution D whose pmf p is such that ∀m∈M .
ii
p (m)= ∑ 4 p (m).
i j = 1 ij
The intuition is as follows. If a leaf node occurs at the maximum depth of the quadtree, then it corresponds to the current mode of a clha. As clha are deterministic, they assume
one of the values in M with probability 1. (We will weaken this
restriction at the end of the section when we consider superposition quad-graphs.) If the leaf does not occur at the maximum
depth of the quadtree, then it corresponds to the superposition of identical degenerate distributions, and no additional
information is obtained by decomposing the leaf into its four
superposition components. The visual interpretation is that a
pixel has one definite color, and nothing is learned by decomposing an area in which all pixels have the same color.
As for the distribution of an interior node i, if all of i’s children are leaves, then, for each mode value m, i’s superposition
is the mean of the occurrences of m. Hence, the probability that
the mode of the parent is m is the probability that the mode of
an arbitrary child is m. If i’s children are interior nodes, it still
holds that the probability that i’s mode is m is the probability
that the mode of an arbitrary leaf below i’s children is m.
We call a quadtree whose nodes are labeled with leaf- and
interior-node distributions a superposition quadtree (sqt). The
distributions in an sqt are not known in advance; our learning
algorithm seeks to determine them for what we perceive to be
spirals. The use of probability distributions is justified by the
fact that different spirals might have slightly different shapes,
i.e., slightly different distributions of values for the leaf nodes
of their associated quadtrees.
The sqts presented so far were constructed over a finite
matrix A containing 2k 2k elements. In general, sqts can be
obtained via the finite unfolding of a quad-graph.
Definition 2 (sqg). A superposition quad-graph (sqg) is a
4-tuple G = (V, v , R, L) consisting of:
0
· a finite set of vertices V with initial vertex v ∈ V,
0
· a transition relation R ⊆ V × [ 1.. 4] × V
s.t. ∀v ∈ V, i ∈ [ 1.. 4]. ∃ u ∈ V. (v, i, u) ∈ R, and
· a probability-distribution labeling L
s.t. ∀v ∈ V. L(v) = Σ L(u).
u∈R(v)
The condition on R ensures that each vertex in V has precisely
four successors in R. The condition on L ensures that the
probability distributions are related through superposition.
The manner in which we construct sqts as finite unfoldings
of sqgs can be extended to support the definition of infinite
sqts generated by recursion. That is, it supports the definition of fractals. Furthermore, just as we use sqts to represent
finite images, sqgs can be used to represent infinite images,
i.e., fractals.
Figure 5(a–c) gives sqgs representing the recursive specification of three fractals and a graphical depiction of the
unfolding of these sqgs up to depth 3. (The sqg of Figure 5(d),
for which no depiction is given, is considered below.) Note
the fractal-like nature of these pictures: the gray areas represent recursion and correspond to recursive nodes in the sqgs.
Such nodes are labeled by distribution variables, the values for
which can be computed by solving a linear system. For example, x and y in Figure 5(b) are computed by solving the linear
system x = 1/4 (x + 1 + y) and y = 1/4 ( 1 + x). The four self-loops
of the leaves are not shown for simplicity. Note that leaves may
now be associated with any constant distribution. Also note
that the finite-state sqgs of Figure 5 (b) and (d) yield equivalent infinite sqts.
4. LineaR suPeRPosition LoGic
In this section, we define lssl. Although the lssl logic—
especially its spatial analogues of the temporal fixpoint operators
of ltl18—and its underlying semantics (Kripke structures)
allow us to reason about infinite paths, physical considerations such as the number of myocytes in a cardiac tissue or
screen resolution impose a maximum length k on paths. We
therefore maintain k as a parameter in lssl’s semantic definition, placing us within the framework of bounded model
checking. 3
Every finite sqt can be transformed into an sqg by adding
to each leaf node a self-loop labeled by i, i ∈ [ 1.. 4]. Moreover,
an sqg can be transformed into a Kripke structure by erasing
(forgetting) the transition labeling, collapsing all resulting
transitions that share the same source and target nodes into
one transition, and assuming nondeterminism among transitions emanating from the same node. For example, applying
this forgetful transformation to the sqgs of Figure 5 yields the
Kripke structures of Figure 6, where the self-loops are made
explicit. The Kripke structure of Figure 6(d) can be seen as
the minimal-state equivalent of the one of Figure 6(b) where
nodes labeled by 0 or 1 are shared.
Definition 3 (Kripke structure). A Kripke structure (ks) over
a set of atomic formulas AF is a four-tuple M = (S, I, R, L) consisting of:
· a countable set of states S, with initial states I ⊆ S,
· a transition relation R ∈ S × S
with ∀s ∈ S. ∃t ∈ S. (s,t) ∈ R, and
· a labeling (or interpretation) function L : S → 2AF.
The condition associated with the transition relation R
ensures that every state has a successor in R. Consequently, it
is always possible to construct an infinite path through a ks,
figure 5: fractals as finite-state SQGs: (a) x = 2/3, (b) x = 5/11, y = 4/11,
and (c) x = 1/2. SQG (d) is equivalent to SQG (b).
1
x
23 4
(a)
101
1
4
x
23 4
10y
1 23
(b)
010
1
4
x
23
(c)
10
1
4
x1
23 4
10y
1, 3
2
(d)
