# On Subclasses of Recognizableωω−Partial Array Languages

Authors: G. Muhiuddin; K. Janaki; D. Al-Kadi; R. Arulprakasam; V. Govindan
Journal: Journal of Mathematics
 (2022)

---

## Abstract

In this paper, the concepts of infinite partial array languages (ωω−partial array languages) and the classes of ωω−partial array languages, namely, local ωω−partial array languages, Buchi local ωω−partial array languages, and Muller local ωω−partial array languages are defined, and their related properties are studied. Furthermore, we introduce nondeterministic finite online tessellation h-automata on ωω−partial array languages. In addition, we prove that the class of all adherences of finite local partial array languages is equal to the class of all local ωω−partial array languages and also prove that every ωω−regular partial array language is a projection of Buchi local ωω−partial array language.


---

## Body

## 1. Introduction

We know that genetic instructions are carried out by DNA molecules. Moreover, in DNA computing, DNA strands are viewed as finite words (strings) and utilized to encode information. Some information may be missing or not visible during DNA sequencing which can be disclosed by positions representing the missing symbols in a word. As a result, in gene comparisons, partial words are studied instead of total words. In 1974, partial words were introduced as “strings with do not care symbols” by Fischer and Paterson [1]. Moreover, Berstel and Boasson [2] began the combinatorics on partial words. Also, Blanchet-Sadri has taken the initial step towards studying languages of partial words [3–6]. Recently, Krishna Kumari et al. [7] introduced Fibonacci partial words and established their combinatorial properties such as palindromes and primitivity.Infinite words otherwise known asω−words have been examined exhaustively in formal language theory [8–11]. In [12], Buchi initiated the study of finite state automata on ω−words. Also, Muller [13] proposed an alternative definition of finite state automata on ω−words. Later on, Mercas and Manea [14] broadened the notion of partial words to ω−partial words in 2007. In 2013, Arulprakasam et al. [15, 16] developed the classes of ω−partial languages and also studied the subclasses of ω−partial languages by automata.Researchers have designed and demonstrated that synthetic DNA can assemble into complex species that involve the lateral fusion of DNA double helices such as double cross-over molecules and triple cross-over molecules [17, 18]. Double cross-over molecules and triple cross-over molecules have been used as tiles and building blocks of large nanoscale arrays. Theoretically, it is proven that two-dimensional array is made up of double cross-over molecules or triple cross-over molecules can replicate the characteristics of a bounded one dimensional cellular automaton [19, 20]. The essential part of these results is the natural representation of a local array language with the tiling system and domino system. Inoue et al. studied the nonclosure properties of two-dimensional online tessellation acceptors in [21–23]. Nakamura and Ono [24] extended finite arrays to infinite arrays in 1988. Also, Giammarresi and Restivo [25] extended the principles and techniques of local and recognizable string languages to arrays for the difficulties arising in the framework of image analysis and pattern recognition in 1992. Moreover, Inoue and Takanami [26] analyzed the characterization of recognizable picture languages in 1993. Dare et al. [27] extended local languages to infinite arrays (ωω−arrays) and analyzed their properties. Furthermore, Sweety et al. [28] extended local languages to finite partial array languages. The motivation for studying ωω−arrays originates from the phenomenon that pictures of functions can be viewed as infinite digitized images and henceforth the analysis can naturally be extended to infinite partial arrays (ωω−partial arrays). Extending the finite partial array to infinite partial array over the alphabet is more interesting, and it has been the subject of studying in several investigations arising from the structure of DNA molecules. In this paper, we extend the concept of partial array languages to ωω−partial array languages and also establish the relationship between nondeterministic finite online tessellation h-automata and the subclasses of recognizable ωω−partial array languages.This paper is organized as follows: In Section2, we review the basic terminology and fundamental definitions that will be useful in this study. In Section 3, we propose ωω−partial array languages and the classes of ωω−partial array languages called local ωω−partial array languages, Buchi local ωω−partial array languages, and Muller local ωω−partial array languages and explore their properties. Furthermore, we propose nondeterministic finite online tessellation h-automata on ωω−partial array languages. Furthermore, we prove that the class of all adherence of a finite local partial array languages is equal to the class of all local ωω−partial array languages and also prove that every ωω−regular partial array language is a projection of Buchi local ωω−partial array language.


## 2. Preliminaries

LetΣ be a finite nonempty set of alphabet. A word w of length n over Σ be defined by a total function w:1,…,n⟶Σ which is represented as w=a1a2…an where ai∈Σ. Let λ be the empty word. The set of all finite words over Σ is denoted as Σ∗. An infinite word x over Σ is a function x:N⟶Σ which is represented as w=a1a2…, where ai∈Σ for all i. The set of all infinite words over Σ is denoted as Σω.An array overΣ of size h,v is a two-dimensional rectangular arrangement of symbols from Σ in h rows and v columns. Let the bottom-most row is the first row and the leftmost column is the first column. The set of all arrays over Σ is denoted as Σ∗∗. For any array X of size h,v, X^ is the array of size h+2,v+2 obtained by surrounding X with a special symbol #∉Σ. An infinite array has an infinite number of rows and infinite number of columns. The set of all infinite arrays over Σ is denoted as Σωω. For any array X∈Σωω, X^ is the infinite array obtained by placing a row of #s below the first row of X and placing a column of #s to the left of the first column of X. For X∈Σ∗∗∪Σωω, Br,cX be the set of all blocks of X of size r,c. A square array of size (2, 2) is called a tile. If an array X has entry xi,j∈Σ, then X=xi,j, i=1,…,h; j=1,…,vif X∈Σ∗∗ is of size h,v and X=xi,j, i=1,…; j=1,… if X∈Σωω. If X=xi,j∈Σωω, a prefix of X is an array Y=ai,j, i=1,…,l; j=1,…,r; 1≤l, r<∞. The set of all prefixes of X is denoted as PreX. If L∈Σ∗∗∪Σωω, then(1)PreL=∪X∈LPreX,adhL=X∈Σωω|PreX⊆PreL.A partial wordy of length n over Σ is a partial function y:1,…,n⟶Σ. For 1≤i<n, if yi is defined, then i belongs to domain of yi∈Du; otherwise, i belongs to a set of holes of yi∈Hu. For convenience, hereafter, we will refer to a partial word over Σ as a word over the enlarged alphabet Σp=Σ∪⋄ where ⋄∉Σ represents a hole. The set of all partial words over Σp of finite length is denoted as Σp∗. An infinite partial word z over Σp is a partial function z:N⟶Σp which is represented as z=a1a2⋯ where ai∈Σp for all i. The set of all infinite words over Σp is denoted as Σpω.A partial array of sizeh,v over Σp is a partial function X:Z+2⟶Σp, where Z is the set of all positive integers. For 1≤i≤h, 1≤j≤v, if Xi,j is defined, then i,j belongs to a domain of Xi,j∈DX; otherwise, i,j belongs to a set of holes of Xi,j∈HX. An array is a partial array over Σp with an empty set of holes. The set of all partial arrays over Σp is denoted as Σp∗∗. Let ∧ be the empty array with no symbols. A language L⊆Σp∗∗ is local if there exists a finite set θ of tiles over Σp∪⋄ such that(2)L=X∈Σp∗∗|B2,2X^⊆θ.


## 3. Online Tessellationh−Automaton on ωω−Partial Array Languages

A two-dimensional online tessellation automaton is a restricted type of cellular automata in which cells do not make transitions at every time step, rather a transition wave passes once diagonally across the array. Each cell changes its state depending on the two neighbors to the top and to the left, respectively. Sweety et al. [28] has introduced online tessellation partial automata to recognize the finite partial array languages. In this section, we extend this idea to ωω−partial array languages. We introduce nondeterministic finite online tessellation h−automaton (the automata to accept infinite partial array language) with acceptance condition on ωω−partial array.Definition 1.
A infinite partial array (ωω− partial array) X over Σp is of the form(3)X=aij=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅a21a22⋅⋅⋅a11a12⋅⋅⋅,where aij∈Σp for 1≤i≤∞ and 1≤j≤∞. The collection of all ωω− partial array over Σ is represented by Σpωω.LetΣp2×2 be the collection of all partial arrays of order 2×2 over Σp. For any X∈Σpωω, then the set of all subarrays of order 2×2 is denoted as B22X^ and the set of all subarrays in B22X^ that exist as subarrays infinitely many times in X is denoted as infB22X^.Definition 2.
A nondeterministic finite online tessellationh-automaton (ND-OThA) is a quintuple ℳ=Sp,Σp,δ,S0,Sf where(i)
Sp=S∪Sh and S∩Sh=∅ in which S be the finite collection of states and Sh be the finite collection of hole states(ii)
Σp be the input alphabet(iii)
S0⊂Sp be the collection of initial states(iv)
Sf⊆Sp be the collection of final states(v)
δ:Sp×Sp×Σp⟶2Sp be the transition function defined as follows:(1)
δs1,s2,a=s3;s1,s2,s3∈S,a∈Σ(2)
δs,sh,a=s1;s,s1∈S,sh∈Sh,a∈Σ(3)
δsh,s,a=s1;s,s1∈S,sh∈Sh,a∈Σ(4)
δsh1,sh2,a=s;s∈S,sh1,sh2∈Sh,a∈Σ(5)
δs1,s2,⋄=sh;s1,s2∈S,sh∈Sh(6)
δs,sh,⋄=sh1;s∈S,sh,sh1∈Sh(7)
δsh,s,⋄=sh1;s∈S,sh,sh1∈Sh(8)
δsh1,sh2,⋄=sh3;sh1,sh2,sh3∈Sh.A computation is done by a ND-OThA on anωω−partial array X, where(4)X^=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#⋅⋅⋅⋅⋅⋅⋅#a21a22⋅⋅⋅⋅⋅#a11a12⋅⋅⋅⋅⋅###⋅⋅⋅⋅⋅,with aij∈Σp and #∉Σp is consummated as follows.Whent=0, s0∈S0 be the initial state corresponding to all positions of X^ having #. The state corresponding to each position i,j by δ is subject to the states corresponding to the positions i−1,j and i,j−1 and the symbol aij. If aij∈Σ, then gij is the state corresponding to the position i,j, and if aij=⋄, then hij is the state corresponding to the position i,j. When t=1, a state from δs0,s0,a11 corresponds to the position 1,1 holding a11. If a11∈Σ, then the state g11 corresponds to the position 1,1, and if a11=⋄, then the state h11 corresponds to the position 1,1. When t=2, states correspond concurrently to the positions 2,1 and 1,2 possessing a21 and a12 and so on.Case 1.
If the stateg11 corresponds to the position 1,1, then the state corresponding to the position 2,1 belongs to δs0,g11,a21 and to the position 1,2 belongs to δg11,s0,a12. These are given as follows:(i)
δs0,g11,a21=g21 if a21∈Σ(ii)
δg11,s0,a12=g12 if a12∈Σ(iii)
δs0,g11,⋄=h21(iv)
δg11,s0,⋄=h12Case 2.
If the stateh11 corresponds to the position 1,1, then the state corresponding to the position 2,1 belongs to δs0,h11,a21 and to the position 1,2 belongs to δh11,s0,a12. These are given as follows:(i)
δs0,h11,a21=g21 if a21∈Σ(ii)
δh11,s0,a12=g12 if a12∈Σ(iii)
δs0,h11,⋄=h21(iv)
δh11,s0,⋄=h12
IfX∈Σpωω, the sequence σ=s11s12s21s31s22s13… of states from Sp is said to be a run of ℳ and it is an element of Spω. The range of σ denoted by rσ is the set s11,s12,s21,s31,…, and infσ denotes the set of all sets which occurs infinitely many times in σ. Now, we say the following:(1)
The runσ is accepted by ℳ in ran,⊆-mode if ranσ⊆Sf(2)
The runσ is accepted by ℳ in inf,∩-mode if infσ∩Sf≠0(3)
The runσ is accepted by ℳ in inf,⊆-mode if infσ⊆Sf(4)
For a ND-OThA that is a quintupleℳ=Sp,Σp,δ,S0,Sℱ where Sℱ⊆2Sp, we say that the run σ is accepted by ℳ in inf,=-mode if infσ∈Sℱ.
Anωω− partial array language L⊆Σpωω is said to be accepted or recognized by ℳ in x-mode, if(5)L=Lωωℳ=X∈Σpωω:arunσexists for whichℳinx−mode acceptsX.
Anωω−partial array L is said to be an ωω−regular partial array language if there exists ℳ in inf,∩-mode such that L=Lωωℳ.Example 1.
Consider a ND-OThA, andℳ=Sp,Σp,δ,S0,Sf, where Sp=s0,s1,s2,sh, Σp=α,β∪⋄, S0=s0, and Sf=s2,sh, and the transition function δ is defined as follows:δs0,s0,α=δs1,s0,α=δs0,s1,α=δs1,s1,α=s1δs1,s0,β=δs2,s0,β=δs1,s2,β=δs2,s2,β=δsh,s1,β=δsh,s2,β=s2δso,s1,⋄=δso,sh,⋄=sh
Then, the ND-OThAℳ recognizes the ωω−partial array language L=Lωωℳ=Ar,c∈Σpωω/1≤r,c<∞ in inf,∩-mode, where(6)Ar,c=#⋄y⋅⋅⋅yyy⋅#⋄y⋅⋅⋅yyy⋅#xx⋅⋅⋅xyy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅⋅xyy⋅#xx⋅⋅⋅xyy⋅###⋅⋅⋅###⋅.
Fori,jth positions,(7)entries inAr,c=x,if1≤i≤r,1≤j≤c,⋄,ifαi,1wherei>r,y,remaining positions.


### 3.1. Localωω−Partial Array Languages

Sweety et al. [28] provided automata characterization of finite local partial array languages. Here, we define a subclass of ωω−partial array languages termed as local ωω−partial array languages and obtain the automata characterization of local ωω−partial array languages.Definition 3.
Anωω−partial array language L⊆Σpωω is called a local ωω−partial array language if a set of tile J⊆Σp2×2 exists with(8)L=X∈Σpωω:B22X^⊆J,where we consider L=LωωJ. The class of all local ωω−partial array languages is represented by Llpωω.Example 2.
Consider the set of tilesJ⊆Σp2×2 over Σp:(9)J=#x#x#y#yxxx⋄⋄yyy##,#x,#x,#y,##,##,##,##,xxx⋄⋄yyyy⋄y⋄yyxx,x⋄,⋄y,xx,x⋄,y⋄,yy.
Then,L=LωωJ=Ar,c/r,c≥1∪B, where(10)Ar,c=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅y⋄yy⋅#xx⋅⋅x⋄yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅######⋅⋅⋅⋅.
Fori,jth positions,(11)entries inAr,c=x,if1≤i≤r,1≤j≤c,⋄,ifj=c+1,y,remaining positions,and(12)B=⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅⋅xx⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅⋅xx⋅#xx⋅⋅⋅xx⋅###⋅⋅⋅##⋅.
Hence,L included local ωω−partial array languages. Some members of these languages are given as follows:(13)⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yyy⋄yy⋅⋅#yyy⋄yy⋅⋅#xxx⋄yy⋅⋅#xxx⋄yy⋅⋅#######⋅⋅,⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋄yy⋅⋅⋅#xx⋄yy⋅⋅⋅#xx⋄yy⋅⋅⋅#xx⋄yy⋅⋅⋅######⋅⋅⋅,⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xxxxx⋅⋅⋅#xxxxx⋅⋅⋅#xxxxx⋅⋅⋅#xxxxx⋅⋅⋅######⋅⋅⋅,…….Theorem 1.
Intersection of any two localωω−partial array languages is also a local ωω−partial array language.Proof.
Let the localωω−partial array languages over Σp be L1 and L2. Then, there exist the sets J1,J2⊆Σp2×2 such that L1=LωωJ1 and L2=LωωJ2, respectively. Consider the set J, where J=J1∩J2; then, LωωJ=LωωJ1∩LωωJ2. Therefore, L1∩L2 is a local ωω−partial array language over Σp.Theorem 2.
Union of any two localωω−partial array languages need not be a local ωω−partial array language.Proof.
Assume the localωω−partial array languages over Σp are L1 and L2. Then, there exist the sets J1,J2⊆Σp2×2 such that L1=LωωJ1 and L2=LωωJ2, respectively. For instance, L1=Ar,c/1≤r,c<∞∪B and L2=Cr,c/1≤r,c<∞∪D, where(14)Ar,c=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅y⋄yy⋅#xx⋅⋅x⋄yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅#########⋅.
Fori,jth positions,(15)entries inAr,c=x,if1≤i≤r,1≤j≤c,⋄,ifj=c+1,y,remaining positions.We have(16)B=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅⋅xx⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅⋅xx⋅⋅#xx⋅⋅⋅xx⋅⋅###⋅⋅⋅##⋅⋅,and(17)Cr,c=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄xx⋅#yy⋅⋅y⋄xx⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅y⋄xx⋅#yy⋅⋅y⋄xx⋅#########⋅.
Fori,jth positions,(18)entries inCr,c=⋄,ifj=c+1,y,if1≤i≤r,1≤j≤c,x,remaining positions,and(19)D=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅⋅yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅⋅yy⋅⋅#yy⋅⋅⋅yy⋅⋅###⋅⋅⋅##⋅⋅.
IfL1∪L2 included local ωω−partial array languages, then an ωω−array,(20)⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅⋅yy⋅⋅#xx⋅⋅⋅xx⋅⋅#yy⋅⋅⋅yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅⋅yy⋅⋅#yy⋅⋅⋅yy⋅⋅###⋅⋅⋅##⋅⋅,is in L1∪L2. Therefore, L1∪L2∉Llpωω.Theorem 3.
IfLlp is the class of all finite local partial array languages and Llpωω is the class of all local ωω−partial array languages, then Llpωω=adhLlp.Proof.
Consider theωω−partial arrays X∈Σpωω and Y∈Σp∗∗. Let L∈Llpωω be the local ωω−partial array language and L″∈Llp be the finite local partial array language such that L=X∈Σpωω:B22X^⊆J and L″=Y∈Σp∗∗:B22Y^⊆J for some J⊆Σp2×2. Now, we will show that L=adhL″. For this, suppose(21)X∈adhL″⇔PreX⊆PreL″⇔B22PreX⊆B22PreL″⇔B22X^⊆J⇔X∈L,such that L=adhL″ which implies Llpωω⊆adhLlp.
Similarly,adhLlp⊆Llpωω. Consequently, we have Llpωω=adhLlp.Theorem 4.
IfL⊆Σpωω is a local ωω−partial array language, then L is recognized by a ND-OThA in ran,⊆-mode.Proof.
Assume a localωω−partial array language L such that(22)L=X∈Σpωω:B22X^⊆J,where the set J⊆Σp2×2. Consider the ND-OThA ℳ=Sp,Σp,δ,S0,Sf. Now, we define ℳ corresponding to L.
LetSp=J; then,(23)δ:Sp×Sp×Σp⟶2Sp such that Sf=Sp.
Therefore,L=Lωωℳ in ran,⊆-mode.Theorem 5.
IfL⊆Σpωω is recognized by a ND-OThA in ran,⊆-mode, then L is a local ωω−partial array language.Proof.
LetL⊆Σpωω is recognized by a ND-OThA, ℳ=Sp,Σp,δ,S0,Sf in ran,⊆-mode. Now, we define a local ωω−partial array language corresponding to ℳ. Let Γp=Σp∪#×Sp and J=Sp, and let(24)where J=∪i=111Ji. Consider the local ωω− partial array language L″ corresponding to the collection J. Let ψ:Γp⟶Σp be such that(i)
ψa,s=a where s∈Sp and a∈Σ∪#(ii)
ψ⋄,s=⋄ where s∈Sp.
Hence,ψL″=L. Therefore, L is a local ωω−partial array language.


### 3.2. Buchi Localωω−Partial Array Languages

In this section, we introduce the class of Buchi localωω−partial array languages and prove that every ωω−regular partial array language is a projection of a Buchi local ωω− partial array language.Definition 4.
Anωω−partial array language L⊆Σpωω is called Buchi local ωω−partial array language if there exists the system Q=J,J1, where J⊆Σp2×2 and J1⊆J such that(25)L=X∈Σpωω:B22X^⊆JandinfB22X^∩J1≠∅,where we consider L=LblpωωQ. The class of all Buchi local ωω−partial array languages is represented by Lblpωω.Example 3.
Consider the systemQ=J,J1, where(26)J=#x#x#⋄#y#yxxx⋄⋄y##,#x,#x,#⋄,#y,##,##,##,yyxxx⋄⋄y⋄⋄⋄⋄yyxy##,xx,x⋄,⋄y,xx,x⋄,⋄⋄,yy,and(27)J1=yyyy.
Then,L=LblpωωQ=Ar,c/1≤r,c<∞∪Bc/1≤c<∞∪Cr/1≤r<∞ where(28)Ar,c=#yy⋅⋅yyyy⋅#⋄⋄⋅⋅⋄⋄⋄⋄⋅#xx⋅⋅x⋄yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅#########⋅.
Fori,jth positions,(29)entries inAr,c=x,if1≤i≤r,1≤j≤c,⋄,ifi=r+1,j=c+1,y,remaining positions,and(30)Bc=#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅#########⋅.
Fori,jth positions,(31)entries inBc=x,ifi≥1,1≤j≤c,⋄,ifj=c+1,y,remaining positions,and(32)Cr=#yy⋅⋅yyyy⋅#yy⋅⋅yyyy⋅#⋄⋄⋅⋅⋄⋄⋄⋄⋅#xx⋅⋅xxxx⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅xxxx⋅#xx⋅⋅xxxx⋅#########⋅.
Fori,jth positions,(33)entriesinCr=x,ifj≥1,1≤i≤r,⋄,ifi=r+1,y,remaining positions.
Therefore,L includes Buchi local ωω−partial array languages.Theorem 6.
Intersection of any two Buchi localωω− partial array languages need not be a Buchi local ωω−partial array language.Proof.
LetL1 and L2 be two Buchi local ωω−partial array languages over Σp. Then, there exist the systems Q=J1,J3 and Q′=J2,J4 where J1,J2⊆Σp2×2 and J3⊆J1,J4⊆J2 such that L1=LblpωωQ and L2=LblpωωQ′, respectively. Now, consider the system Q″=J,J′ where J=J1∩J2 and J′=J3∩J4. Suppose J3 and J4 may have an empty intersection, but some words may have infinitely many occurrences of a pattern of J3 and of another pattern of J4, providing a word in the intersection of L1 and L2. Take, for example, J1=J2 that contain all 2×2 words, J3 that only contains the 2×2 block a′s, and J4 that only contains the 2×2 block b′s. Then, the intersection contains those words that have infinitely many a−blocks and infinitely many b−blocks. This is not a Buchi local ωω−partial array language. Hence, L1∩L2 need not be a Buchi local ωω−partial array language over Σp.Theorem 7.
Union of any two Buchi localωω−partial array languages is also a Buchi local ωω−partial array language.Proof.
LetL1 and L2 be two Buchi local ωω−partial array languages over Σp. Then, there exist the systems Q=J1,J3 and Q′=J2,J4 where J1,J2⊆Σp2×2 and J3⊆J1,J4⊆J2 such that L1=LblpωωQ and L2=LblpωωQ′, respectively. Now, consider the system Q″=J,J′ where J=J1∪J2 and J′=J3∪J4; then, LblpωωQ″=LblpωωQ∪LblpωωQ′. Therefore, L1∪L2 is a Buchi local ωω−partial array language over Σp.Remark 1.
Llpωω⊂Lblpωω.Theorem 8.
IfL⊆Σpωω is a Buchi local ωω− partial array language, then L is recognized by a ND-OThA in inf,∩-mode.Proof.
LetL be a Buchi local ωω−partial array language. Then, there exists the system Q=J,J1, where J⊆Σp2×2 and J⊆J1 such that(34)L=X∈Σpωω:B22X^⊆JandinfB22X^∩J1≠∅.
Consider the ND-OThA,ℳ=Sp,Σp,δ,S0,Sf. Now, we define ℳ corresponding to L.
LetSp=J. Then,(35)δ:Sp×Sp×Σp⟶2Sp. Consequently, L=Lωωℳ in inf,∩-mode.Theorem 9.
Everyωω−regular partial array language is a projection of a Buchi local ωω−partial array language.Proof.
LetL⊆Σpωω be a ωω−regular partial array language. Then, L is recognized by a ND-OThA ℳ=Sp,Σp,δ,S0,Sf in inf,∩-mode. Now, we define a Buchi local ωω−partial array language corresponding to ℳ. Let Γp=Σp∪#×Sp and J=Sp, and let(36)where J=∪i=111Ji and J1=J11, i.e., a set of infinitely often repeating subarrays of size 2×2. Consider L″ as the Buchi local ωω−partial array language corresponding to the system Q=J,J1 where J1⊆J. Let ψ:Γp⟶Σp, such that(i)
ψa,s=a where s∈Sp and a∈Σ∪#(ii)
ψ⋄,s=⋄ where s∈Sp
Hence,ψL″=L. Therefore, L is a projection of Buchi local ωω−partial array language.


### 3.3. Muller Localωω−Partial Array Languages

In this section, we define Muller localωω−partial array language and show that the class of Muller local ωω−partial array languages is the same as the class of ωω−partial array languages recognized by a ND-OThA in inf,=-mode.Definition 5.
Anωω−partial array language L⊆Σpωω is called Muller local ωω− partial array language if there exists the system R=J,J″, where J⊆Σp2×2 and J″⊆2J such that(37)L=X∈Σpωω:B22X^⊆JandinfB22X^∈J′′.
In this case, we denoteL=LMlpωωR. The class of all Muller local ωω− partial array languages is represented by LMlpωω.Theorem 10.
IfL⊆Σpωω is a Muller local ωω− partial array language if and only if L is recognized by a ND-OThA in inf,=-mode.Proof.
LetL∈Σpωω be an ωω−partial array language recognized by a ND-OThA ℳ=Sp,Σp,δ,S0,Sℱ in inf,=-mode, i.e.,L=Lωωℳ. Now, we define Muller local ωω− partial array languages corresponding to ℳ. Let Γp=Σp∪#×Sp, and let(38)Let(39)where Sℱ=F1,F2,…,Fn. Let L′′ be the Muller local ωω−partial array language corresponding to the system R=J,J″, where J=J11i:i=1,2,…,n. Let ψ:Γp⟶Σp be such that(i)
ψa,q=a where q∈Sp and a∈Σ∪#(ii)
ψ⋄,q=⋄ where q∈Sp
Hence,ψL″=L. Consequently, L is a Muller local ωω−partial array language.
Conversely, letL=X∈Σpωω:B22X^⊆JandinfB22X^∈J″ be a Muller local ωω−partial array language. Define ℳ corresponding to the language L. Let us consider S=J. Then,(40)
Let the transition functionδ:Sp×Sp×Σp⟶2Sp.(41)
Then, we have(42)and(43)
Therefore,L=Lωωℳ. This completes the proof.


## 3.1. Localωω−Partial Array Languages

Sweety et al. [28] provided automata characterization of finite local partial array languages. Here, we define a subclass of ωω−partial array languages termed as local ωω−partial array languages and obtain the automata characterization of local ωω−partial array languages.Definition 3.
Anωω−partial array language L⊆Σpωω is called a local ωω−partial array language if a set of tile J⊆Σp2×2 exists with(8)L=X∈Σpωω:B22X^⊆J,where we consider L=LωωJ. The class of all local ωω−partial array languages is represented by Llpωω.Example 2.
Consider the set of tilesJ⊆Σp2×2 over Σp:(9)J=#x#x#y#yxxx⋄⋄yyy##,#x,#x,#y,##,##,##,##,xxx⋄⋄yyyy⋄y⋄yyxx,x⋄,⋄y,xx,x⋄,y⋄,yy.
Then,L=LωωJ=Ar,c/r,c≥1∪B, where(10)Ar,c=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅y⋄yy⋅#xx⋅⋅x⋄yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅######⋅⋅⋅⋅.
Fori,jth positions,(11)entries inAr,c=x,if1≤i≤r,1≤j≤c,⋄,ifj=c+1,y,remaining positions,and(12)B=⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅⋅xx⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅⋅xx⋅#xx⋅⋅⋅xx⋅###⋅⋅⋅##⋅.
Hence,L included local ωω−partial array languages. Some members of these languages are given as follows:(13)⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yyy⋄yy⋅⋅#yyy⋄yy⋅⋅#xxx⋄yy⋅⋅#xxx⋄yy⋅⋅#######⋅⋅,⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋄yy⋅⋅⋅#xx⋄yy⋅⋅⋅#xx⋄yy⋅⋅⋅#xx⋄yy⋅⋅⋅######⋅⋅⋅,⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xxxxx⋅⋅⋅#xxxxx⋅⋅⋅#xxxxx⋅⋅⋅#xxxxx⋅⋅⋅######⋅⋅⋅,…….Theorem 1.
Intersection of any two localωω−partial array languages is also a local ωω−partial array language.Proof.
Let the localωω−partial array languages over Σp be L1 and L2. Then, there exist the sets J1,J2⊆Σp2×2 such that L1=LωωJ1 and L2=LωωJ2, respectively. Consider the set J, where J=J1∩J2; then, LωωJ=LωωJ1∩LωωJ2. Therefore, L1∩L2 is a local ωω−partial array language over Σp.Theorem 2.
Union of any two localωω−partial array languages need not be a local ωω−partial array language.Proof.
Assume the localωω−partial array languages over Σp are L1 and L2. Then, there exist the sets J1,J2⊆Σp2×2 such that L1=LωωJ1 and L2=LωωJ2, respectively. For instance, L1=Ar,c/1≤r,c<∞∪B and L2=Cr,c/1≤r,c<∞∪D, where(14)Ar,c=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅y⋄yy⋅#xx⋅⋅x⋄yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅#########⋅.
Fori,jth positions,(15)entries inAr,c=x,if1≤i≤r,1≤j≤c,⋄,ifj=c+1,y,remaining positions.We have(16)B=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅⋅xx⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅⋅xx⋅⋅#xx⋅⋅⋅xx⋅⋅###⋅⋅⋅##⋅⋅,and(17)Cr,c=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄xx⋅#yy⋅⋅y⋄xx⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅y⋄xx⋅#yy⋅⋅y⋄xx⋅#########⋅.
Fori,jth positions,(18)entries inCr,c=⋄,ifj=c+1,y,if1≤i≤r,1≤j≤c,x,remaining positions,and(19)D=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅⋅yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅⋅yy⋅⋅#yy⋅⋅⋅yy⋅⋅###⋅⋅⋅##⋅⋅.
IfL1∪L2 included local ωω−partial array languages, then an ωω−array,(20)⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅⋅yy⋅⋅#xx⋅⋅⋅xx⋅⋅#yy⋅⋅⋅yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#yy⋅⋅⋅yy⋅⋅#yy⋅⋅⋅yy⋅⋅###⋅⋅⋅##⋅⋅,is in L1∪L2. Therefore, L1∪L2∉Llpωω.Theorem 3.
IfLlp is the class of all finite local partial array languages and Llpωω is the class of all local ωω−partial array languages, then Llpωω=adhLlp.Proof.
Consider theωω−partial arrays X∈Σpωω and Y∈Σp∗∗. Let L∈Llpωω be the local ωω−partial array language and L″∈Llp be the finite local partial array language such that L=X∈Σpωω:B22X^⊆J and L″=Y∈Σp∗∗:B22Y^⊆J for some J⊆Σp2×2. Now, we will show that L=adhL″. For this, suppose(21)X∈adhL″⇔PreX⊆PreL″⇔B22PreX⊆B22PreL″⇔B22X^⊆J⇔X∈L,such that L=adhL″ which implies Llpωω⊆adhLlp.
Similarly,adhLlp⊆Llpωω. Consequently, we have Llpωω=adhLlp.Theorem 4.
IfL⊆Σpωω is a local ωω−partial array language, then L is recognized by a ND-OThA in ran,⊆-mode.Proof.
Assume a localωω−partial array language L such that(22)L=X∈Σpωω:B22X^⊆J,where the set J⊆Σp2×2. Consider the ND-OThA ℳ=Sp,Σp,δ,S0,Sf. Now, we define ℳ corresponding to L.
LetSp=J; then,(23)δ:Sp×Sp×Σp⟶2Sp such that Sf=Sp.
Therefore,L=Lωωℳ in ran,⊆-mode.Theorem 5.
IfL⊆Σpωω is recognized by a ND-OThA in ran,⊆-mode, then L is a local ωω−partial array language.Proof.
LetL⊆Σpωω is recognized by a ND-OThA, ℳ=Sp,Σp,δ,S0,Sf in ran,⊆-mode. Now, we define a local ωω−partial array language corresponding to ℳ. Let Γp=Σp∪#×Sp and J=Sp, and let(24)where J=∪i=111Ji. Consider the local ωω− partial array language L″ corresponding to the collection J. Let ψ:Γp⟶Σp be such that(i)
ψa,s=a where s∈Sp and a∈Σ∪#(ii)
ψ⋄,s=⋄ where s∈Sp.
Hence,ψL″=L. Therefore, L is a local ωω−partial array language.


## 3.2. Buchi Localωω−Partial Array Languages

In this section, we introduce the class of Buchi localωω−partial array languages and prove that every ωω−regular partial array language is a projection of a Buchi local ωω− partial array language.Definition 4.
Anωω−partial array language L⊆Σpωω is called Buchi local ωω−partial array language if there exists the system Q=J,J1, where J⊆Σp2×2 and J1⊆J such that(25)L=X∈Σpωω:B22X^⊆JandinfB22X^∩J1≠∅,where we consider L=LblpωωQ. The class of all Buchi local ωω−partial array languages is represented by Lblpωω.Example 3.
Consider the systemQ=J,J1, where(26)J=#x#x#⋄#y#yxxx⋄⋄y##,#x,#x,#⋄,#y,##,##,##,yyxxx⋄⋄y⋄⋄⋄⋄yyxy##,xx,x⋄,⋄y,xx,x⋄,⋄⋄,yy,and(27)J1=yyyy.
Then,L=LblpωωQ=Ar,c/1≤r,c<∞∪Bc/1≤c<∞∪Cr/1≤r<∞ where(28)Ar,c=#yy⋅⋅yyyy⋅#⋄⋄⋅⋅⋄⋄⋄⋄⋅#xx⋅⋅x⋄yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅#########⋅.
Fori,jth positions,(29)entries inAr,c=x,if1≤i≤r,1≤j≤c,⋄,ifi=r+1,j=c+1,y,remaining positions,and(30)Bc=#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅x⋄yy⋅#xx⋅⋅x⋄yy⋅#########⋅.
Fori,jth positions,(31)entries inBc=x,ifi≥1,1≤j≤c,⋄,ifj=c+1,y,remaining positions,and(32)Cr=#yy⋅⋅yyyy⋅#yy⋅⋅yyyy⋅#⋄⋄⋅⋅⋄⋄⋄⋄⋅#xx⋅⋅xxxx⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅#xx⋅⋅xxxx⋅#xx⋅⋅xxxx⋅#########⋅.
Fori,jth positions,(33)entriesinCr=x,ifj≥1,1≤i≤r,⋄,ifi=r+1,y,remaining positions.
Therefore,L includes Buchi local ωω−partial array languages.Theorem 6.
Intersection of any two Buchi localωω− partial array languages need not be a Buchi local ωω−partial array language.Proof.
LetL1 and L2 be two Buchi local ωω−partial array languages over Σp. Then, there exist the systems Q=J1,J3 and Q′=J2,J4 where J1,J2⊆Σp2×2 and J3⊆J1,J4⊆J2 such that L1=LblpωωQ and L2=LblpωωQ′, respectively. Now, consider the system Q″=J,J′ where J=J1∩J2 and J′=J3∩J4. Suppose J3 and J4 may have an empty intersection, but some words may have infinitely many occurrences of a pattern of J3 and of another pattern of J4, providing a word in the intersection of L1 and L2. Take, for example, J1=J2 that contain all 2×2 words, J3 that only contains the 2×2 block a′s, and J4 that only contains the 2×2 block b′s. Then, the intersection contains those words that have infinitely many a−blocks and infinitely many b−blocks. This is not a Buchi local ωω−partial array language. Hence, L1∩L2 need not be a Buchi local ωω−partial array language over Σp.Theorem 7.
Union of any two Buchi localωω−partial array languages is also a Buchi local ωω−partial array language.Proof.
LetL1 and L2 be two Buchi local ωω−partial array languages over Σp. Then, there exist the systems Q=J1,J3 and Q′=J2,J4 where J1,J2⊆Σp2×2 and J3⊆J1,J4⊆J2 such that L1=LblpωωQ and L2=LblpωωQ′, respectively. Now, consider the system Q″=J,J′ where J=J1∪J2 and J′=J3∪J4; then, LblpωωQ″=LblpωωQ∪LblpωωQ′. Therefore, L1∪L2 is a Buchi local ωω−partial array language over Σp.Remark 1.
Llpωω⊂Lblpωω.Theorem 8.
IfL⊆Σpωω is a Buchi local ωω− partial array language, then L is recognized by a ND-OThA in inf,∩-mode.Proof.
LetL be a Buchi local ωω−partial array language. Then, there exists the system Q=J,J1, where J⊆Σp2×2 and J⊆J1 such that(34)L=X∈Σpωω:B22X^⊆JandinfB22X^∩J1≠∅.
Consider the ND-OThA,ℳ=Sp,Σp,δ,S0,Sf. Now, we define ℳ corresponding to L.
LetSp=J. Then,(35)δ:Sp×Sp×Σp⟶2Sp. Consequently, L=Lωωℳ in inf,∩-mode.Theorem 9.
Everyωω−regular partial array language is a projection of a Buchi local ωω−partial array language.Proof.
LetL⊆Σpωω be a ωω−regular partial array language. Then, L is recognized by a ND-OThA ℳ=Sp,Σp,δ,S0,Sf in inf,∩-mode. Now, we define a Buchi local ωω−partial array language corresponding to ℳ. Let Γp=Σp∪#×Sp and J=Sp, and let(36)where J=∪i=111Ji and J1=J11, i.e., a set of infinitely often repeating subarrays of size 2×2. Consider L″ as the Buchi local ωω−partial array language corresponding to the system Q=J,J1 where J1⊆J. Let ψ:Γp⟶Σp, such that(i)
ψa,s=a where s∈Sp and a∈Σ∪#(ii)
ψ⋄,s=⋄ where s∈Sp
Hence,ψL″=L. Therefore, L is a projection of Buchi local ωω−partial array language.


## 3.3. Muller Localωω−Partial Array Languages

In this section, we define Muller localωω−partial array language and show that the class of Muller local ωω−partial array languages is the same as the class of ωω−partial array languages recognized by a ND-OThA in inf,=-mode.Definition 5.
Anωω−partial array language L⊆Σpωω is called Muller local ωω− partial array language if there exists the system R=J,J″, where J⊆Σp2×2 and J″⊆2J such that(37)L=X∈Σpωω:B22X^⊆JandinfB22X^∈J′′.
In this case, we denoteL=LMlpωωR. The class of all Muller local ωω− partial array languages is represented by LMlpωω.Theorem 10.
IfL⊆Σpωω is a Muller local ωω− partial array language if and only if L is recognized by a ND-OThA in inf,=-mode.Proof.
LetL∈Σpωω be an ωω−partial array language recognized by a ND-OThA ℳ=Sp,Σp,δ,S0,Sℱ in inf,=-mode, i.e.,L=Lωωℳ. Now, we define Muller local ωω− partial array languages corresponding to ℳ. Let Γp=Σp∪#×Sp, and let(38)Let(39)where Sℱ=F1,F2,…,Fn. Let L′′ be the Muller local ωω−partial array language corresponding to the system R=J,J″, where J=J11i:i=1,2,…,n. Let ψ:Γp⟶Σp be such that(i)
ψa,q=a where q∈Sp and a∈Σ∪#(ii)
ψ⋄,q=⋄ where q∈Sp
Hence,ψL″=L. Consequently, L is a Muller local ωω−partial array language.
Conversely, letL=X∈Σpωω:B22X^⊆JandinfB22X^∈J″ be a Muller local ωω−partial array language. Define ℳ corresponding to the language L. Let us consider S=J. Then,(40)
Let the transition functionδ:Sp×Sp×Σp⟶2Sp.(41)
Then, we have(42)and(43)
Therefore,L=Lωωℳ. This completes the proof.


## 4. Conclusion

In the present paper, we have defined the concepts of infinite partial array languages (ωω−partial array languages) and the classes of ωω−partial array languages such as local ωω−partial array languages, Buchi local ωω−partial array languages, and Muller local ωω−partial array languages and studied their related properties. Also, we have proposed nondeterministic finite online tessellation h-automata on ωω−partial array languages. In addition, we have proved that the class of all adherence of finite local partial array languages is equal to the class of all local ωω−partial array languages and also shown that every ωω−regular partial array language is a projection of Buchi local ωω−partial array language.



---

*Source: 1493126-2022-09-12.xml*