# An Application of Iterative Pushdown Automata  to Contour Words of Balls and Truncated Balls in Hyperbolic Tessellations

Authors: Maurice Margenstern
Journal: ISRN Algebra
 (2012)

---

## Abstract

We give an application of iterated pushdown automata to contour words of balls and two other domains in infinitely many tilings
of the hyperbolic plane. We also give a similar application for the tiling{5,3,4} of the hyperbolic 3D space and for the tiling {5,3,3,4} of the hyperbolic 4D space as well.


---

## Body

## 1. Introduction

Iterated pushdown automata were introduced in [1, 2] and we refer the reader to [3] for references and for the connection of this topic with sequences of rational numbers. By their definition, iterated pushdown automata are more powerful than standard pushdown automata, but they are far less powerful than Turing machines. As Turing machines can be simulated by a finite automaton with two independent stacks, iterated pushdown automata can be viewed as an intermediate device, see also [4] for other connections of automata with graph algebras.In this paper, we show an application of this device to the characterization of contour words of a family of bounded domains in many tilings of the hyperbolic plane. We do the same kind of application for a tiling of the hyperbolic 3D space and for another one in the hyperbolic 4D space. These two latter applications cannot be generalized to any dimension as, starting from dimension 5, there is no tiling of the hyperbolic space which would be a tessellation generated by a regular polytope.In Section2, we remember the definition of iterated pushdown automata with an application to the computation of the recognition of words of the form afn, where {fn}n∈ℕ is the Fibonacci sequence with f0=f1=1. This sequence will always be denoted by {fn}n∈ℕ in all the paper.In Section3, we remind the reader about several features and properties on tilings of the hyperbolic plane.In Section4, we define the contour words which we are interested in and we construct iterated pushdown automata which recognize them for the case of the pentagrid and the heptagrid, that is, the tilings {5,4} and {7,3} of the hyperbolic plane. In the same section, we extend these results to infinitely many tilings of the hyperbolic plane.In Section5, we extend the result to two tilings of the 3D and 4D hyperbolic spaces.


## 2. Iterated Pushdown Automata

In this section, we fix the notations which will be used in the paper. We follow the notations of [3].


### 2.1. Iterated Pushdown Stores

This data structure is defined by induction, as follows:(2.1)0-pds(Γ)={ϵ},k+1-pds(Γ)=(Γ[k-pds(Γ)])*,it-pds(Γ)=∪kk-pds(Γ).The elements of ak+1-pds(Γ) structure are k-pds(Γ) structures, and each element is labelled by a letter of Γ. A k-pds(Γ) structure will often be called a k-level store, for short. When k is fixed, we speak of outer stores and of inner stores in a relative way: an i-level store is outer than a j-one if and only if i<j. In the same situation, the j-level store is inner than the i-one.We define functions and operations onk-level stores, by induction on k.From the above definition, we get that ak+1-level store ω can be uniquely represented in the form:(2.2)ω=A[flag]⋅rest,
where A∈Γ, flag is a k-level store, and rest is k+1-store. Moreover, if ℓ is the number of elements of rest, the number of elements of ω is ℓ+1.A first operation consists in defining the generalization of the standard notion oftop symbol in an ordinary pushdown structure. This is performed by the function topsym defined by(2.3)topsym(ϵ)=ϵ,topsym(A[flag]⋅rest)=A⋅topsym(flag).It is important to remark thattopsym is the single direct access to all inner stores of a k-level store. In other words, for any inner store, only its topmost symbol can be accessed and when this inner store is in the top of the outmost store.Also note that thetopsym function performs a reading. There are two families of writing operations, also concerning the elements visible from the topmost function only.The first one consists of the pop operations defined by the following induction:popj(ϵ)isundefined,popj+1(A[flag]·rest)=A·[popj(flag)]·rest.The second family consists of the push operations defined by the following induction:push1(γ)(ϵ)=γ,forγ∈Γ,pushj(γ)(ϵ) is undefined for j>1,pushj+1(w)(A[flag]·rest)=w1[flag]…wk[flag]·rest, where w=w1…wk, with wi∈Γ for 1≤i≤k.


### 2.2. Iterated Pushdown Automata

Intuitively, the definition is very close to the traditional one of standard nondeterministic standard automata. Ak-iterated pushdown automaton is defined by giving the following data:(i)
a finite set of states,Q,(ii)
an input finite alphabetΣ,(iii)
a store finite alphabetΓ,(iv)
a transition functionδ from Q×Σ∪{ϵ}×Γk into a finite set of instructions of the form (q,op), where q is a state and op is a pop or a push operation as described in the previous subsection.We also assume that there is an initial state denoted byq0 and that the initial state of the store is Z[ϵ], where Z is a fixed in-advance symbol of Γ. Note that we allow ϵ-transition which plays a key role.A configuration is a word of the form(q,w,ω), where q is the current state of the automaton, w is the current word, and ω is the current k-level store of the automaton. A computational step of the automaton allows to go from one configuration to another by the application of one transition. In order to apply a transition, the current state of the automaton must be that of the transition, the first letter of w must be the symbol of Σ in the transition if any, and topsym(ω) must be the word of Γk in the transition if any. A word w is accepted if and only if there is a sequence of computational steps starting from (q0,w,Z[ϵ]) to a first configuration of the form (q,ϵ,ϵ). The language recognized by a k-iterated pushdown automaton is the set of words in Σ* which are accepted by the automaton.


### 2.3. An Example: The Fibonacci Sequence

As an illustrative example of the working of such an automaton, we take the set of words of the formafn, where {fn}n∈ℕ is the Fibonacci sequence. This language is recognized by a 2-iterated pushdown automaton as proved in [3]. Here, we give the automaton and a proof of its correctness.The proof is based on the following lemma.Lemma 2.1.
One has the following relations, for any nonnegativek:
(2.4)(q0,afk,X2[Fk]⋅ω)⟹δ*(q0,ϵ,ω),(q0,afk+1,X1[Fk]⋅ω)⟹δ*(q0,ϵ,ω).Proof.
It is performed by induction whose basic casek=0 is easy. If we start from (q0,afk+1,X1[Fk]·ω), we have the following derivation:
(2.5)(q0,afk+2,X1[Fk+1]⋅ω)⊢(q1,afk+2,X1[Fk]⋅ω)⊢(q0,afk+2,X1[Fk]⋅X2[Fk]⋅ω)⊢(q0,afk,X2[Fk]⋅ω)
by induction hypothesis as fk+2=fk+1+fk. And, again by induction hypothesis.
(2.6)(q0,afk,X2[Fk]⋅ω)⊢(q0ϵ,ω).
Similarly,(2.7)(q0,afk+1,X2[Fk+1]⋅ω)⊢(q2,afk+1,X2[Fk]⋅ω)⊢(q0,afk+1,X1[Fk]⋅ω)⊢(q0,ϵ,ω),
by induction hypothesis.
Letam be the initial word. With the first two transitions, we guess an integer k such that m=fk if any. Then we arrive at the configuration (q0,am,Z[Fk]). Next, we have
(2.8)(q0,am,Z[Fk])⊢(q0,am,X2[Fk]).
And by the lemma, we proved that (q0,am,X2[Fk])⊢(q0,ϵ,ϵ) and so the word is accepted.
We can see that ifm=fk and if we guessed a wrong k, then either the word is not empty when the store vanishes, and we cannot restore it, or the word is empty as the store is not. This also shows that if m≠fk, as there is in this case a unique k such that fk<m<fk+1, we always have either an empty word an a nonempty store or an empty store with a nonempty word, whatever the guess.


## 2.1. Iterated Pushdown Stores

This data structure is defined by induction, as follows:(2.1)0-pds(Γ)={ϵ},k+1-pds(Γ)=(Γ[k-pds(Γ)])*,it-pds(Γ)=∪kk-pds(Γ).The elements of ak+1-pds(Γ) structure are k-pds(Γ) structures, and each element is labelled by a letter of Γ. A k-pds(Γ) structure will often be called a k-level store, for short. When k is fixed, we speak of outer stores and of inner stores in a relative way: an i-level store is outer than a j-one if and only if i<j. In the same situation, the j-level store is inner than the i-one.We define functions and operations onk-level stores, by induction on k.From the above definition, we get that ak+1-level store ω can be uniquely represented in the form:(2.2)ω=A[flag]⋅rest,
where A∈Γ, flag is a k-level store, and rest is k+1-store. Moreover, if ℓ is the number of elements of rest, the number of elements of ω is ℓ+1.A first operation consists in defining the generalization of the standard notion oftop symbol in an ordinary pushdown structure. This is performed by the function topsym defined by(2.3)topsym(ϵ)=ϵ,topsym(A[flag]⋅rest)=A⋅topsym(flag).It is important to remark thattopsym is the single direct access to all inner stores of a k-level store. In other words, for any inner store, only its topmost symbol can be accessed and when this inner store is in the top of the outmost store.Also note that thetopsym function performs a reading. There are two families of writing operations, also concerning the elements visible from the topmost function only.The first one consists of the pop operations defined by the following induction:popj(ϵ)isundefined,popj+1(A[flag]·rest)=A·[popj(flag)]·rest.The second family consists of the push operations defined by the following induction:push1(γ)(ϵ)=γ,forγ∈Γ,pushj(γ)(ϵ) is undefined for j>1,pushj+1(w)(A[flag]·rest)=w1[flag]…wk[flag]·rest, where w=w1…wk, with wi∈Γ for 1≤i≤k.


## 2.2. Iterated Pushdown Automata

Intuitively, the definition is very close to the traditional one of standard nondeterministic standard automata. Ak-iterated pushdown automaton is defined by giving the following data:(i)
a finite set of states,Q,(ii)
an input finite alphabetΣ,(iii)
a store finite alphabetΓ,(iv)
a transition functionδ from Q×Σ∪{ϵ}×Γk into a finite set of instructions of the form (q,op), where q is a state and op is a pop or a push operation as described in the previous subsection.We also assume that there is an initial state denoted byq0 and that the initial state of the store is Z[ϵ], where Z is a fixed in-advance symbol of Γ. Note that we allow ϵ-transition which plays a key role.A configuration is a word of the form(q,w,ω), where q is the current state of the automaton, w is the current word, and ω is the current k-level store of the automaton. A computational step of the automaton allows to go from one configuration to another by the application of one transition. In order to apply a transition, the current state of the automaton must be that of the transition, the first letter of w must be the symbol of Σ in the transition if any, and topsym(ω) must be the word of Γk in the transition if any. A word w is accepted if and only if there is a sequence of computational steps starting from (q0,w,Z[ϵ]) to a first configuration of the form (q,ϵ,ϵ). The language recognized by a k-iterated pushdown automaton is the set of words in Σ* which are accepted by the automaton.


## 2.3. An Example: The Fibonacci Sequence

As an illustrative example of the working of such an automaton, we take the set of words of the formafn, where {fn}n∈ℕ is the Fibonacci sequence. This language is recognized by a 2-iterated pushdown automaton as proved in [3]. Here, we give the automaton and a proof of its correctness.The proof is based on the following lemma.Lemma 2.1.
One has the following relations, for any nonnegativek:
(2.4)(q0,afk,X2[Fk]⋅ω)⟹δ*(q0,ϵ,ω),(q0,afk+1,X1[Fk]⋅ω)⟹δ*(q0,ϵ,ω).Proof.
It is performed by induction whose basic casek=0 is easy. If we start from (q0,afk+1,X1[Fk]·ω), we have the following derivation:
(2.5)(q0,afk+2,X1[Fk+1]⋅ω)⊢(q1,afk+2,X1[Fk]⋅ω)⊢(q0,afk+2,X1[Fk]⋅X2[Fk]⋅ω)⊢(q0,afk,X2[Fk]⋅ω)
by induction hypothesis as fk+2=fk+1+fk. And, again by induction hypothesis.
(2.6)(q0,afk,X2[Fk]⋅ω)⊢(q0ϵ,ω).
Similarly,(2.7)(q0,afk+1,X2[Fk+1]⋅ω)⊢(q2,afk+1,X2[Fk]⋅ω)⊢(q0,afk+1,X1[Fk]⋅ω)⊢(q0,ϵ,ω),
by induction hypothesis.
Letam be the initial word. With the first two transitions, we guess an integer k such that m=fk if any. Then we arrive at the configuration (q0,am,Z[Fk]). Next, we have
(2.8)(q0,am,Z[Fk])⊢(q0,am,X2[Fk]).
And by the lemma, we proved that (q0,am,X2[Fk])⊢(q0,ϵ,ϵ) and so the word is accepted.
We can see that ifm=fk and if we guessed a wrong k, then either the word is not empty when the store vanishes, and we cannot restore it, or the word is empty as the store is not. This also shows that if m≠fk, as there is in this case a unique k such that fk<m<fk+1, we always have either an empty word an a nonempty store or an empty store with a nonempty word, whatever the guess.


## 3. The Tilings of the Hyperbolic Plane

We assume that the reader is a bit familiar with hyperbolic geometry, at least with its most popular models, Poincarés’s half-plane and disc.We remember the reader that in the hyperbolic plane, thanks to a well-known theorem of Poincaré, there are infinitely many tilings which are generated by tessellation starting from a regular polygon. This means that, starting from the polygon, we recursively copy it by reflections in its sides and of the images in their sides. This family of tilings is defined by two parameters:p, the number of sides of the polygon, and q, the number of polygons which can be put around a vertex without overlapping and covering any small enough neighbourhood of the vertex.In order to represent the tilings which we will consider and the regions whose contour word will be under study, we will make use of Poincaré’s disc model. Our illustrations will take place in thepentagrid and the heptagrid, that is, the tilings {5,4} and {7,3}, respectively, of the hyperbolic plane. Figures 1 and 2 will illustrate these tilings.(a) the pentagrid. (b) the heptagrid.
(a)(b)(a) the pentagrid. (b) the heptagrid. Note that in both cases, the sectors are spanned by the same tree.
(a)(b)From Figure1,the pentagrid and the heptagrid seem rather different. However, there is a tight connection between these tilings which can be seen from Figure 2. In both pictures of the latter figure, we represent the tiling by selecting a central tile and then by displaying as many sectors as the number of sides of the central tile. In each case, these sectors do not overlap and their union together with the central cell gives the tiling of the whole hyperbolic plane. Now, there is a deeper common point: in both cases, each sector is spanned by a tree which we call a Fibonacci tree for a reason which will soon be explained.As proved in [5, 6], the corresponding tree can be defined as follows. We distinguish two kinds of nodes, say black nodes, labelled by B, and white nodes, labelled by W. Now, we get the sons of a node by the following rules: B→BW and W→BWW, the root of the tree being a white node, see Figure 3. It is not difficult to see that if the root is on level 0 of the tree, the number of nodes on the level k of the tree is f2k+1, where {fk}k∈ℕ is the Fibonacci sequence with f0=f1=1.Figure 3
The standard Fibonacci tree. The nodes are numbered from the root, from left to right on each level and level after level. For each node, the figure displays the representation of the number of the node with respect to the Fibonacci sequence, the representation avoiding consecutive 1s.The Fibonacci tree has a lot of nice properties which we cannot discuss here. In particular, there is a way to locate the tiles of the pentagrid or the heptagrid very easily thanks to coordinates devised from the properties of the Fibonacci tree, see [5–7].


## 4. The Contour Words

Now, we have the tools to define the regions from which we define contour words, and we also have the tools to define the iterated pushdown automata which recognize them.


### 4.1. Balls

Consider a ballBk of radius k+1 in the penta- or the heptagrid. This ball is the union of the central cell and α truncated sectors, α=5 for the pentagrid and α=7 for the heptagrid, each truncated sector being spanned by a Fibonacci tree up to the level k. Accordingly, the number of tiles which are exactly at the distance k+1 from the central cell is α·f2k+1. Denote the set of these tiles by ∂Bk. Figure 4 illustrates ∂B3 in the pentagrid and in the heptagrid.The representation of∂B3. (a) the pentagrid. (b) the heptagrid. In both cases, sw3=bwbwwbww.
(a)(b)Theα sectors around the central cell can be numbered from 1 to α by fixing sector 1 once for all and by counterclockwise turning around the central cell. We call contour wordcwk the word obtained by taking the labels of the tiles which are on ∂Bk, starting from the left-hand side border of sector 1 and by counter clockwise running along ∂Bk, until the tile which is on the right-hand side border of the sector α. It is easy to remark that the contour work cwk can be written as (swk)α, where swk is obtained by taking the word which is on ∂Bk from the left-hand side of the sector to its right-hand side.Already by the length of the contour words, we can see that the set of all contour words is not algebraic: it is enough to apply Ogden’s pumping lemma.Now we have the following theorem.Theorem 4.1.
The contour words of the pentagrid and those of the heptagrid can be recognized by a 2-level pushdown automaton.Proof.
Indeed, we can transform Automaton1 in order to do the job. The new automaton is represented in Automaton 2
For the proof, it is enough to prove that for any nonnegativek(4.1)(q0,bswk,B[Fk]⋅ω)⟹δ*(q0,ϵ,ω),(q0,swk,W[Fk]⋅ω)⟹δ*(q0,ϵ,ω),
where bswk is the word obtained on the level k of a Fibonacci tree whose root is a black node, starting from the left-hand side border to the right-hand side one.
The rest of the easy proof is left to the reader.
However, we can give an idea of the automaton which will better convince the reader.
In fact, the automaton can be seen as a device which traverses the tree in a depth first way. To this purpose, starting from the root whose height isk, the automaton puts on the outer store the nodes it takes, always going to left first. For each node, the automaton puts the labels of the son of the node together with the height of each sons which is stored as an inner store. As the height of the sons is reduced by 1 with respect to that of the father, this is obtained by a simple popping of the inner store. This explains both the construction of the automaton and its correctness.
Of course, the figure of Automaton2 provides us with two automata: one for the pentagrid and one for the heptagrid.Automaton 1:The 2-pushdown automaton recognizing the Fibonacci sequence.
three states:q0, q1 and q2; input word in {a}*; Γ={Z,X1,X2,F};initial state:q0; initial stack: Z[ϵ]; transition function δ:δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(X2))}δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(X2))}δ(q0,ϵ,X1F)=(q1,pop2)δ(q0,ϵ,X2F)=(q2,pop2)δ(q0,a,X1)=(q0,pop1)δ(q0,a,X2)=(q0,pop1)δ(q1,ϵ,X1F)=(q0,push1(X1X2))δ(q2,ϵ,X2F)=(q0,push1(X1))δ(q1,ϵ,X1)=(q0,push1(X1X2))δ(q2,ϵ,X2)=(q0,push1(X1))Automaton 2:The 2-pushdown automaton recognizing the contour word of a ball in the pentagrid or in the heptagrid.
two states:q0 and q1; input word in {b,w}*; Γ={Z,B,W,F};initial state:q0; initial stack: Z[ϵ]; transition function δ:δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(Wα))}δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(Wα))}δ(q0,ϵ,WF)=(q1,pop2)δ(q0,ϵ,BF)=(q1,pop2)δ(q0,b,B)=(q0,pop1)δ(q0,w,W)=(q0,pop1)δ(q1,ϵ,WF)=(q0,push1(BWW))δ(q1,ϵ,BF)=(q0,push1(BW))δ(q1,ϵ,W)=(q0,push1(BWW))δ(q1,ϵ,B)=(q0,push1(BW))We remark from the proof that the result can be extended to any tree with a finite branching, where the degree of the nodes can be defined by a fixed set of rules. A similar automaton can then be easily deduced. We refer the reader to [3] for more information on the connection between iterated pushdown automata and trees.As proved in [6, 8], for each p≥5, the tilings {p,4} and {p+2,3} of the hyperbolic plane are spanned by the same tree, which can be seen as a generalization of the Fibonacci tree for this couple of tilings. The tree has two kinds of nodes, again black and white, labelled by B and W, respectively. The tree is now generated by the following rules: (R)W⟶BWp-3,B⟶BWp-4.We can define balls in the tilings{p,4} and {p+2,3} as in the case of the pentagrid or the heptagrid: it is in fact a general definition. Now, we can define also the border of a ball and the contour word which is defined as in the case of the pentagrid and of the heptagrid.Now, considering the transitions of Automaton2, it is easy to change them in order to obtain a 2-pushdown automaton which exactly recognizes the contour words of the balls of the tilings {p,4} and {p+2,3}. Taking a copy of Automaton 2, replace in it α by p for a tiling {p,4}, by p+2 for a tiling {p+2,3}, and replace BW by BWp-4 in the last four rules of the new automaton.And so, we can state the following theorem.Theorem 4.2.
For each integerp, p≥5, there is a 2-pushdown automaton which recognizes exactly the contour words of the balls of the tilings {p,4} and {p+2,3}.


### 4.2. Sectors

Now, we can also consider truncated sectors as a region. We can define two kinds of truncated sectors which were already studied in [6] as quarters and bars in the case of the pentagrid.A truncated sector of the first kind, we will say awhitek-sector, consists of the tiles which belong to a Fibonacci tree rooted at a white tile up to the level k, this level being included. Similarly, we define a blackk-sector using a Fibonacci tree rooted at a black node. It is plain that a white and a black k-sector can be defined indifferently in the pentagrid or in the heptagrid. Moreover, these notions can be extended to the tilings {p,4} and {p+2,3}, replacing the Fibonacci tree by the tree defined by the rules (R).The contour word of ak-sector is defined by its border, as in the case of a ball. Let Wk be a white k-sector. Then, its border, ∂Wk, is defined as the set of tiles which are on the leftmost branch of the tree spanning the sector, on its rightmost branch or on the level k of the tree, see Figure 5.The representation of∂W3. (a) the pentagrid. (b) the heptagrid. In both cases, the contour word is rssbwbwwbwwss.
(a)(b)Similarly, ifBk is black k-sector, its border, ∂Bk, is defined as the set of tiles which are on the leftmost branch of the tree spanning the sector, on its rightmost branch, or on the level k of the tree, see Figure 6.The representation of∂B3. (a) the pentagrid. (b) the heptagrid. In both cases, the contour word is rssbwbwwss.
(a)(b)Now that we defined the contour words attached to∂Wk and ∂Bk, we can prove the following result.Theorem 4.3.
There is a 2-iterated pushdown automaton which recognizes the contour word of all∂Wk’s as well as another one to recognize the contour words of all ∂Bk’s.Proof.
There is no problem to recognize the leftmost branch of the tree, as it is always on the top of the store. For the rightmost branch, the idea of the proof consists in introducing new rules which will leave on the end of the external store a witness of each node on the rightmost branch. The rules can be defined as follows:(4.2)Wr⟶BbWWbX,Wb⟶BWWbX,Bb⟶BbW,W⟶BWW,B⟶BW.
Note that the second line contains the rules already used in Automaton2. The interpretation of the new rules is straightforward: Wr stands for the root, Bb for the tiles on the leftmost branch below the root, which are black nodes, and Wb for the tiles on the rightmost branch below the root. Now, X is a witness left by Wb in order to remember the tile on the rightmost branch of the tree, look at the corresponding instructions in Automaton 3.
Note that Automaton3 recognizes the contour word of truncated white sectors. For truncated black sectors, it is enough to replace the rule Wr→BbWWb by a rule Br→BbWr and to replace the transitions
(4.3)δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(Wr))},δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(Wr))}
by the transitions
(4.4)δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(Br))},δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(Br))}
and to change accordingly the transitions involving Wr by transitions involving Br. The proof of the correctness of Automaton 3 and the modified automaton for the truncated black sectors is straightforward, and it is left to the reader.Automaton 3:The 2-pushdown automaton recognizing the contour word of a truncated white sector in the pentagrid or in the heptagrid.
two states:q0 and q1; input word in {r,s,b,w}*;Γ={Z,B,W,Bb,Wb,Wr,X,F};initial state:q0; initial stack: Z[ϵ]; transition function δ:δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(Wr))}δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(Wr))}δ(q0,ϵ,WF)=(q1,pop2);δ(q0,ϵ,BF)=(q1,pop2)δ(q0,r,WrF)=(q1,pop2);δ(q0,r,Wr)=(q1,pop1)δ(q0,ϵ,WbF)=(q1,pop2)δ(q0,s,BbF)=(q1,pop2);δ(q0,b,Bb)=(q0,pop1);δ(q0,b,B)=(q0,pop1)δ(q0,w,W)=(q0,pop1);δ(q0,w,Wb)=(q0,pop1)δ(q0,s,XF)=(q0,pop1)δ(q1,ϵ,WrF)=(q0,push1(BbWWr));δ(q1,ϵ,WbF)=(q0,push1(BWWrX))δ(q1,ϵ,WF)=(q0,push1(BWW))δ(q1,ϵ,BbF)=(q0,push1(BbW));δ(q1,ϵ,BF)=(q0,push1(BW))What has been said for the contour word of a ball can be said for contour words of sectors also in the case of the tilings{p,4} and {p+2,3} of the hyperbolic plane. There are also two kinds of sectors and the transformations are very similar to the one which we performed in order to prove Theorem 4.2. We leave this as an exercise for the reader.


## 4.1. Balls

Consider a ballBk of radius k+1 in the penta- or the heptagrid. This ball is the union of the central cell and α truncated sectors, α=5 for the pentagrid and α=7 for the heptagrid, each truncated sector being spanned by a Fibonacci tree up to the level k. Accordingly, the number of tiles which are exactly at the distance k+1 from the central cell is α·f2k+1. Denote the set of these tiles by ∂Bk. Figure 4 illustrates ∂B3 in the pentagrid and in the heptagrid.The representation of∂B3. (a) the pentagrid. (b) the heptagrid. In both cases, sw3=bwbwwbww.
(a)(b)Theα sectors around the central cell can be numbered from 1 to α by fixing sector 1 once for all and by counterclockwise turning around the central cell. We call contour wordcwk the word obtained by taking the labels of the tiles which are on ∂Bk, starting from the left-hand side border of sector 1 and by counter clockwise running along ∂Bk, until the tile which is on the right-hand side border of the sector α. It is easy to remark that the contour work cwk can be written as (swk)α, where swk is obtained by taking the word which is on ∂Bk from the left-hand side of the sector to its right-hand side.Already by the length of the contour words, we can see that the set of all contour words is not algebraic: it is enough to apply Ogden’s pumping lemma.Now we have the following theorem.Theorem 4.1.
The contour words of the pentagrid and those of the heptagrid can be recognized by a 2-level pushdown automaton.Proof.
Indeed, we can transform Automaton1 in order to do the job. The new automaton is represented in Automaton 2
For the proof, it is enough to prove that for any nonnegativek(4.1)(q0,bswk,B[Fk]⋅ω)⟹δ*(q0,ϵ,ω),(q0,swk,W[Fk]⋅ω)⟹δ*(q0,ϵ,ω),
where bswk is the word obtained on the level k of a Fibonacci tree whose root is a black node, starting from the left-hand side border to the right-hand side one.
The rest of the easy proof is left to the reader.
However, we can give an idea of the automaton which will better convince the reader.
In fact, the automaton can be seen as a device which traverses the tree in a depth first way. To this purpose, starting from the root whose height isk, the automaton puts on the outer store the nodes it takes, always going to left first. For each node, the automaton puts the labels of the son of the node together with the height of each sons which is stored as an inner store. As the height of the sons is reduced by 1 with respect to that of the father, this is obtained by a simple popping of the inner store. This explains both the construction of the automaton and its correctness.
Of course, the figure of Automaton2 provides us with two automata: one for the pentagrid and one for the heptagrid.Automaton 1:The 2-pushdown automaton recognizing the Fibonacci sequence.
three states:q0, q1 and q2; input word in {a}*; Γ={Z,X1,X2,F};initial state:q0; initial stack: Z[ϵ]; transition function δ:δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(X2))}δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(X2))}δ(q0,ϵ,X1F)=(q1,pop2)δ(q0,ϵ,X2F)=(q2,pop2)δ(q0,a,X1)=(q0,pop1)δ(q0,a,X2)=(q0,pop1)δ(q1,ϵ,X1F)=(q0,push1(X1X2))δ(q2,ϵ,X2F)=(q0,push1(X1))δ(q1,ϵ,X1)=(q0,push1(X1X2))δ(q2,ϵ,X2)=(q0,push1(X1))Automaton 2:The 2-pushdown automaton recognizing the contour word of a ball in the pentagrid or in the heptagrid.
two states:q0 and q1; input word in {b,w}*; Γ={Z,B,W,F};initial state:q0; initial stack: Z[ϵ]; transition function δ:δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(Wα))}δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(Wα))}δ(q0,ϵ,WF)=(q1,pop2)δ(q0,ϵ,BF)=(q1,pop2)δ(q0,b,B)=(q0,pop1)δ(q0,w,W)=(q0,pop1)δ(q1,ϵ,WF)=(q0,push1(BWW))δ(q1,ϵ,BF)=(q0,push1(BW))δ(q1,ϵ,W)=(q0,push1(BWW))δ(q1,ϵ,B)=(q0,push1(BW))We remark from the proof that the result can be extended to any tree with a finite branching, where the degree of the nodes can be defined by a fixed set of rules. A similar automaton can then be easily deduced. We refer the reader to [3] for more information on the connection between iterated pushdown automata and trees.As proved in [6, 8], for each p≥5, the tilings {p,4} and {p+2,3} of the hyperbolic plane are spanned by the same tree, which can be seen as a generalization of the Fibonacci tree for this couple of tilings. The tree has two kinds of nodes, again black and white, labelled by B and W, respectively. The tree is now generated by the following rules: (R)W⟶BWp-3,B⟶BWp-4.We can define balls in the tilings{p,4} and {p+2,3} as in the case of the pentagrid or the heptagrid: it is in fact a general definition. Now, we can define also the border of a ball and the contour word which is defined as in the case of the pentagrid and of the heptagrid.Now, considering the transitions of Automaton2, it is easy to change them in order to obtain a 2-pushdown automaton which exactly recognizes the contour words of the balls of the tilings {p,4} and {p+2,3}. Taking a copy of Automaton 2, replace in it α by p for a tiling {p,4}, by p+2 for a tiling {p+2,3}, and replace BW by BWp-4 in the last four rules of the new automaton.And so, we can state the following theorem.Theorem 4.2.
For each integerp, p≥5, there is a 2-pushdown automaton which recognizes exactly the contour words of the balls of the tilings {p,4} and {p+2,3}.


## 4.2. Sectors

Now, we can also consider truncated sectors as a region. We can define two kinds of truncated sectors which were already studied in [6] as quarters and bars in the case of the pentagrid.A truncated sector of the first kind, we will say awhitek-sector, consists of the tiles which belong to a Fibonacci tree rooted at a white tile up to the level k, this level being included. Similarly, we define a blackk-sector using a Fibonacci tree rooted at a black node. It is plain that a white and a black k-sector can be defined indifferently in the pentagrid or in the heptagrid. Moreover, these notions can be extended to the tilings {p,4} and {p+2,3}, replacing the Fibonacci tree by the tree defined by the rules (R).The contour word of ak-sector is defined by its border, as in the case of a ball. Let Wk be a white k-sector. Then, its border, ∂Wk, is defined as the set of tiles which are on the leftmost branch of the tree spanning the sector, on its rightmost branch or on the level k of the tree, see Figure 5.The representation of∂W3. (a) the pentagrid. (b) the heptagrid. In both cases, the contour word is rssbwbwwbwwss.
(a)(b)Similarly, ifBk is black k-sector, its border, ∂Bk, is defined as the set of tiles which are on the leftmost branch of the tree spanning the sector, on its rightmost branch, or on the level k of the tree, see Figure 6.The representation of∂B3. (a) the pentagrid. (b) the heptagrid. In both cases, the contour word is rssbwbwwss.
(a)(b)Now that we defined the contour words attached to∂Wk and ∂Bk, we can prove the following result.Theorem 4.3.
There is a 2-iterated pushdown automaton which recognizes the contour word of all∂Wk’s as well as another one to recognize the contour words of all ∂Bk’s.Proof.
There is no problem to recognize the leftmost branch of the tree, as it is always on the top of the store. For the rightmost branch, the idea of the proof consists in introducing new rules which will leave on the end of the external store a witness of each node on the rightmost branch. The rules can be defined as follows:(4.2)Wr⟶BbWWbX,Wb⟶BWWbX,Bb⟶BbW,W⟶BWW,B⟶BW.
Note that the second line contains the rules already used in Automaton2. The interpretation of the new rules is straightforward: Wr stands for the root, Bb for the tiles on the leftmost branch below the root, which are black nodes, and Wb for the tiles on the rightmost branch below the root. Now, X is a witness left by Wb in order to remember the tile on the rightmost branch of the tree, look at the corresponding instructions in Automaton 3.
Note that Automaton3 recognizes the contour word of truncated white sectors. For truncated black sectors, it is enough to replace the rule Wr→BbWWb by a rule Br→BbWr and to replace the transitions
(4.3)δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(Wr))},δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(Wr))}
by the transitions
(4.4)δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(Br))},δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(Br))}
and to change accordingly the transitions involving Wr by transitions involving Br. The proof of the correctness of Automaton 3 and the modified automaton for the truncated black sectors is straightforward, and it is left to the reader.Automaton 3:The 2-pushdown automaton recognizing the contour word of a truncated white sector in the pentagrid or in the heptagrid.
two states:q0 and q1; input word in {r,s,b,w}*;Γ={Z,B,W,Bb,Wb,Wr,X,F};initial state:q0; initial stack: Z[ϵ]; transition function δ:δ(q0,ϵ,Z)={(q0,push2(F)),(q0,push1(Wr))}δ(q0,ϵ,ZF)={(q0,push2(FF)),(q0,push1(Wr))}δ(q0,ϵ,WF)=(q1,pop2);δ(q0,ϵ,BF)=(q1,pop2)δ(q0,r,WrF)=(q1,pop2);δ(q0,r,Wr)=(q1,pop1)δ(q0,ϵ,WbF)=(q1,pop2)δ(q0,s,BbF)=(q1,pop2);δ(q0,b,Bb)=(q0,pop1);δ(q0,b,B)=(q0,pop1)δ(q0,w,W)=(q0,pop1);δ(q0,w,Wb)=(q0,pop1)δ(q0,s,XF)=(q0,pop1)δ(q1,ϵ,WrF)=(q0,push1(BbWWr));δ(q1,ϵ,WbF)=(q0,push1(BWWrX))δ(q1,ϵ,WF)=(q0,push1(BWW))δ(q1,ϵ,BbF)=(q0,push1(BbW));δ(q1,ϵ,BF)=(q0,push1(BW))What has been said for the contour word of a ball can be said for contour words of sectors also in the case of the tilings{p,4} and {p+2,3} of the hyperbolic plane. There are also two kinds of sectors and the transformations are very similar to the one which we performed in order to prove Theorem 4.2. We leave this as an exercise for the reader.


## 5. Dimensions 3 and 4

We take advantage of the remark we formulated after the proof of Theorem4.1 in order to mention that the results of the previous section can be extended to the hyperbolic 3D and 4D spaces. As already mentioned in the introduction, there are only a few tessellations in the hyperbolic 3D and 4D spaces, and, starting from dimension 5, there is no such tiling in the hyperbolic space.We will briefly indicate the reason why the result of Theorem4.1 can be extended to two tilings of the hyperbolic 3D and 4D spaces. We will first see the 3D case and then the 4D one.


### 5.1. Dimension 3

There are four tessellations in the hyperbolic 3D space. We will consider only one of them, namely, the tiling{5,3,4}, which we will call the dodecagrid, as it is built by tessellation starting from the regular dodecahedral with right angles. The numbers in the signature {p,q,r} say that the faces have p sides, that, on a tile, q faces meet at a vertex, and that any edge of a tile is shared by exactly four tiles. Such a dodecahedron is unique up to isometries of the hyperbolic 3D space. In [6, 9], it is proved that the dodecagrid can be split into eight sectors exactly, the eight sectors being defined by a leading dodecahedron. The eight leading dodecahedron share a common vertex called the central point and each one is in contact with exactly three of them through three of its faces. These faces of contact define three planes of the hyperbolic 3D space which have a common point and which are pairwise perpendicular. Now, each sector is spanned by a tree 𝒯 whose root is associated with its leading dodecahedron.Now, the tree𝒯 is a 3D one which can also be represented as a planar one as its generation can be given by finitely many rules looking very much to those used in the case of the pentagrid or the heptagrid. Without entering in further details about the justification of this property, it is known from [6, 9] that, for this purpose, we can indicate a set of four rules which generate 𝒯 on the basis of the labelling of each node with one of the letters O, H, C or T, the leading dodecahedron being labelled with O.As we proved in [10], it is possible to reduce the previous set of rules to three of them, keeping only the nodes labelled with O, H, and T. The labelling with four rules is based on a splitting of the dodecagrid involving four regions also labelled O, H, C, and T, see Figure 7, from which we deduce the rules (R30). Considering the splitting defined by Figure 8, we get the following rules:(R3)O⟶O2H6T,H⟶OH6T,T⟶H5T,(R30)O⟶O5C3T,H⟶O4C3T,C⟶O3C3T,T⟶O2HC2T.Figure 7
From left to right: a corner, a half-octant, a corridor, a tunnel. Note that the faces are numbered in the same way in all the figures.Figure 8
The new splitting of a corner of the dodecagrid. In the left-hand side, the splitting of a corner. On the middle, the splitting of a half-octant. On the right-hand side, the splitting of a tunnel.From this, using the already applied technique of the previous paragraph, it is possible to devise a 2-iterated pushdown automaton which recognizes the contour words of a region whose definition is a bit changed with respect to what was given in the previous section. Here, a ballBk3 of radius k is the set of tiles which are within a distance k, in tiles, from the central point. Define the border of Bk3, denoted by ∂Bk3, as the tiles which are at a distance k exactly from the central point. The contour word is defined by traversing ∂Bk3 in the way induced by the maps very similar in principle to those defined in [6, 9]. Indeed, there is a way to injectively enumerate the tiles of the different level of 𝒯 which allow to lift up a planar representation of 𝒯 as defined by the rules (R3) up to the actual 3D tree. This can be obtained by maps of level 1, and there is a way, described in [6, 9] to generate the map of the level k from the maps of level 1 of the different trees defined by the rules (R3), considering the trees rooted at each possible kind of nodes.The sectors themselves do generate a contour word. The just indicated maps can be used to identify thesides of the tree in the maps and the considered nodes of the tree can be given an appropriate sign. Then, the traversal defined by the extension of Automaton 2 to this case will generate a contour word in which we have first the signs corresponding to the nodes which are on the sides of the sector and then the nodes which are at distance k, using the traversal defined by the maps. As we have three possible labels for the nodes, the rules (R3) define three kinds of sectors. We will call k-truncatedγ-sector, with γ∈{O,H,T}, the set of tiles which belong to a tree generated by the rules (R3) which is rooted at a tile labelled γ.Then we have the following.Theorem 5.1.
There is a 2-iterated pushdown automaton which recognizes the contour words of the ballsBk in the hyperbolic 3D space. Also, for each γ∈{O,H,T}, there is a 2-iterated pushdown automaton which recognizes the contour words of any k-truncated γ-sector.


### 5.2. Dimension 4

In the hyperbolic 4D space, there are five tessellations based on a regular polytope. We will take the one which extends the dodecagrid. From the regular dodecahedron with right angles, it is possible to construct a regular polytope called the 120-cell, whose faces are regular dodecahedra with right angles. From this regular polytope, we can generate a tiling by tessellation which we call the 120-cell grid. The signature of this grid is {5,3,3,4} which means that four 120-cells share a common pentagon, that three dodecahedra share a common edge, and that three pentagons share a common point, remembering that the 2-dimensional structure is a pentagon.The common point with the dodecagrid is that the technique used for the dodecagrid also applies here. The space is the union of 16 sectors, each one having a leading 120-cell sharing a common vertex which is the central point. Each sector is spanned by a tree whose root is associated with the leading 120-cell. This tree is also generated by a finite set of rules of the same type as that of the rules (R3). Now, this time the set of rules is much more complex as it involves 11 labels. For this reason, we will use the matricial representation of the previous subsection with a slight modification. In Table 1, the leftmost column indicates the labels. The labels are not repeated on the first line: it is assumed that the coefficients of the matrix apply to the type of node whose label is on the row whose index is the same as the column index of the coefficient, the indices starting from 1, and the leftmost column receiving index 0. We refer the reader to [11] for the justification of these rules and for further explanations.Table 1
The matrix of the generating rules of the 120-cell grid.
9610213531914511185102135319145111741021353191451116a31120353191451116b2122035319145111521120353191451114210203531914511131111935319145111211019353191451111110183531914511101101834319145111Defining the balls by the distance from a central point as in the 3D case, and the sectors from Table1, we can devise the instructions of a 2-iterated pushdown automaton which will recognize the contour word of a ball. We also can do the same for the k-truncated γ-sectors with γ∈{9,8,7,6a,6b,5,4,3,2,1,0}.


## 5.1. Dimension 3

There are four tessellations in the hyperbolic 3D space. We will consider only one of them, namely, the tiling{5,3,4}, which we will call the dodecagrid, as it is built by tessellation starting from the regular dodecahedral with right angles. The numbers in the signature {p,q,r} say that the faces have p sides, that, on a tile, q faces meet at a vertex, and that any edge of a tile is shared by exactly four tiles. Such a dodecahedron is unique up to isometries of the hyperbolic 3D space. In [6, 9], it is proved that the dodecagrid can be split into eight sectors exactly, the eight sectors being defined by a leading dodecahedron. The eight leading dodecahedron share a common vertex called the central point and each one is in contact with exactly three of them through three of its faces. These faces of contact define three planes of the hyperbolic 3D space which have a common point and which are pairwise perpendicular. Now, each sector is spanned by a tree 𝒯 whose root is associated with its leading dodecahedron.Now, the tree𝒯 is a 3D one which can also be represented as a planar one as its generation can be given by finitely many rules looking very much to those used in the case of the pentagrid or the heptagrid. Without entering in further details about the justification of this property, it is known from [6, 9] that, for this purpose, we can indicate a set of four rules which generate 𝒯 on the basis of the labelling of each node with one of the letters O, H, C or T, the leading dodecahedron being labelled with O.As we proved in [10], it is possible to reduce the previous set of rules to three of them, keeping only the nodes labelled with O, H, and T. The labelling with four rules is based on a splitting of the dodecagrid involving four regions also labelled O, H, C, and T, see Figure 7, from which we deduce the rules (R30). Considering the splitting defined by Figure 8, we get the following rules:(R3)O⟶O2H6T,H⟶OH6T,T⟶H5T,(R30)O⟶O5C3T,H⟶O4C3T,C⟶O3C3T,T⟶O2HC2T.Figure 7
From left to right: a corner, a half-octant, a corridor, a tunnel. Note that the faces are numbered in the same way in all the figures.Figure 8
The new splitting of a corner of the dodecagrid. In the left-hand side, the splitting of a corner. On the middle, the splitting of a half-octant. On the right-hand side, the splitting of a tunnel.From this, using the already applied technique of the previous paragraph, it is possible to devise a 2-iterated pushdown automaton which recognizes the contour words of a region whose definition is a bit changed with respect to what was given in the previous section. Here, a ballBk3 of radius k is the set of tiles which are within a distance k, in tiles, from the central point. Define the border of Bk3, denoted by ∂Bk3, as the tiles which are at a distance k exactly from the central point. The contour word is defined by traversing ∂Bk3 in the way induced by the maps very similar in principle to those defined in [6, 9]. Indeed, there is a way to injectively enumerate the tiles of the different level of 𝒯 which allow to lift up a planar representation of 𝒯 as defined by the rules (R3) up to the actual 3D tree. This can be obtained by maps of level 1, and there is a way, described in [6, 9] to generate the map of the level k from the maps of level 1 of the different trees defined by the rules (R3), considering the trees rooted at each possible kind of nodes.The sectors themselves do generate a contour word. The just indicated maps can be used to identify thesides of the tree in the maps and the considered nodes of the tree can be given an appropriate sign. Then, the traversal defined by the extension of Automaton 2 to this case will generate a contour word in which we have first the signs corresponding to the nodes which are on the sides of the sector and then the nodes which are at distance k, using the traversal defined by the maps. As we have three possible labels for the nodes, the rules (R3) define three kinds of sectors. We will call k-truncatedγ-sector, with γ∈{O,H,T}, the set of tiles which belong to a tree generated by the rules (R3) which is rooted at a tile labelled γ.Then we have the following.Theorem 5.1.
There is a 2-iterated pushdown automaton which recognizes the contour words of the ballsBk in the hyperbolic 3D space. Also, for each γ∈{O,H,T}, there is a 2-iterated pushdown automaton which recognizes the contour words of any k-truncated γ-sector.


## 5.2. Dimension 4

In the hyperbolic 4D space, there are five tessellations based on a regular polytope. We will take the one which extends the dodecagrid. From the regular dodecahedron with right angles, it is possible to construct a regular polytope called the 120-cell, whose faces are regular dodecahedra with right angles. From this regular polytope, we can generate a tiling by tessellation which we call the 120-cell grid. The signature of this grid is {5,3,3,4} which means that four 120-cells share a common pentagon, that three dodecahedra share a common edge, and that three pentagons share a common point, remembering that the 2-dimensional structure is a pentagon.The common point with the dodecagrid is that the technique used for the dodecagrid also applies here. The space is the union of 16 sectors, each one having a leading 120-cell sharing a common vertex which is the central point. Each sector is spanned by a tree whose root is associated with the leading 120-cell. This tree is also generated by a finite set of rules of the same type as that of the rules (R3). Now, this time the set of rules is much more complex as it involves 11 labels. For this reason, we will use the matricial representation of the previous subsection with a slight modification. In Table 1, the leftmost column indicates the labels. The labels are not repeated on the first line: it is assumed that the coefficients of the matrix apply to the type of node whose label is on the row whose index is the same as the column index of the coefficient, the indices starting from 1, and the leftmost column receiving index 0. We refer the reader to [11] for the justification of these rules and for further explanations.Table 1
The matrix of the generating rules of the 120-cell grid.
9610213531914511185102135319145111741021353191451116a31120353191451116b2122035319145111521120353191451114210203531914511131111935319145111211019353191451111110183531914511101101834319145111Defining the balls by the distance from a central point as in the 3D case, and the sectors from Table1, we can devise the instructions of a 2-iterated pushdown automaton which will recognize the contour word of a ball. We also can do the same for the k-truncated γ-sectors with γ∈{9,8,7,6a,6b,5,4,3,2,1,0}.



---

*Source: 742310-2012-03-29.xml*