Determinism in Multi-Soliton Automata

For a brief account of the history of solitons we refer to [8] and [9, pp.18–19]. An extensive list of references regarding soliton computations and soliton automata can be found in [2]. The notion of soliton automata is encountered in [4]. In that paper also the concepts of determinism and strong determinism of soliton automata are considered and have been further investigated in [5, 6]. Strong determinism requires that, for every possible start and target atom, a soliton can take at most one path leading through the molecule. The main simplification of soliton automata as considered in [4, 5, 6] is the assumption that only one single soliton can be present in a molecule at the same time. This restriction has been overcome in [2] (and the subsequent paper [7]), where multi-soliton automata have been taken into consideration in which more than one soliton can travel through a molecule simultaneously. Several different concepts of determinism for multi-soliton automata are defined in [10] and [3].

The present paper aims to continue this line of research. In the next section, the necessary notions related to soliton automata and the various concepts of determinism are given. We restrict ourselves to the case of multi-soliton automata since single-soliton automata as considered in [4] are special cases of multi-soliton automata. In addition to deterministic and strongly deterministic soliton automata, also the concepts of perfect determinism and the degree of non-determinism are defined. Perfect determinism describes a natural concept that is somewhat ”in between” determinism and strong determinism for soliton automata. The degree of non-determinism is a measure of descriptional complexity quantifying the amount of non-determinism of soliton automata. Section 2 concludes with the proof showing that the degree of non-determinism is connected with respect to soliton automata, that is, for every positive integer $g$, there is a soliton automaton with degree of non-determinism $g$.

Section 3 extends the notions of determinism to graphs underlying soliton automata (namely the graphs representing the bonding structure of the molecules under consideration, called soliton graphs). Similarly to the results known for the single-soliton case [4], we give a characterization of soliton graphs always inducing strongly deterministic soliton automata. In [4] it is shown that a single-soliton automaton is strongly deterministic if and only if its underlying graph is a tree or a so-called chestnut (see Definition 21). For the multi-soliton case, we show that a soliton graph is strongly deterministic if and only if it is a tree. Moreover, we prove that there is a chestnut which is not even perfectly deterministic. The paper concludes with a few remarks on open research questions related to the results presented here.

An alphabet is a finite non-empty set the elements of which are called symbols. Let $\Sigma$ be an alphabet. The set of all (finite) words over $\Sigma$, including the empty word $\lambda$, is denoted by $\Sigma^{\ast}$; let $\Sigma^{+}=\Sigma^{\ast}\setminus\{\lambda\}$. The length $\text{lg}(w)$ of a word $w\in\Sigma^{\ast}$ is defined by

A semi-automaton is a construct $\mathcal{A}=(Q,\Sigma,\tau)$ where $Q$ is a non-empty set, $\Sigma$ is an alphabet and $\tau:Q\times\Sigma\to 2^{Q}$ is a mapping. The elements of $Q$ are called states; $\Sigma$ is the input alphabet of $\mathcal{A}$; $\tau$ is the transition function of $\mathcal{A}$. In this paper, we assume that $Q$ is finite and that, for all $q\in Q$ and all $a\in\Sigma$, $\tau(q,a)\not=\emptyset$. Moreover, we drop the prefix “semi-” as we do not consider any other kind of automata.

Let $\mathcal{A}=(Q,\Sigma,\tau)$ be an automaton. The transition function $\tau$ is extended to $2^{Q}\times\Sigma^{\ast}$ as follows: for $R\subseteq Q$ and $w\in\Sigma^{\ast}$, let

For $w\in\Sigma^{\ast}$, let $\tau_{w}$ be the mapping defined by $\tau_{w}(R)=\tau(R,w)$ for all $R\subseteq Q$. Instead of $\tau_{w}(R)$ we often write $R\tau_{w}$.

The automaton $\mathcal{A}$ is said to be deterministic if $|\tau_{a}(q)\rvert=1$ for all $a\in\Sigma$ and all $q\in Q$. In that case $\tau_{a}$ is considered as a mapping of $Q$ into $Q$, that is as a transformation of $Q$ rather than of $2^{Q}$. Inputs $u$ and $v$ of $\mathcal{A}$ are said to be equivalent if and only if $\tau_{u}=\tau_{v}$.

A graph is a pair $G=(N,E)$ with $N$ the set of nodes and $E\subseteq N\times N$ the set of edges. We consider only finite undirected graphs. An edge connecting nodes $n$ and $n^{\prime}$ is given both as $(n,n^{\prime})$ and $(n^{\prime},n)$. Therefore, we require that, for $n,n^{\prime}\in N$, $(n,n^{\prime})\in E$ if and only if $(n^{\prime},n)\in E$ and that these represent the same edge. Thus, any two nodes can be connected by at most one edge. A path is a sequence of nodes $n_{0},n_{1},...,n_{k}$ such that for $0\leq i<k$ the pair $(n_{i},n_{i+1})\in E$.

A weight function for $G$ is a mapping $w:N\times N\to\mathbb{N}_{0}$ satisfying

A weighted graph is a triple $(N,E,w)$ such that $(N,E)$ is a graph and $w$ is a weight function.

For a node $n$, the set $V(n)=\{n^{\prime}\mid(n,n^{\prime})\in E\}$ is the vicinity of $n$. The degree of $n$ is $d(n)=|V(n)|$, and the weight of $n$ is $w(n)=\sum_{n^{\prime}\in V(n)}w(n,n^{\prime})$. A node $n$ is said to be isolated if $d(n)=0$, exterior if $d(n)=1$, and interior if $d(n)>1$.

We now provide several definitions regarding soliton automata.

A soliton graph is an abstraction of a polyacetylene molecule. Carbon atoms are represented as interior nodes, and connections to surrounding structures are represented as exterior nodes. When drawing soliton graphs, we use letters for interior nodes and numbers for exterior nodes. Just like in polyacetylene, only single and double bonds are allowed. In the graph, single bonds are represented as edges with a weight of $1$, and double bonds are represented as edges with a weight of $2$. We draw an edge of weight $1$ as a simple line and an edge of weight $2$ as two parallel lines. The conditions regarding weight and degree imply that the two edges at a node of degree $2$ must have different weights, and that, of the three edges meeting at a node of degree $3$, two must have weight $1$ and one must have weight $2$. An example of a soliton graph is depicted in Figure 1.

In [2] it has been reasoned about properties of the abstract model. The derived properties can be summarized as follows:

• (I)

  One can insert and extract solitons at exterior nodes.

• (II)

  Solitons move at a constant speed and have to move in every step. The speed is measured discretely as moving from one node to another one.

• (III)

  Solitons move at the same speed, which is why solitons cannot overtake each other on the same path.

• (IV)

  Solitons move over edges of alternating weights.

• (V)

  When a soliton travels along an edge of weight $w$, the weight of the edge changes to $3-w$.

• (VI)

  A soliton does not travel along the same edge twice in immediately consecutive steps.

• (VII)

  Multiple solitons cannot travel along the same edge in the same step.

Let $G$ be a soliton graph, let $X$ be the set of its exterior nodes and $S=X\times X$. Then any set $B\subseteq\mathcal{B}(S)$ is called a set of bursts for $G$. The pair $s_{i}\in S$ contains the two nodes the $i$th soliton enters and leaves the graph through, respectively. A burst of the form $s_{1}\|_{k_{1}}s_{2}\|_{k_{2}}\cdots s_{m-1}\|_{k_{m-1}}s_{m}\bot$ is to be interpreted as follows. If the burst is initiated at time $t$, the symbol $s_{1}$ is input at time $t$; $s_{2}$ is input at time $t+{k_{1}}$; and, in general, $s_{j}$ is input at time $t+\sum_{i=1}^{j-1}k_{i}$. Here the empty sum is defined to be 0. The symbol $\bot$ indicates that the input process pauses until the system has stabilized.

If $\pi$ is a position map for $m$, then $\pi(i)$ indicates at which node the $i$th soliton is or how many steps are still required until it will enter the graph. Thus $\pi(i)=1$ means that the ith soliton will enter the graph in the next step. $\pi(i)=n$ with $n\in N$ means that the soliton is at node $n$. $\pi(i)=0$ means, by definition, that the $i$th soliton has left the graph.

For example, let

be a burst. Then $\pi_{b}$ is given by the following table:

This means that the first two solitons start at node $n_{1}$ and $n_{2}$, respectively. The other solitons have to wait for $3$ or $4$ time steps.

The processing of a burst starts with its initial position map and ends with a final position map corresponding in terms of the number of solitons. Small intermediate steps occur leading from the initial position map to the final position map. A burst is successful if and only if all its solitons have left the soliton graph after a finite amount of time.

This ensures that the waiting times of the solitons are reduced in every step, solitons enter the graph at the right node, they have to use an edge in order to reach the next node, and that $0$ is a value in the position map if the corresponding soliton reached the exterior node it is supposed to leave the graph through.

A configuration defines the weights of the current graph and the positions of the solitons for a certain time step. Note that the graph in a configuration need not be a soliton graph. It represents the situation when all solitons have reached the ”next” nodes on their ways. Consider, for example, the soliton graph in Figure 1. If a soliton entered the graph at node $1$ and has reached node $h$, the weight of edge $(1,h)$ has changed to $2$; thus $w(h)=5$.

The conditions above ensure that all solitons behave exactly as defined in the rules concerning soliton movements. A consequence of the condition that no two solitons can traverse the same edge at the same time is that they also cannot enter the same exterior node at the same time. This holds true both for exterior nodes used as entry points and those used as exit points. Two solitons can be at an interior node simultaneously, but must leave it on different edges. Moreover, they cannot simply swap places.

Every element of $\mbox{{Result}}(G,b)$ is again a soliton graph.

Let $B\subseteq\mathcal{B}(X\times X)$ be a set of bursts. Let

For $i\in\mathbb{N}_{0}$, let

and

We can use the resulting soliton graphs we obtain by traversing total legal configuration trails as states of an automaton. Such an automaton is induced by an underlying soliton graph and a set of bursts.

Note that $\mbox{{States}}(G,B)$ is bounded, as the set of vertices and the set of edges do not change, only the weights do. Therefore, there is a finite set $B$ of bursts such that $\mbox{{States}}(G,B)=\mbox{{States}}(G,B^{\prime})$ for all sets $B^{\prime}$ of bursts with $B\subseteq B^{\prime}$. If there is no risk of confusion, a $B$-soliton automaton will be called multi-soliton automaton or simply soliton automaton.

Now we define different kinds of determinism for soliton automata.

A soliton automaton is deterministic if there is exactly one successor state for each state in the set $\mbox{{States}}(G,B)$ and each burst in $B$. Strong determinism is an even stronger constraint, as it also restraints in how many ways it is possible to transition from one state into another. An automaton has this kind of determinism if there is at most one total legal configuration trail for each state in $\mbox{{States}}(G,B)$ and each burst in $B$.

By definition, all total legal configuration trails are considered as transitions between the automaton’s states. There are, however, cases in which an infinite number of configuration trails are possible for a state and a burst. For example, a soliton can get into a situation where it has the possibility to traverse a cycle infinitely many times. Since configuration trails for those kinds of situations contain ”unnecessary” repetitions, we aim to classify configuration trails into two categories: perfect and imperfect. In order to determine when a configuration trail becomes imperfect, we search for equivalent configurations in it. Therefore, we first need to describe when two configurations are called equivalent.

A configuration trail is perfect, if there are no two occurrences of successor-equivalent configurations in it. In the other case, we define it as imperfect, because then it would contain unnecessary steps. Consider the case of a configuration trail with two successor-equivalent configurations $(G_{i},\pi_{i})$ and $(G_{j},\pi_{j})$. We could make the exact same next moves after time step $i$ and $j$, so we might as well cut out all the configurations from $(G_{i+1},\pi_{i+1})$ until $(G_{j},\pi_{j})$. In [3] it is shown that considering only perfect configuration trails in the construction of a soliton automaton does not change its set of states. Also, if an imperfect configuration trail exists in a soliton automaton it can not be strongly deterministic.

Let $G$ be the soliton graph from configuration $1$ in Figure 2 and let $B=\{(1,1)\bot\}$. In [4] it is shown that the $B$-soliton automaton $\mathcal{A}_{B}(G)$ is strongly deterministic. On the other hand, by using the set of bursts $B^{\prime}=\{(1,1)\|_{1}(1,1)\bot\}$ the automaton $\mathcal{A}_{B^{\prime}}(G)$ is not strongly deterministic. This is due to the white soliton having two possible successor positions in configuration $11$. It could move to node $b$, like in configuration $12$, or it could move to node $d$, resulting in both solitons staying inside the cycle. Eventually, this configuration trail would lead to a configuration successor-equivalent to configuration $11$ and can therefore be classified as imperfect. However, for this graph and this burst we cannot find any perfect total legal configuration trails, except from the trail continued from configuration $12$. In order to further discriminate such situations we introduce the following property.

The automaton $\mathcal{A}_{B^{\prime}}(G)$ from our example is perfectly deterministic, but not strongly deterministic. Hence, perfect determinism lies ”in between” determinism and strong determinism.

Distinct soliton automata that are not deterministic may be different ”distances” away from fulfilling the determinism property. We now formulate a measure of descriptional complexity that quantifies this distance.

Proof. For $g\geq 1$, let $G_{g}=(N_{g},E_{g},w_{g})$ be the soliton graph with exactly two exterior nodes 1 and 2 and a path $1,n_{1},n_{2},\ldots,n_{2g-1},n_{2g}$ with $w_{g}(1,n_{1})=1$ which we will call basic chain in the sequel. Moreover, additional edges leave the basic chain at every other node of the basic chain:

The edges leaving the basic chain all lead to the exterior node 2 and belong to a sub-graph forming a binary tree with $n_{2},n_{4},\ldots,n_{2g}$ as leaves and node 2 as its root, in which the root has weight 2 and branching edges always have weight 1. The inner nodes of that tree are denoted by $v_{1},\ldots,v_{r}$ with $r=2g-3$ (if $g>1$). There is an edge $(n_{2},v_{1})$ with weight 1 and, for $1<k\leq g$, there is an edge $(n_{2k},v_{2k-3)}$ with weight 1. The first three soliton graphs $G_{1},G_{2},G_{3}$ are depicted in Figure 3.

Further, let $B=\{(1,2)\bot\}$. Since the soliton has a non-deterministic choice only on every node $n_{2k}$ of the basic chain, $1\leq k<g$, there are exactly $g$ soliton paths for the soliton in $B$. Notice that once the soliton has left the basic chain it has to follow the path leading directly to node 2 since it enters a node with degree 3 only when it has just traversed an edge with weight 1. Thus, $|\mbox{{Result}}(G_{g},B)\rvert\leq g$. The soliton uses exactly one of the edges $(n_{2},v_{1})$ or $(n_{2k},v_{2k-3})$, $1<k\leq g$, and the weight of the used edge has turned to 2 whereas the other edges leaving the basic chain keep their weight 1. Consequently, $|\mbox{{Result}}(G_{g},B)\rvert=g$.

Next, we prove $\mbox{{Result}}(G^{\prime},B)=\{G_{g}\}$ for all $G^{\prime}\in\mbox{{Result}}(G_{g},B)$ and every $g\geq 1$. Assume the soliton has used edge $(n_{2k},v_{2k-3})$ in $G_{g}$, for some $k$, $1<k\leq g$ (the case $k=1$, when it has used $(n_{2},v_{1})$, is similar). Then, the resulting soliton graph $G^{\prime}$ is of the form

In $G^{\prime}$, every soliton path for burst $(1,2)\bot$ has the prefix $1,n_{1},n_{2},\ldots,n_{2k},v_{2k-3}$. Now, this path can be continued with $v_{2k-2},v_{2k-1},\ldots,2$ leading directly to node 2, and the resulting soliton graph is $G_{g}$. Alternatively, the soliton can use edge $(v_{2k-3},v_{2k-4})$ (or, if $k=1$, edge $(v_{1},n_{4}))$, or it can use $(v_{2k-3},v_{2k-2})$ and later an edge with weight 1 leading back towards the basic chain (which has the same weights as in $G_{g}$ now). In any such case, some node $n_{j}$ of the basic chain will be reached via an edge with weight 1. Therefore, the soliton has to use the edge $(n_{j},n_{j-1})$ next, leading ”to the left” in the basic chain. Now, it cannot reach node 2, because every node $n_{\ell}$ in the basic chain having degree 3 is reached via an edge with weight 1 and has to be left to $n_{\ell-1}$ since $w(n_{\ell},n_{\ell-1})=2$. Therefore, no further soliton graphs are added to $\mbox{{Result}}(G^{\prime},B)$.

In conclusion, $|\mbox{{Result}}(G^{\prime},B)\rvert=1$ for all $G^{\prime}\in\mbox{{Result}}(G_{g},B)$ and $g$ is the smallest integer with $|\mbox{{Result}}(G,B)\rvert\leq g$ for all $G\in\mbox{{States}}(G_{g},B)$. Hence, the degree of nondeterminism of $\mathcal{A}_{B}(G_{g})$ is $g$, for every $g\geq 1$. $\Box$

So far, we defined determinism properties only on soliton automata. We now extend our definitions to soliton graphs.

For our statements about graph determinism it is important to consider soliton graphs that can not be decomposed into independent sub-graphs. In the case of a single wave, meaning the case of a single soliton traversing a soliton graph, impervious paths may appear. A path is impervious if none of its edges is used by the soliton in any configuration trail [4]. An example of an impervious path is the path h-i-j-k in Figure 1. The soliton has to enter the soliton graph either via node $1$ or node $2$, hence by traversing an edge with weight $1$. Since it has to use an edge with weight $2$ next, it can only move towards the cycle on the respective side. On its way back, on node h or k, respectively, it has to traverse an edge with weight $2$ in the next step, still not allowing it to enter the path h-i-j-k and forcing it to leave the soliton graph via the node it entered the graph through. In order to formalize this idea for the case of multiple solitons being present we give the following definitions.