We study interrelations between symbolic descriptions of concurrently evolving systems and underlying sequential dynamics. We focus our interests on minimal shifts and t-shifts generated by them, assuming that an independence relation is given by a five vertex co-graph.
In [
The problem is well known in the theory of computing.
Namely, a one-tape Turing machine is equivalent, in the
sense of a computational power, to a Turing machine with
multiple tapes. However, if we analyze moves of the tape
then a “simple” computation of a multi-tape machine may
force quite “complex” behavior of a one-tape machine
during a simulation process. Some attempts have been made
for the better understanding of relations between
dynamics of computation and computation process itself -
compare [
Our recent results are published in [
Now we recall only basic concepts of graph theory,
symbolic dynamics and theory of traces. All the missing
notions may be found in [
We consider only simple and finite graphs. By a cograph we understand either a single vertex graph, or the disjoint union of two co-graphs, or the edge complement of a co-graph.
Let Σ be any finite set (alphabet) and denote by Σ∗ and Σω the set of all finite and infinite words over Σ, respectively. The set Σ∗ with concatenation of words and the empty word, denoted 1 is a free monoid. The set of nonempty words is denoted by Σ+ and Σ∞ = Σ∗ ∪ Σω .
Let I ⊂ Σ × Σ be a symmetric and irreflexive relation. In the sequel I is called an independence (commutation) relation; its complement is denoted by D and called a dependence relation. For every letter a ∈ Σ we denote by D(a) = { b ∈ Σ : (a, b) ∈/ I} , a set of all letters from Σ which depend on a. The relation I may be extended to a congruence ∼I on Σ∗. We have u ∼I v if and only if it is possible to transform u to v by a finite number of swaps ab → ba of independent letters. A trace is an element of the quotient space M(Σ, I) = Σ∗/ ∼I . For w ∈ Σ∗, t ∈ M(Σ, I) we denote by | w | a and | t | a the number of occurrences of the letter a ∈ Σ in w and t respectively. al ph(w) and al ph(t) denote the set of all letters which occur in w, t. Two traces t1 and t2 are independent, denoted t1It2, if and only if al ph(t1) × al ph(t2) ⊂ I. If x ∈ Σω and i ≤ j are nonnegative integers then we denote x[i, j] = xixi+1 . . . x j and x[i, j) = x[i, j−1].
We recall that a word w ∈ Σ∗ is in the Foata normal form, if it is the empty word or if there exist an integer n > 0 and nonempty words v1, ..., vn ∈ Σ+ (called Foata steps) such that: 1. w = v1.....vn, 2. for any i = 1, ..., n the word vi is a concatenation of pairwise independent letters and is minimal with respect to the lexicographic ordering, 3. for any i = 1, ..., n − 1 and for an arbitrary letter a ∈ al ph(vi+1) there exists a letter b ∈ al ph(vi) such that (a, b) ∈ D.
It is well known that for any x ∈ Σ∗ there exists the unique w ∈ [x]∼I in the Foata normal form.
In the theory of dynamical systems continuous maps acting on metric spaces are considered. Hence we endow Σω with the following metric d. If x = y then d(x, y) = 0 and otherwise d(x, y) = 2− j where j is the number of letters in the longest common prefix of x and y. Now, define a shift map σ : Σω → Σω by
(σ (x))i = xi+1 where (· )i denotes the i-th letter of a sequence. It is easy to observe that σ is continuous. Σω together with the map σ is referred to as the full shift over Σ. Any closed and σ -invariant (i.e. σ (X ) ⊂ X ) set X ⊂ Σ is called a shift or a subshift.
For any word w = (wi)i∈N ∈ Σω the dependence graph φ G(w) = [V, E,λ ] is defined as follows. We put V = N and λ (i) = wi for any i ∈ N. The function λ successively labels nodes of φ G(w) by letters of w. There exists an arrow (i, j) ∈ E, if and only if i < j and (wi, w j ) ∈ D. Let us denote the set of all possible dependence graphs (up to an isomorphism of graphs) by Rω (Σ, I) and let φ G : Σω ements o→fRωR(ωΣ(,ΣI,)Ii)nfibneitae n(raetuarl)altrparcoejse.cEtiaocnh. dWepeecnadlelneclegraph is acyclic and it induces a well-founded ordering on N. Then for any v ∈ V the function h : V → N given by h(v) = max P (v) where P (v) = { n ∈ N : ∃v1, .., vn ∈ V, vn = v, (vi, vi+1) ∈ E for i = 1, ..., n − 1} is well defined.
By Fn(t) we denote a word w ∈ Σ∗ consisting of all the
letters from the n-th level of infinite trace t ∈ Rω (Σ, I),
that is from the set { λ (v) : v ∈ V, h(v) = n} . It follows
from the definition of a dependence relation that for any
infinite trace t ∈ Rω (Σ, I) the word w = F1(t) . . . Fn(t) is
in the Foata normal form with Foata steps given by Fi(t)
and t = φ G(F1(t)F2(t) . . .). Then in the same way as it
was done for Σω we may endow Rω (Σ, I) with a
metric dR(s, t) putting dR(s, t) = 0 if s = t and dR(s, t) =
2− j+1 if s 6= t where j is the maximal integer such that
Fi(t) = Fi(s) for 1 ≤ i ≤ j. By a full t-shift we mean
the metric space (Rω (Σ, I), dR) together with a
continuous map Φ : Rω (Σ, I) → Rω (Σ, I) defined by the formula
Φ(t) = φ G(F2(t)F3(t) . . .) for any t ∈ Rω (Σ, I).
Analogically as a shift is defined, by a t-shift we mean any closed
and Φ-invariant subset of Rω (Σ, I). It was proved in [
Let (X , d) be a compact metric space and let f : X → X be continuous. A point y ∈ X is said to be an ω -limit point of x if it is an accumulation point of the sequence x, f (x), f 2(x), . . . . The set containing all elements of the sequence x, f (x), f 2(x), . . . is called an orbit of x and denoted by Orb+(x). The set of all ω -limit points of x is referred to as ω -limit set of x and denoted by ω (x, f ). A point x is said to be periodic (fixed) if f n(x) = x for some n ≥ 1 (n = 1) and is said to be recurrent if x ∈ ω (x, f ). If x is not periodic (fixed) point but f m(x) is periodic (fixed) for some positive integer m then we say that x is eventually periodic (fixed). A subset M of X is minimal if it is closed, nonempty, invariant (i.e. f (M) ⊂ M) and contains no proper subset with these three properties. It is well known that if a nonempty closed set M ⊂ X is minimal then the orbit of every point of M is dense in M. We recall that a point x is referred to as minimal (or almost periodic) if it belongs to a minimal set.
Let X and Y be compact metric spaces and let f : X → X and g : Y → Y be continuous maps. If there is a homeomorphism ϕ : X → Y with ϕ ◦ f = g ◦ ϕ, we will say that f and g are (topologically) conjugate and π is called a (topological) conjugacy. If there is a conjugacy from X to Y then Y is sharing all properties of X . Not formally we can think about these two shifts as they are the same.
Let X be a closed and σ -invariant subset of Σω . We define the set Bn(X ) of n admissible words for X by:
Bn(X ) = x[i,i+n) ∈ Σ∗ : x ∈ X , i ∈ N .
Let w ∈ Σ∗. The set of all subwords of w with the length equal to n is denoted by
Sn(w) = { u ∈ Bn(Σ∗) : ∃ v1, v2 ∈ Σ∗ , w = v1uv2} . We may extend canonically the definition of Sn to the case of x ∈ Σω , i.e. given x ∈ Σω we define:
Sn(x) = u ∈ Bn(Σ∗) : ∃ i , u = x[i,i+n) .
The least integer m (if it exists) such that for any w ∈ Bm(X ) it holds that Sn(w) = Sn(x) is called the n-th recurrency index of x in X and is denoted by R(n, x, X ). If such m does not exist we put R(n, x, X ) = +∞. In the case of X = cl(Orb+(x)) we will simplify the notation writing R(n, x) instead of R(n, x, cl(Orb+(x))) where cl(A) denotes the closure of a set A. Let us recall some facts on recurrency indices.
Theorem 1 ([17, Thm. 7.2]). Let x ∈ Σω . The following conditions are equivalent:
2. R(n, x) < +∞ for all positive integers n.
Theorem 2 ([17, Thm. 7.1]). If M ⊂ Σω is a minimal set, then R(n, x) = R(n, y) for any x, y ∈ M and n ∈ N.
Let us consider an independence alphabet (Σ, I) and let
A be the set of all nonempty words over Σ which are
products of pairwise independent letters and are minimal with
respect to the lexicographical ordering of Σ. Hence an
element of A is a Foata step which may occur in some Foata
normal form of a word (finite or not) over (Σ, I). We
define a graph G (Σ, I) putting V = A as the vertex set and
defining the set of edges E ⊂ V × V as follows. A pair
((a1 . . . ak), (b1 . . . bl)) is in E if for any 0 ≤ j ≤ k there
exists 1 ≤ i ≤ l such that (a j, bi) ∈ D. It is well known that
the set
XG (Σ,I) = { a0a1 . . . ∈ A ω : (ai, ai+1) ∈ E for i = 0, 1, . . . }
is a shift space over A and it was proved in [
Given a trace t ∈ Rω (Σ, I) we define an n-th recurrency index of t by R(n,t) = R(n,π (t)). 3
In our paper [
We start our presentation with two useful theorems.
Theorem 3 ([
I = ((Σ × Θ) ∪ (Θ × Σ)) \ ΔΣ, where ΔΣ = { (a, a) : a ∈ Σ} .
Let π : Σω → (Σ \ Θ)∞ be a projection π (a) = (1 if a ∈ Θ
a if a ∈/ Θ Then φ G(X ) and π (X ) are t-shift and shift respectively, they are conjugated and (π (X ),σ ) is minimal.
The proof of a subsequent assertion is a modified
version of the original one in [
Theorem 4. Let X be a minimal shift, al ph(X ) = Σ. Let Σ1, Σ2 be a partition of Σ and assume that Σ1 × Σ2 ⊂ D. Then there exists an integer M such that the sets
M Y = [ Φi(φ G(X )), i=0
Z = ΦM(Y ). are t-shifts. Furthermore t-shift (Z, Φ) is minimal. Proof. We will show that φ G(x) is a minimal point for some x ∈ X . Let us fix an infinite word x = x0x1 . . . ∈ X such that x0 ∈ Σ1 and x1 ∈ Σ2 what is possible according to the minimality of X . It follows from the assumption that for every i = 0, 1, ... any Foata step Fi(x) is a word in Σ∗1 or Σ∗2 exclusively, that is if al ph(Fi(x)) ∩ Σ j 6= 0/ then Fi(x) ∈ Σ∗j where j = 1, 2.
Now, let us fix a point x = x0x1 . . . ∈ X such that x0 ∈ Σ1 and x1 ∈ Σ2. We will show that φ G(x) is a minimal point. In the word x there exist letters x j1 , x j2 ∈ Σ1 and x j1+1, x j2−1 ∈ Σ2 for some j1 < j2. Then x j1 and x j2 determine some Foata steps, in the sense that x j1 ∈ Fi1 (x) and x j2 ∈ Fi2 (x) respectively for some i1 < i2. All the intermediate steps are uniquely determined by the intermediate letters, that is Fi(x) = Fi−i1 (x( j1, j2)) for every i1 < i < i2 - by the definition of I and according to the fact that x j1 , x j2 ∈ Σ1 and x j1+1, x j2−1 ∈ Σ2 it is not allowed to move any intermediate letter outside two-sided boundary given by the letters x j1 , x j2 . Now, let us introduce the following notation M = sup n : ∃ i, xi, xi+n ∈ Σ1, Σ1 ∩ al ph(x(i,i+n)) = 0/ . M is finite since X is minimal, in particular M ≤ 2R(x, 1). For any positive integers i, s there exist indices i1 ≤ i, i ≤ i2 − s such that i1 − i ≤ M, i2 − i − s ≤ M and Fi1 (x), Fi2 (x) ∈ Σ∗2 and Fi1−1(x), Fi2+1(x) ∈ Σ∗. In partic1 ular, this implies that all the steps Fi1 (x), . . . , Fi2 (x) are uniquely determined by some subword u of x with the length | u| < (2M + s + 2)| Σ| . But from the minimality of x each subword of x with the length R((2M + s)| Σ| , x) contains u as a subword. Additionally Fi+1(x) = Fi(σ (x)) and F0(x) = x0 ∈ Σ1. Finally
R(s,φ G(σ (x))) ≤ R((2M + s)| Σ| , x)
and then φ G(σ (x)) is a minimal point. If we fix y ∈ X with
∞
y0 ∈ Σ1 then there exists an increasing sequence { ik} k=1
such that limk→∞ σ ik (x) = y. In particular, we may assume
that x[ik,ik+1] = y[
Now let us consider five letter alphabet and an independence relation given by a co-graph of order 5. We devide the set of 24 mentioned co-graphs into three subclasses according to their properties in order to facilitate analysis of the situation.
Theorem 5. Let the independence relation I be represented by a co-graph G.
1. If G belongs to subclass I (Fig.1), then there exists a positive integer M and Y = SiM=0 Φi(φ G(X )) is a t-shift and Z = ΦM(Y ) is a minimal subshift. 2. If G belongs to subclass II (Fig.2), then two cases can occur. The first one is described in statement 1. and in the second one φ G(X 0) is a minimal subshift.
• subclass I
If the relation I is represented by any graph belonging to subclass I (see Fig. 1), • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • then there exists at least one letter (denote it by a) which is in relation D with any other letter. Then we can apply Theorem 4 because Σ1 = { a} , Σ2 = Σ \ { a} fulfill the assumptions of the mentioned theorem. In particular, Y = SiM=0 Φi(φ G(X )) is a t-shift and after a finite number of iterations it becomes a minimal subshift Z = ΦM(Y ), where M is a positive integer which depends on the structure of X . In fact, exactly the same situation holds for the last two graphs from this subclass, but now Σ is decomposed into two sets containing two and three letters respectively. • subclass II
If the relation I is represented by any graph depicted at Fig 2, then there is at least one letter which is independent with any other letter.
Then by Theorem 3 φ G(X ) is homeomorphic to φ G(X 0) where X 0 is obtained from X by removing this particular letter. But this transformation allows us to modify the independence relation by removing exactly the same letter from I. Finally we obtain two cases. The first that allows to apply Theorem 4, and • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • the second in which a form of the relation I obviously implies that φ G(X 0) is minimal (for example I consisted of five isolated vertices).
One can see that the previous Theorem does not consider two remaining co-graphs on five vertices depicted in Fig. 3.
• • •
• • • • • • • Unfortunately in this case we are unable to give any general description. So this case remains open for a further research.
Acknowledgement This work is the result of the project implementation: Research and Education at UPJŠ - Heading towards Excellent European Universities, ITMS project code: 26110230056, supported by the Operational Program Education funded by the European Social Fund (ESF).
The research of the second author was partially supported by Slovak APVV grant APVV-0035-10 and Slovak VEGA grant 1/0479/12.