Ratio Mathematica                                                                            Volume 42, 2022 

 

 

 

To some structural properties of ∞-languages 

 
 

Ivan Mezník1 
 

 

 

Abstract 

Properties of catenation of sequences of finite (words) and infinite (𝜔-words) 
lengths are largely studied in formal language theory. These operations are 

derived from the mechanism how they are accepted or generated by the 

corresponding devices. Finite automata accept structures containing only 

words, 𝜔-automata accept only 𝜔-words. Structures containing both words 
and 𝜔-words (∞-words) are mostly generated by various types of ∞-automata 
(∞-machines). The aim of the paper is to investigate algebraic properties of 

operations on ∞-words generated by IGk-automata, where k is to model the 

depth of memory. It has importance in many applications (shift registers, 

discrete systems with memory…). It is shown that resulting algebraic 

structures are of „pure“ groupoid or partial groupoid type. 

 

Keywords: ∞-words; ∞-language; ρn,p,r-catenation; closure of an ∞-

language; 

ρ-operation. 
 

Mathematics Subject Classification: 68Q70, 08A552 

 

 

 

 

 

 

 

 

 

 
1 Institute of Informatics, Faculty of Business and Management, Brno University of Technology, Kolejní 

2906/4, 612 00  Brno, Czech Republic; meznik@vutbr.cz. 
2 Received on January 23th, 2022. Accepted on June 4th, 2022. Published on June 30th, 2022.  

doi: 10.23755/rm.v41i0.721. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is 

published under the CC-BY licence agreement. 

127



Ivan Mezník 

 

1. Introduction 

 The notion of an ∞-language was introduced by Nivat ([10]) as a free-monoid 
structure containing words finite („clasical“ languages) and infinite (ω-languages) 

lengths. The theory of ω-languages has been intensively developed so far, mostly as 

a generalization of acceptance conditions of various types of automata 

([1], [8], [9], [11], [12], [13], [14], [15] among others). Devices capable to accept (or 
generate) simultaneously words or finite or infinite (ω-words) lengths were described and 

investigated in [2], [3]. Such devices (k-machines, IGk-machines) also provide to 
implement the depth of memory and possess various applications (shift registers, 

modelling of phenomena working in a discrete time scale). They also make a lot of 

properties. In [3] lattice structures were described. The way how they generate words and 
ω-words motivates to study various types of catenation of words, which is the aim of the 

paper. The paper is organized as follows. In Section 2 we introduce basic concepts. In 

Sections 3 and 4 we examine properties of 𝜌-closure and 𝜌-operation, respectively. 
 

2. Preliminaries 

An alphabet is any finite set (including the empty set) and is denoted by 𝛴; its 
elements are called letters. Let ω be the least infinite ordinal and n, 0 ≤ 𝑛 ≤ 𝜔 be an 
ordinal. For 𝛴 ≠ ∅ the set of all finite sequences of elements of Σ including the empty 
sequence λ is denoted by 𝛴∗, the set of all infinite sequences of elements of Σ by 𝛴𝜔 and 
the set  𝛴∗ ∪ 𝛴𝜔 by 𝛴∞. For 𝛴 = ∅, by definition, 𝛴∗ = 𝛴𝜔 = 𝛴∞ = ∅. The elements of 
𝛴∗ are words, the elements of 𝛴𝜔 are ω-words, the elements of 𝛴∞ are ∞-words. Instead 
of (𝑎0, 𝑎1, … , 𝑎𝑛−1) ∈ 𝛴

∗, 𝑛 ≥ 1 and (𝑎0, 𝑎1, … ) ∈ 𝛴
𝜔 we write simply 𝑎0𝑎1 … 𝑎𝑛−1 and 

𝑎0𝑎1 …. For 𝑤 ∈ 𝛴
∞, the length of w, denoted by |𝑤| is defined as follows: if 𝑤 =

𝑎0𝑎1 … 𝑎𝑛−1 ∈ 𝛴
∗ then |𝑤| = 𝑛, if 𝑤 = 𝑎0𝑎1 … ∈ 𝛴

𝜔 then |𝑤| = 𝜔 and if 𝑤 = 𝜆 then 
|𝑤| = 0. A subset of 𝛴∗ and 𝛴𝜔 and 𝛴∞ is referred to as a language and an ω-language 
and an ∞-language (over Σ) respectively. For 𝐿 ⊆ 𝛴∞ we define 𝑚(𝑙) = 𝑖𝑛𝑓{|𝑤|; 𝑤 ∈
𝐿}. Let 𝑤 ∈ 𝛴∞ − {𝜆}, 1 ≤ 𝑚 ≤ 𝑛 < 1 + |𝑤|; by 𝑤(𝑛) we denote the n-th letter of w, by 
w[𝑚, 𝑛]  the word 𝑤(𝑚) … 𝑤(𝑛) and if |𝑤| = 𝜔 by 𝑤[𝑚, 𝜔] the word 𝑤(𝑚)𝑤(𝑚 +
1) …. Instead of 𝑤[1, 𝑛] we write only 𝑤[𝑛]. In case 𝑚 > 𝑛 we formally put 𝑤[𝑚, 𝑛] =
𝜆. The usual operation of catenation on 𝛴∗ may be extended to 𝛴∞ as a partial operation 
as follows. Let 𝑤 ∈ 𝛴∗, |𝑤| = 𝑛, 𝑤 ′ ∈ 𝛴∞; if 𝑤 ′ ∈ 𝛴∗, then 𝑤𝑤 ′ is defined by catenation 
on 𝛴∗ and if 𝑤 ′ ∈ 𝛴𝜔, then 𝑤𝑤 ′ = 𝑤(1)𝑤(2) … 𝑤(𝑛)𝑤 ′(1)𝑤 ′(2) …. For 𝑤 ∈ 𝛴∗, 𝑘 ≥
1, the symbol 𝑤 𝑘  denotes the result of k catenations of w and the symbol 𝑤 𝜔 denotes the 
result of infinite number of catenations of w; by definition, 𝑤 0 = 𝜆. 
 

3. Closure of an ∞-language 
In this section we define the notion of a 𝜌-catenation. Subsequently the concept of 

a 𝜌-closure is introduced and its closure characterization is derived. 

128



To some structural properties of ∞-languages 

 

2.1 Definition. Let 𝑛, 𝑝, 𝑟  be positive integers and 𝑢 ∈ 𝛴∞, 𝑣 ∈ 𝛴∞. For u,v 
satisfying the property 

𝑢[𝑝, 𝑝 + 𝑛 − 1] = 𝑣[𝑟, 𝑟 + 𝑛 − 1] 

we define the operation 𝜌𝑛,𝑝,𝑟 by  
 

(2.1)                                       𝜌𝑛,𝑝,𝑟 (𝑢, 𝑣) = 𝑢[𝑝 + 𝑛 − 1]𝑣[𝑟 + 𝑛, |𝑣|] 
 

called a  𝜌𝑛,𝑝,𝑟-catenation or only ρ-catenation if n,p,r are given by the context. 

Apparently, each 𝜌𝑛,𝑝,𝑟-catenation is a partial operation in 𝛴
∞. In other words, each 

 𝜌𝑛,𝑝,𝑟-catenation defines a partial groupoid in 𝛴
∞. In this manner (regarding the given 

n,p,r) the set of partial operations (groupoids) in 𝛴∞ is given. Instead of 𝜌𝑛,𝑝,𝑟 (𝑢, 𝑣) we 

write as customary 𝑢𝜌𝑛,𝑝,𝑟 𝑣 or only 𝑢𝜌𝑣, if 𝑛, 𝑝, 𝑟 are clear from the context. To simplify 

the text, by stating  𝑢𝜌𝑛,𝑝,𝑟 𝑣 it is supposed that (𝑢, 𝑣) ∈ 𝐷𝑜𝑚(𝜌𝑛,𝑝,𝑟 ).  

2.2 Lemma. Suppose 𝑢 ∈ 𝛴∞ and 𝑢𝜌𝑛,𝑝,𝑟 𝑢 for some 𝑛, 𝑝, 𝑟 . Then it holds 

𝑢𝜌𝑛,𝑝,𝑟 𝑢 = 𝑢. 

Proof. It is an immediate consequence of Definition 2.1  

Remarks. 1∘ Suppose 𝑢 ∈ 𝛴∞ and 𝑛, 𝑝, 𝑟 ≤ |𝑢|. Then there is obviously an infinite 
number of words 𝑥 ∈ 𝛴∞  such that  𝑢𝜌𝑛,𝑝,𝑟 𝑥 = 𝑢  playing the role of the „identity“ 

element of 𝜌𝑛,𝑝,𝑟-catenation. 

2∘ Operation 𝜌𝑛,𝑝,𝑟 is in general not commutative. For example consider words u,v over 

𝛴 = {𝑎, 𝑏}, 𝑢 = (𝑎𝑏)3, 𝑣 = 𝑎3. Applying the previous definition we get  𝑢𝜌1,3,1𝑣 =

𝑎𝑏𝑎3, 𝑣𝜌1,3,1𝑢 = 𝑎
2(𝑎𝑏)3, 𝑢𝜌1,3,1𝑣 ≠ 𝑣𝜌1,3,1𝑢. 

3∘ Operation 𝜌𝑛,𝑝,𝑟 is in general not associative. For example consider 𝜌1,3,2 −

𝑐𝑎𝑡𝑒𝑛𝑎𝑡𝑖𝑜𝑛 in {𝑎, 𝑏}∞ and let 𝑢 = (𝑎𝑏)4, 𝑣 = 𝑎5, 𝑤 = 𝑎7. Construct (𝑢𝜌1,3,2𝑣)𝜌1,3,2𝑤,

𝑢𝜌1,3,2(𝑣𝜌1,3,2𝑤). Due to Definition 2.1 we get (𝑢𝜌1,3,2𝑣)𝜌1,3,2𝑤 = 𝑎𝑏𝑎
5, whereas 

𝑢𝜌1,3,2(𝑣𝜌1,3,2𝑤) = 𝑎𝑏𝑎
7. Of course, some of catenations in the given expressions need 

not be defined. 

2.3 Theorem Let 𝑢 ∈ 𝛴∞, 𝑣 ∈ 𝛴∞ and suppose 𝑢𝜌𝑛,𝑝,𝑟 𝑣, 𝑣𝜌𝑛,𝑟,𝑠𝑤 for some 

𝑛, 𝑝, 𝑟, 𝑠 ≥ 1. Then 𝑢𝜌𝑛,𝑝,𝑠𝑤 and there holds  
 

(2.2)                                                  𝑢𝜌𝑛,𝑝,𝑠𝑤 = 𝑢𝜌𝑛,𝑝,𝑟 (𝑣𝜌𝑛,𝑟,𝑠𝑤). 
 

Proof. Suppose that   𝑢𝜌𝑛,𝑝,𝑟 𝑣, 𝑣𝜌𝑛,𝑟,𝑠 𝑤 hold for given 𝑛, 𝑝, 𝑟, 𝑠 ≥ 1. From Definition 

2.1 it follows that 𝑢[𝑝, 𝑝 + 𝑛 − 1] = 𝑣[𝑟, 𝑟 + 𝑛 − 1] and 𝑣[𝑟, 𝑟 + 𝑛 − 1] = 𝑤[𝑠, 𝑠 + 𝑛 −
1]. Then evidently 𝑢[𝑝, 𝑝 + 𝑛 − 1] = 𝑤[𝑠, 𝑠 + 𝑛 − 1], applying Definition 2.1 we get 
𝑢𝜌𝑛,𝑝,𝑠𝑤 = 𝑢[𝑝 + 𝑛 − 1]𝑤[𝑠 + 𝑛, |𝑤|] and the first part of the statement is verified. 

Rewriting this expression we obtain 
 

(2.3)              𝑢𝜌𝑛,𝑝,𝑠𝑤 = 𝑢[1] … 𝑢[𝑝 + 𝑛 − 1]𝑤[𝑠 + 𝑛]𝑤[𝑠 + 𝑛 + 1] … 𝑤[|𝑤|]. 
 

Now we costruct the right part of (2.2). By Definition 2.1 we have 
 

129



Ivan Mezník 

 

                        𝑣𝜌𝑛,𝑟,𝑠𝑤 = 𝑣[1] … 𝑣[𝑟] … 𝑣[𝑟 + 𝑛 − 1]𝑤[𝑠 + 𝑛] … 𝑤[|𝑤|], 
 

where  𝑣[𝑟, 𝑟 + 𝑛 − 1] = 𝑣[𝑟] … 𝑣[𝑟 + 𝑛 − 1] = 𝑤[𝑠] … 𝑤[𝑠 + 𝑛 − 1] = 𝑤[𝑠, 𝑠 + 𝑛 −
1] and 
 

(2.4)             𝑢𝜌𝑛,𝑝,𝑟 (𝑣𝜌𝑛,𝑟,𝑠𝑤) = 𝑢[1] … 𝑢[𝑝] … 𝑢[𝑝 + 𝑛 − 1]𝑤[𝑠 + 𝑛] … 𝑤[|𝑤|]. 
 

From (2.3) and (2.4) the statement (2.2) holds and the proof is completed. 

2.4 Theorem Let 𝑢, 𝑣 ∈ 𝛴∞ and suppose 𝑢𝜌𝑛,𝑝,𝑟 𝑣 for fixed 𝑛 > 1, 𝑝 ≥ 1, 𝑟 ≥ 1. 

Then 𝑢𝜌𝑚,𝑝,𝑟 𝑣 for any 𝑚 < 𝑛 and it holds 
 

(2.5)                                                 𝑢𝜌𝑛,𝑝,𝑟 𝑣 = 𝑢𝜌𝑚,𝑝,𝑟 𝑣 . 
 

Proof. Let 𝑢𝜌𝑛,𝑝,𝑟 𝑣 for the given 𝑛, 𝑝, 𝑟. From Definition 2.1 it follows that 

𝑢[𝑝, 𝑝 + 𝑛 − 1] = 𝑣[𝑟, 𝑟 + 𝑛 − 1]. Since 𝑚 < 𝑛 , then apparently 𝑢[𝑝, 𝑝 + 𝑚 − 1] =
𝑣[𝑟, 𝑟 + 𝑚 − 1] holds for any 𝑚 < 𝑛 as well and thus 𝑢𝜌𝑚,𝑝,𝑟 𝑣. Due to (2.1) 𝑢𝜌𝑛,𝑝,𝑟 𝑣 =

𝑢[𝑝 + 𝑛 − 1]𝑣[𝑟 + 𝑛, |𝑣|]. In a detailed version we have 
 

(2.6)                              𝑢𝜌𝑛,𝑝,𝑟 𝑣 = 𝑢[1] … 𝑢[𝑝 + 𝑛 − 1]𝑣[𝑟 + 𝑛] … 𝑣[|𝑣|].   
 

With a view to 𝑚 < 𝑛, (2.6) may be rewritten as 
 

(2.7) 𝑢𝜌𝑛,𝑝,𝑟 𝑣 = 𝑢[1] … 𝑢[𝑝 + 𝑚 − 1]𝑢[𝑝 + 𝑚] … 𝑢[𝑝 + 𝑛 − 1]𝑣[𝑟 + 𝑛]𝑣[𝑟 + 𝑛 +

1] … 𝑣[|𝑣|]. 
 

Now, we construct 𝑢𝜌𝑚,𝑝,𝑟 𝑣  for 𝑚 < 𝑛. It holds 𝑢[𝑝, 𝑝 + 𝑚 − 1] = 𝑣[𝑟, 𝑟 + 𝑚 − 1] 

and by (2.1) 
 

(2.8)              𝑢𝜌𝑚,𝑝,𝑟 𝑣 =  𝑢[𝑝 + 𝑚 − 1]𝑣[𝑟 + 𝑚, |𝑣|]. 
 

In detail 
 

(2.9)           𝑢𝜌𝑚,𝑝,𝑟 𝑣 = 𝑢[1] … 𝑢[𝑝 + 𝑚 − 1]𝑣[𝑟 + 𝑚] … 𝑣[|𝑣|].    
 

With a view to 𝑚 < 𝑛, (2.9) may be rewritten as 
 

 (2.10) 𝑢𝜌𝑚,𝑝,𝑟 𝑣 = 𝑢[1] … 𝑢[𝑝] … 𝑢[𝑝 + 𝑚 − 1]𝑣[𝑟 + 𝑚] … 𝑣[𝑟 + 𝑛 − 1]𝑣[𝑟 +

𝑛] … 𝑣[|𝑣|]. 

Due to (2.7) and (2.10)   𝑢[1] … 𝑢[𝑝 + 𝑚 − 1] and  𝑣[𝑟 + 𝑛] … 𝑣[|𝑣|] are common 
parts. It remains to verify that 𝑣[𝑟 + 𝑚] … 𝑣[𝑟 + 𝑛 − 1] =  𝑢[𝑝 + 𝑚] … 𝑢[𝑝 + 𝑛 − 1]. 
Using assumptions of Definition 2.1 we have 𝑢[𝑝, 𝑝 + 𝑛 − 1] = 𝑣[𝑟, 𝑟 + 𝑛 − 1] and thus 
also 𝑣[𝑟 + 𝑚] … 𝑣[𝑟 + 𝑛 − 1] =  𝑢[𝑝 + 𝑚] … 𝑢[𝑝 + 𝑛 − 1]. Hence (2.7) and (2.10) are 
identical words and the proof is completed. 

2.5 Definition. Let a  𝜌𝑛,𝑝,𝑟 − catenation be given. Define a relation  𝑅𝑛,𝑝,𝑟  on 𝛴
∞ by 

 

(2.11)                  𝑅𝑛,𝑝,𝑟 = {𝑢, 𝑣 ∈ 𝛴
∞; (𝑢, 𝑣) ∈ 𝐷𝑜𝑚(𝜌𝑛,𝑝,𝑟 )} ⊆ 𝛴

∞ × 𝛴∞. 
 

2.6 Lemma. The relation 𝑅𝑛,𝑝,𝑟  is 

(i) reflexive,  

(ii) not symmetric,  

(iii) not antisymmetric,  

130



To some structural properties of ∞-languages 

 

(iv) not transitive. 

Proof. (i) Reflexivity of  𝑅𝑛,𝑝,𝑟  follows immediately from Lemma 2.2. (ii) Consider 

𝑢 = 𝑎𝑏𝑏𝑏, 𝑣 = 𝑎𝑎𝑏𝑏𝑏. By Definition 2.1 it holds 𝑢 = 𝑎𝑏𝑏𝑏𝜌2,3,3𝑎𝑎𝑏𝑏𝑏 = 𝑣, whereas 
𝑣 = 𝑎𝑎𝑏𝑏𝑏𝜌2,3,3𝑎𝑏𝑏𝑏 = 𝑢 does not hold, so the relation 𝑅𝑛,𝑝,𝑟  is not transitive. (iii) Put 

𝑢 = 𝑎𝑏𝑎𝑏𝑎𝑏𝑎𝑏 = (𝑎𝑏)4, 𝑣 = 𝑏𝑎𝑏𝑎𝑏𝑎𝑏𝑎𝑏𝑎 = (𝑏𝑎)5. By Definition 2.1 we have 
𝑢𝜌1,2,5𝑣, 𝑣𝜌1,2,5𝑢, but 𝑢 ≠ 𝑣 and hence the relation 𝑅𝑛,𝑝,𝑟  is not antisymmetric. (iv) Let 

𝑢 = 𝑎𝑏𝑏𝑏, 𝑣 = 𝑏𝑎𝑏𝑎𝑏𝑎, 𝑤 = 𝑏𝑏𝑏𝑏. From Definition it follows 𝑢𝜌1,1,2𝑣, 𝑣𝜌1,1,2𝑤, but 
𝑢𝜌1,1,2𝑤 does not hold and the relation 𝑅𝑛,𝑝,𝑟  is not transitive. 

2.5 Definition. Let 𝐿 ⊆ 𝛴∞ be an  ∞-language,  𝑛 ≥ 1 integer and 𝑢, 𝑣 ∈ 𝛴∞. Put  

𝐶𝑛
𝜌

(𝑢, 𝑣) =
∪

𝑝, 𝑟
𝑢𝜌𝑛,𝑝,𝑟 𝑣, 𝐶𝑛

𝜌
(𝐿) =

∪
𝑢, 𝑣

𝐶𝑛
𝜌

(𝑢, 𝑣), 𝐶𝜌(𝐿) =
∪
𝑛

𝐶𝑛
𝜌

(𝐿). 

The set 𝐶𝑛
𝜌

(𝐿) is called the n-th ρ-closure of L and the set 𝐶𝜌(𝐿) =
∪
𝑛

𝐶𝑛
𝜌

(𝐿) the ρ-

closure of L respectively. 

2.6 Lemma. Let 𝐿 ⊆ 𝛴∞ − {𝜆} be an  ∞-language. Then 𝐿 ⊆ 𝐶𝜌(𝐿) holds true. 

Proof. Suppose 𝑤 ∈ 𝐿. Trivially 𝑤(1) = 𝑤(1) and by Definition 2.1 it holds 
𝑤𝜌1,1,1𝑤 = 𝑤[1]𝑤[2, |𝑤|] = 𝑤 and hence by Definition 2.5 𝑤 ∈ 𝐶1

𝜌
(𝐿) and also 𝑤 ∈

𝐶𝜌(𝐿) and the statement holds true. 

2.7 Theorem Let 𝐿 ⊆ (𝛴∞ − {𝜆}) be an ∞-language. Then for every 𝑖 ≥ 1 there 
holds 

𝐶𝑖+1
𝜌

(𝐿) ⊆ 𝐶𝑖
𝜌

(𝐿). 

Proof. Let 𝑤 ∈ 𝐶𝑖+1
𝜌

(𝐿). According to Definition 2.1 there exist 𝑢, 𝑣 ∈ 𝛴∞ and 

𝑖, 𝑝, 𝑟 ≥ 1 with the property 𝑢[𝑝, 𝑝 + 𝑖] = 𝑣[𝑟, 𝑟 + 𝑖] for which 𝑢𝜌𝑖+1,𝑝.𝑟 𝑣 = 𝑢[𝑝 +

𝑖]𝑣[𝑟 + 𝑖 + 1, |𝑣|] = 𝑤 holds. Obviously if 𝑢[𝑝, 𝑝 + 𝑖] = 𝑣[𝑟, 𝑟 + 𝑖]  then also 𝑢[𝑝, 𝑝 +
𝑖 − 1] = 𝑣[𝑟, 𝑟 + 𝑖 − 1] holds. By Definition 2.5 we get 𝑢𝜌𝑖,𝑝,𝑟 𝑣 = 𝑢[𝑝 + 𝑖 − 1]𝑣[𝑟 +

𝑖, |𝑣|] = 𝑤 ′ ∈ 𝐶𝑖
𝜌

(𝐿). But apparently 𝑤, 𝑤 ′ are identical words. Hence 𝑤 ∈ 𝐶𝑖
𝜌

(𝐿) and 
the statement is valid. 

As a consequence of Definition 2.5 and Theorem 2.7 the following Corollary 2.8 

holds: 

2.8 Corollary Let 𝐿 ⊆ (𝛴∞ − {𝜆}) be an  ∞-language. Then 𝐶𝜌(𝐿) = 𝐶1
𝜌

(𝐿) holds 
true. 

2.9 Example Let 𝐿 = {𝑎𝑏, 𝑏𝑎𝑘 , 𝑎𝜔 ; 𝑘 ≥ 1} ⊆ {𝑎, 𝑏}∞ be an ∞ - language. To find 
𝐶𝑛

𝜌
(𝐿) and 𝐶𝜌(𝐿) applying Definition 2.5 we get the results as follows. 

(i) 𝐶1
𝜌

(𝐿): 𝐶1
𝜌

(𝑎𝑏, 𝑎𝑏) = {𝑎𝑏}, 𝐶1
𝜌

(𝑎𝑏, 𝑏𝑎𝑘 ) = {𝑎𝑘 , 𝑎𝑏𝑎𝑘 ; 𝑘 ≥ 1}, 𝐶1
𝜌

(𝑏𝑎𝑘 , 𝑎𝑏) =

{𝑏, 𝑏𝑎𝑘 𝑏; 𝑘 ≥ 1}, 𝐶1
𝜌

(𝑏𝑎𝑘 , 𝑏𝑎𝑘 ) = {𝑏𝑎𝑘 ; 𝑘 ≥ 1}, 𝐶1
𝜌

(𝑎𝑏, 𝑎𝜔 ) = {𝑎𝜔 }, 𝐶1
𝜌

(𝑎𝜔 , 𝑎𝑏) =

{𝑎𝑘 𝑏; 𝑘 ≥ 1}, 𝐶1
𝜌

(𝑎𝜔 , 𝑎𝜔 ) = {𝑎𝜔 }, 𝐶1
𝜌

(𝑏𝑎𝑘 , 𝑎𝜔 ) = {𝑏𝑎𝜔 }, 𝐶1
𝜌

(𝑎𝜔 , 𝑏𝑎𝑘 ) = {𝑎𝑘 ; 𝑘 ≥ 1}; 

therefore 𝐶1
𝜌

(𝐿) = {𝑎𝑏, 𝑎𝑘 , 𝑎𝑏𝑎𝑘 , 𝑏𝑎𝑘 𝑏, 𝑏𝑎𝑘 , 𝑎𝜔 , 𝑎𝑘 𝑏, 𝑏𝑎𝜔 ; 𝑘 ≥ 1}. 

131



Ivan Mezník 

 

(ii) 𝐶2
𝜌

(𝐿): 𝐶2
𝜌

(𝑎𝑏, 𝑎𝑏) = {𝑎𝑏}, 𝐶2
𝜌

(𝑎𝑏, 𝑏𝑎𝑘 ) = ∅, 𝐶2
𝜌

(𝑏𝑎𝑘 , 𝑎𝑏) = ∅, 𝐶2
𝜌

(𝑎𝜔 , 𝑎𝜔 ) =

{𝑎𝜔 }, 𝐶2
𝜌

(𝑏𝑎𝑘 , 𝑎𝜔 ) = {𝑏𝑎𝜔 } for 𝑘 ≥ 2, 𝐶2
𝜌

(𝑎𝜔, 𝑏𝑎𝑘 ) = {𝑎𝑘 ; 𝑘 ≥ 2}, 𝐶2
𝜌

(𝑏𝑎𝑘 , 𝑏𝑎𝑘 ) =

{𝑏𝑎𝑘 ; 𝑘 ≥ 1}, 𝐶2
𝜌

(𝑎𝑏, 𝑎𝜔 ) = ∅, 𝐶2
𝜌

(𝑎𝜔 , 𝑎𝑏) = ∅; therefore 𝐶2
𝜌

(𝐿) =
{𝑎𝑏, 𝑏𝑎𝑘 , 𝑎𝜔 , 𝑏𝑎𝜔 , 𝑎𝑘+1; 𝑘 ≥ 1}. 
(iii) 𝐶3

𝜌
(𝐿): 𝐶3

𝜌
(𝑎𝑏, 𝑎𝑏)=𝐶3

𝜌
(𝑎𝑏, 𝑏𝑎𝑘 ) = 𝐶3

𝜌
(𝑏𝑎𝑘 , 𝑎𝑏) = 𝐶3

𝜌
(𝑎𝑏, 𝑎𝜔 ) = 𝐶3

𝜌
(𝑎𝜔 , 𝑎𝑏) =

∅, 𝐶3
𝜌

(𝑏𝑎𝑘 , 𝑏𝑎𝑘 ) = {𝑏𝑎𝑘 ; 𝑘 ≥ 2}, 𝐶3
𝜌

(𝑎𝜔 , 𝑎𝜔 ) = {𝑎𝜔 }, 𝐶3
𝜌

(𝑏𝑎𝑘 , 𝑎𝜔 ) = {𝑏𝑎𝜔 } for 𝑘 ≥

3, 𝐶3
𝜌

(𝑎𝜔 , 𝑏𝑎𝑘 ) = {𝑎𝑘 ; 𝑘 ≥ 3}; therefore 𝐶3
𝜌

(𝐿) = {𝑏𝑎𝑘 , 𝑎𝜔 , 𝑏𝑎𝜔 , 𝑎𝑘+1; 𝑘 ≥ 2}. 

(iv) 𝐶𝑛
𝜌

(𝐿) for 𝑛 ≥ 4: 𝐶𝑛
𝜌

(𝑎𝑏, 𝑎𝑏)=𝐶𝑛
𝜌

(𝑎𝑏, 𝑏𝑎𝑘 ) = 𝐶𝑛
𝜌

(𝑏𝑎𝑘 , 𝑎𝑏) = 𝐶𝑛
𝜌

(𝑎𝑏, 𝑎𝜔 ) =

𝐶𝑛
𝜌

(𝑎𝜔 , 𝑎𝑏) = ∅, 𝐶𝑛
𝜌

(𝑏𝑎𝑘 , 𝑏𝑎𝑘 ) = {𝑏𝑎𝑘 ; 𝑘 ≥ 𝑛 − 1}, 𝐶𝑛
𝜌

(𝑎𝜔 , 𝑎𝜔 ) =
{𝑎𝜔 }, 𝐶𝑛

𝜌
(𝑏𝑎𝑘 , 𝑎𝜔 ) = {𝑏𝑎𝜔 } for 𝑘 ≥ 𝑛 − 1, 𝐶𝑛

𝜌
(𝑎𝜔, 𝑏𝑎𝑘 ) = {𝑎𝑘 ; 𝑘 ≥ 𝑛 − 1}; therefore 

𝐶𝑛
𝜌

(𝐿) = {𝑏𝑎𝑘 , 𝑎𝜔 , 𝑏𝑎𝜔 , 𝑎𝑘+1; 𝑘 ≥ 𝑛 − 1}.  

Conclusion: 𝐶𝜌(𝐿) = {𝑎𝑏, 𝑎𝑘 , 𝑎𝑏𝑎𝑘 , 𝑏𝑎𝑘 𝑏, 𝑏𝑎𝑘 , 𝑎𝜔 , 𝑎𝑘 𝑏, 𝑏𝑎𝜔 ; 𝑘 ≥ 1} = 𝐶1
𝜌

(𝐿). 

2.10 Theorem.  The set of ρ-closures is not closed under set union. 

Proof. We state an counterexample. Consider 𝐿1 = {𝑎𝑏}, 𝐿2 = {𝑎
𝜔} over {𝑎, 𝑏}∞and 

put 𝐿 = 𝐿1 ∪ 𝐿2 = {𝑎𝑏, 𝑎
𝜔 }. Applying Definition 2.1 and Corollary 2.8 we get 𝐶𝜌(𝐿1) =

𝐶1
𝜌

(𝐿1) = 𝐶
𝜌({𝑎𝑏}) = {𝑎𝑏}, 𝐶𝜌(𝐿2) = 𝐶1

𝜌
(𝐿2) = 𝐶

𝜌({𝑎𝜔 }) = {𝑎𝜔 }. Further, 𝐶𝜌(𝐿) =

𝐶𝜌(𝐿1 ∪ 𝐿2) = 𝐶
𝜌({𝑎𝑏, 𝑎𝜔 }) = {𝑎𝜔 , 𝑎𝑘 𝑏; 𝑘 ≥ 1}. Obviously 𝐶𝜌(𝐿1 ∪ 𝐿2) ≠ 𝐶

𝜌(𝐿1) ∪
𝐶𝜌𝐿2) and the statement is verified. 

2.11 Theorem. Let 𝐿1, 𝐿2 ⊆ 𝛴
∞ .  Then 𝐶𝜌(𝐿1) ∪ 𝐶

𝜌𝐿2) ⊆ 𝐶
𝜌(𝐿1 ∪ 𝐿2). 

Proof. With a view to Corollary 2.6 we may consider  𝐶1
𝜌

 instead of 𝐶𝜌. Let 𝑤 ∈

𝐶1
𝜌

(𝐿1) ∪ 𝐶1
𝜌

(𝐿2). According to Definition  2.3 then (a) there exist 𝑢 ∈ 𝐿1, 𝑣 ∈ 𝐿1 and 

positive integers 𝑝, 𝑟 such that 𝑢𝜌1,𝑝,𝑟 𝑣 = 𝑤 ∈ 𝐶1
𝜌

(𝐿1) or (b) there exist 𝑢 ∈ 𝐿2, 𝑣 ∈ 𝐿2 

and positive integers 𝑝, 𝑟 such that 𝑢𝜌1,𝑝,𝑟 𝑣 = 𝑤 ∈ 𝐶1
𝜌

(𝐿2). Assuming (a), the statement 

there exist 𝑢 ∈ 𝐿1 ∪ 𝐿2, 𝑣 ∈ 𝐿1 ∪ 𝐿2 and positive integers 𝑝, 𝑟 such that 𝑢𝜌1,𝑝,𝑟 𝑣 = 𝑤 ∈

𝐶1
𝜌

(𝐿1 ∪ 𝐿2) is obviously also valid for an arbitrary set 𝐿2. Assuming (b), the statement 
there exist 𝑢 ∈ 𝐿2 ∪ 𝐿1, 𝑣 ∈ 𝐿2 ∪ 𝐿1 and positive integers 𝑝, 𝑟 such that 𝑢𝜌1,𝑝,𝑟 𝑣 = 𝑤 ∈

𝐶1
𝜌

(𝐿2 ∪ 𝐿1) is valid as well for ab arbitrary set 𝐿1. Thus 𝑤 ∈ 𝐶1
𝜌

(𝐿1 ∪ 𝐿2) and the proof 
is completed. 

2.12 Theorem. The set of ρ-closures is not closed under set intersection. 

Proof. We state an counterexample. Consider 𝐿1 = {𝑎
𝜔, 𝑎3, 𝑏}, 𝐿2 = {𝑎

3, 𝑎𝑏} over 
{𝑎, 𝑏}∞and put 𝐿 = 𝐿1 ∩ 𝐿2 = {𝑎

3}. Applying Definition 2.1 and Corollary 2.8 we get 
𝐶𝜌(𝐿1) = 𝐶1

𝜌
(𝐿1) = 𝐶1

𝜌
({𝑎𝜔, 𝑎3, 𝑏}) = {𝑎𝜔 , 𝑏, 𝑎𝑘 ; 𝑘 ≥ 1}, 𝐶𝜌(𝐿2) = 𝐶1

𝜌
(𝐿2) =

𝐶1
𝜌

({𝑎3, 𝑎𝑏}) = {𝑎, 𝑎2, 𝑎3, 𝑎4, 𝑎5, 𝑏, 𝑎𝑏, 𝑎2𝑏, 𝑎3𝑏}, 𝐶𝜌(𝐿1) ∩ 𝐶
𝜌(𝐿2) =

{𝑎, 𝑎2, 𝑎3, 𝑎4, 𝑎5, 𝑏}. Further,𝐶𝜌(𝐿) = 𝐶𝜌(𝐿1 ∩ 𝐿2) = 𝐶
𝜌({𝑎3}) = {𝑎𝑘  ; 1 ≤ 𝑘 ≤ 5}. 

Obviously 𝐶𝜌(𝐿1 ∩ 𝐿2) ≠ 𝐶
𝜌(𝐿1) ∩ 𝐶

𝜌(𝐿2) and the statement is verified. 

2.13 Theorem. Let 𝐿1, 𝐿2 ⊆ 𝛴
∞. Then 𝐶𝜌(𝐿1 ∩ 𝐿2) ⊆ 𝐶

𝜌(𝐿1) ∩ 𝐶
𝜌(𝐿2). 

132



To some structural properties of ∞-languages 

 

Proof. With a view to Corollary 2.6 we may work with 𝐶1
𝜌

 instead of 𝐶𝜌. Let 𝑤 ∈

𝐶1
𝜌

(𝐿1 ∩ 𝐿2). According to Definition 2.3 there exist 𝑢 ∈ (𝐿1 ∩ 𝐿2), 𝑣 ∈ (𝐿1 ∩ 𝐿2) and 

positive integers 𝑝, 𝑟 such that 𝑢𝜌1,𝑝,𝑟 𝑣 = 𝑤 ∈ 𝐶1
𝜌

(𝐿1 ∩ 𝐿2). Since 𝑢 ∈ (𝐿1 ∩ 𝐿2), 𝑣 ∈

(𝐿1 ∩ 𝐿2), then 𝑤 ∈ 𝐶1
𝜌

(𝐿1) and also 𝑤 ∈ 𝐶1
𝜌

(𝐿2). Thus 𝑤 ∈ 𝐶1
𝜌

(𝐿1) ∩ 𝐶1
𝜌

(𝐿2) and the 
statement holds. 

2.14 Example.  Using the setting of the counterexample from the proof of Theorem 

2.12, we have 𝐶𝜌(𝐿1 ∩ 𝐿2) = 𝐶
𝜌({𝑎3}) = {𝑎𝑘  ; 1 ≤ 𝑘 ≤ 5} ⊆ 𝐶𝜌(𝐿1) ∩ 𝐶

𝜌(𝐿2) =
{𝑎, 𝑎2, 𝑎3, 𝑎4, 𝑎5, 𝑏} to illustrate Theorem 2.13. Further, we have  𝐶𝜌(𝐿1) ∪ 𝐶

𝜌𝐿2) =
{𝑎𝜔 , 𝑏, 𝑎𝑏, 𝑎2𝑏, 𝑎3𝑏, 𝑎𝑘 ; 𝑘 ≥ 1} ⊆  𝐶𝜌(𝐿1 ∪ 𝐿2) = {𝑎

𝜔 , 𝑎𝑘 , 𝑎𝑘 𝑏, 𝑏; 𝑘 ≥ 1} to illustrate 
Theorem 2.11. 

 

3. Operation 𝝆𝒏 
3.1 Definition. Given 𝐿1, 𝐿2 ⊆ 𝛴

∞ and 𝑛 ≥ 1, an operation 𝜌𝑛 is defined as follows: 
𝜌𝑛(𝐿1, 𝐿2) = {𝑥𝑢𝑦; 𝑡ℎ𝑒𝑟𝑒 𝑒𝑥𝑖𝑠𝑡𝑠 𝑢 ∈ 𝛴

𝑛  𝑤𝑖𝑡ℎ 𝑥𝑢 ∈ 𝐿1𝑎𝑛𝑑 𝑢𝑦 ∈ 𝐿2}. 

Clearly, for each n, 𝜌𝑛 is the operation on 2
𝛴∞ .  In this manner the set of operations 

on 2𝛴
∞

 is given. Instead of  𝜌𝑛 (𝐿1, 𝐿2) we also write 𝐿1𝜌𝑛 𝐿2. 

3.2 Theorem. (i) Let 𝐿1, 𝐿2 ⊆ 𝛴
𝜔 .  Then for all 𝑛 ≥ 1 there holds 𝐿1𝜌𝑛 𝐿2 = ∅. 

                            (ii) Given 𝐿1, 𝐿2 ⊆ 𝛴
∗ and let 𝐿1 ∪ 𝐿2 be a finite set. Then for all 𝑛 >

max
𝑤∈𝐿1∪𝐿2

|𝑤| here holds 𝐿1𝜌𝑛 𝐿2 = ∅. 

Proof. Both statements (i), (ii) follow immediately from Definition 3.1. 

3.3 Example. (a) Let  𝐿1, 𝐿2 ⊆ {𝑎, 𝑏}
∗, 𝐿1 = {(𝑎𝑏)

𝑘 ; 𝑘 ≥ 1},𝐿2 = {𝑎
𝑘 , 𝑏𝑘 ; 𝑘 ≥ 1}. 

Applying Definition 3.1 we have 𝐿1𝜌1𝐿2 = {𝑎𝑏
𝑘 , (𝑎𝑏)𝑘 , (𝑎𝑏)𝑘 𝑏𝑚; 𝑘, 𝑚 ≥ 1}.  Similarly, 

and with accordance to Theorem  3.2(ii) we get  𝐿1𝜌𝑛𝐿2 = ∅ and  𝐿2𝜌𝑛 𝐿1 = ∅ for any 
𝑛 ≥ 2. (b) Let   𝐿1, 𝐿2, 𝐿3 ⊆ {𝑎, 𝑏}

∞, 𝐿1 = {𝑎
𝑘 , 𝑏; 𝑘 ≥ 1}, 𝐿2 = {𝑎

3, 𝑏2}, 𝐿3 = {𝑎
𝜔 , 𝑎𝑏}. 

Applying Definition 3.1 we have  𝐿1𝜌1𝐿2 = {𝑎
𝑘 , 𝑏2; 𝑘 ≥ 3}, 𝐿2𝜌1𝐿3 =

{𝑎𝜔 , 𝑎3𝑏}, ( 𝐿1𝜌1𝐿2)𝜌1𝐿3 = {𝑎
𝜔 , 𝑎𝑘 𝑏; 𝑘 ≥ 1}, 𝐿1𝜌1(𝐿2𝜌1𝐿3) = {𝑎

𝜔 , 𝑎3𝑏}. 

3.4 Theorem. The operation 𝜌𝑛 is generally 
(i) not commutative, 

(ii) not associative. 

Proof. It follows immediately from the results of Example 3.3. 

3.4 Remark. Theorem 3.4 justifies the conclusion that  the set 2𝛴
∞

 with the operation 

𝜌𝑛 forms a „pure“ groupoid. Also nonexistence of an identity element may be simply 
verified. 

 

4. Conclusion 

In this paper we examined algebraic properties of operations on ∞-words having 
direct relation to ∞-languages generated by ∞- automata. It may motivate to consider 

further types of operations, particularly modeling the depth of memory of such devices. 

133



Ivan Mezník 

 

As a generalization a variant structure of ∞-automata may be considered and the 
corresponding structures of their ∞-languages studied.  

 

References 

[1] J. Chvalina, Š. Hošková-Mayerová, General 𝜔-hyperstructures and certain 
applications of those, Ratio Mathematica 23, 3–20(2012) 

[2] Z. Grodzki, The k-machines, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 
Vol. XVIII, 7, 541–544(1970) 

[3] M. Juráš and I. Mezník, On IG-languages, Mathematics University of Oulu(1992) 

[4] W. Kwasowiec, Generable sets, Information and Control 17, 257–264(1970) 

[5] M. Linna, On ω-sets associated with context-free languages, Inform. and Control 31, 
273-293(1976) 

[6] R. McNaughton, Testing and generating infinite sequences by a finite automaton. 
Inform. and Control 9, 521–530 (1966) 

[7] I. Mezník, On a subclass of ∞-regular languages, Theoretical Computer Science 61, 
25–32(1988) 

[8] I. Mezník, On some structural properties of a subclass of ∞-regular languages, 
Discrete Applied Mathematics 18, 315–319(1987) 

[9] D.E. Muller, Infinite sequences and finite machines, In: IEEE Proc. Fourth Ann. 
Symp. On Switching Theory and Logical Design, 3–16(1963) 

[10] M. Nivat, Infinite words, infinite trees, infinite computations, In: J. W. De Bakker 
and J. Van Leeuwen, eds., Foundations of Computer Science III (Mathematisch Centrum, 

Amsterdam), 5–52(1979) 

[11] M. Novotný, Sets constructed by acceptors, Inform. and Control 26, 116–133(1974) 

[12] Z. Pawlak, Stored program computers. Algorytmy 10, 7–22(1969) 

[13] D. Perrin, An introduction to finite automata on infinite words, Lecture Notes in 
Computer Science 192, 2–17(1984) 

[14] A. Skowron, Languages determined by machine systems, Bull. Acad. Polon. Sci. 
Sér. Sci. Math. Astronom. Phys., Vol.XIX, 4, 327–329(1971) 

[15] L. Staiger, Finite-state ω-languages, J. of Comp. And Syst. Sci. 27, 434–448(1983) 

134