11institutetext: Department of Mathematics, Indian Institute of Technology
Madras,
Chennai-600036, India.
11email<EMAIL_ADDRESS>
11email<EMAIL_ADDRESS>
# Generalized Circular One-Way Jumping Finite Automata

Ujjwal Kumar Mishra  Kalpana Mahalingam  Rama Raghavan

###### Abstract

A discontinuous model of computation called one-way jumping finite automata
was defined by H. Chigahara et. al. This model was a restricted version of the
model jumping finite automata. One-way jumping finite automata change their
states after deleting a letter of an input and jump only in one direction.
Allowing a state to delete a subword instead of a letter, we define a new
model generalized circular one-way jumping finite automata. These automata
work on an input in a circular manner. Similar to one-way jumping finite
automata, generalized circular one-way jumping finite automata also jump only
in one direction. We show that this newly defined model is powerful than one-
way jumping finite automata. We define new variants(right and left) of the
model generalized circular one-way jumping finite automata and compare them.
We also compare the newly defined model with Chomsky hierarchy. Finally, we
explore closure properties of the model.

###### Keywords:

Jumping Finite Automata One-Way Jumping Finite Automata Generalized Linear
One-Way Jumping Finite Automata Generalized Circular One-Way Jumping Finite
Automata.

##  1 Introduction

General jumping finite automata $\it{(GJFA)}$, very first discontinuous model
of computation, were introduced in [14] by Meduna et. al. These automata read
and delete an input in a discontinuous manner. The automata can jump in either
direction to delete the input. The model was extensively studied in [16, 17,
4, 8]. Following [14], several jumping transition models have been introduced
and studied in the last few years [5, 15, 10, 2, 6, 9, 13, 11, 7].

The model which is of our interest is one-way jumping finite automata
($\it{OWJFA}$), was defined in [5]. The model $\it{OWJFA}$ was defined by
giving a restriction on jumping behaviour of the model jumping finite automata
($\it{JFA}$), a restricted variant of $\it{GJFA}$. There are two variants of
$\it{OWJFA}$: right one-way jumping finite automata ($\it{ROWJFA}$) and left
one-way jumping finite automata ($\it{LOWJFA}$). $\it{ROWJFA}$ starts
processing an input string from the leftmost symbol of the input whereas
$\it{LOWJFA}$ starts processing an input string from the rightmost symbol. The
models can only jump over symbols which they cannot process in its current
state. Some properties of $\it{ROWJFA}$ are given in [3]. The decision
problems of the model $\it{ROWJFA}$ are discussed in [1]. Nondeterministic
variant of the model $\it{ROWJFA}$ is defined and studied in [2].

$\it{OWJFA}$ processes one symbol at a time, i.e., it go from one state to
another by deleting a symbol. One extension of this model that changes its
states by deleting a subword is generalized linear one-way jumping finite
automata ($\it{GLOWJFA}$), was defined in [15]. These automata work on a
linear tape and can process a subword in a state. In this paper, we introduce
a new model called generalized circular one-way jumping finite automata
$(\it{GCOWJFA})$. This model is also a generalization, in deleting an input,
of the model $\it{OWJFA}$. Unlike $\it{OWJFA}$, it can process a subword,
i.e., $\it{GCOWJFA}$ changes its states by deleting a subword instead of a
symbol. The difference between the model $\it{GLOWJFA}$ and $\it{GCOWJFA}$ is
that $\it{GLOWJFA}$ work on a linear tape whereas $\it{GCOWJFA}$ work on a
circular tape. Because of this difference both the models have distinct
computational power. We show that the generalization $\it{GCOWJFA}$ increases
the power of $\it{OWJFA}.$ Similar to $\it{OWJFA}$, we define two types of
$\it{GCOWJFA}$: generalized right circular one-way jumping finite automata
($\it{GRCOWJFA}$) and generalized left circular one-way jumping finite
automata ($\it{GLCOWJFA}$). The models $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$
delete an input in clockwise and anti-clockwise direction, respectively. Both
the models $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$ can jump over a part of the
input if they cannot delete it.

In this paper, we compare the model $\it{GCOWJFA}$ with the models
$\it{OWJFA}$ and $\it{GLOWJFA}$. We also compare $\it{GRCOWJFA}$ and
$\it{GLCOWJFA}$. The language classes of $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$
are compared with the language classes of Chomsky hierarchy. Closure
properties of the language classes of $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$ are
explored.

The paper is organised as follows: In Section 2, we give some basic notion and
notation. We also recall the definitions of $\it{ROWJFA}$, $\it{LOWJFA}$,
$\it{GRLOWJFA}$, $\it{GLLOWJFA}$ and give examples of these models, in this
section. The models $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$ have been introduced
in Section 3. The models have been illustrated by examples. In Section 4, the
models $\it{GLOWJFA}$ and $\it{GCOWJFA}$ have been compared. We compare the
models $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$ in Section 5. In Section 6, the
language classes of the newly introduced model $\it{GCOWJFA}$ are compared
with the language classes of Chomsky hierarchy. Finally, we discuss closure
properties of the newly introduced models, in Section 7. We end the paper with
few concluding remarks.

##  2 Preliminaries

In this section, we recall some basic notations and definitions. An alphabet
set is a finite non-empty set $\Sigma$. The elements of $\Sigma$ are called
letters or symbols. A word or string $w=a_{1}a_{2}\cdots a_{n}$ is a finite
sequence of symbols, where $a_{i}\in\Sigma$ for $1\leq i\leq n$. The reverse
of $w$ is obtained by writing the symbols of $w$ in reverse order and denoted
by $w^{R}$, hence $w^{R}=a_{n}\cdots a_{2}a_{1}$. By $\Sigma^{*}$, we denote
the set of all words over the alphabet $\Sigma$ and by $\lambda$, the empty
word. A language $L$ is a subset of $\Sigma^{*}$ and
$L^{\mathrm{C}}=\Sigma^{*}\setminus L$ denotes the complement of $L$. The
symbol $\emptyset$ represents the empty language or empty set. For an
arbitrary word $w\in\Sigma^{*}$, we denote its length or the number of letters
in it by $|w|$. For a letter $a\in\Sigma$, $|w|_{a}$ denotes the number of
occurrences of $a$ in $w$. Note that,
$\Sigma^{+}=\Sigma^{*}\setminus\\{\lambda\\}$ and $|\lambda|=0$. For a finite
set $A$, $|A|$ denotes the number of elements in $A$. A word $y\in\Sigma^{*}$
is a subword or substring of a word $w\in\Sigma^{*}$ if there exist words
$x,z\in\Sigma^{*}$ such that $w=xyz$. If $w=uv$, then the words
$u\in\Sigma^{*}$ and $v\in\Sigma^{*}$ are said to be a prefix and a suffix of
$w$, respectively. Two sets $A$ and $B$ are comparable if $A\subseteq B$ or
$B\subseteq A$. For two sets $A$ and $B$, if $A$ is a proper subset of $B$,
then we use the notation $A\subset B$. For definitions of other basic language
operations (like union, intersection etc.), the reader is referred to [12].

We now recall the definitions of right and left one-way jumping finite
automata [5]. A right one-way jumping finite automaton $(\it{ROWJFA})$ is a
quintuple $\mathcal{A}=(\Sigma,Q,q_{0},F,R)$, where $\Sigma$ is an alphabet
set, $Q$ is a finite set of states, $q_{0}$ is the starting state, $F\subseteq
Q$ is a set of final states and $R\subseteq Q\times\Sigma\times Q$ is a set of
rules, where for a state $p\in Q$ and a symbol $a\in\Sigma$, there is at most
one $q\in Q$ such that $(p,a,q)\in R$. By a rule $(p,a,q)\in R$, we mean that
the automaton goes to the state $q$ from the state $p$ after deleting the
symbol ‘$a$’. For $p\in Q$, we set

$\Sigma_{p}=\Sigma_{R,p}=\\{b\in\Sigma:(p,b,q)\in R~{}for~{}some~{}q\in Q\\}.$

A configuration of the right one-way jumping automaton $\mathcal{A}$ is a
string of $Q\Sigma^{*}$. The right one-way jumping relation, denoted as
$\circlearrowright_{\mathcal{A}}$, over $Q\Sigma^{*}$ is defined as follows.
Let $(p,a,q)\in R,x\in(\Sigma\setminus\Sigma_{p})^{*}$ and $y\in\Sigma^{*}$.
Then, the $\it{ROWJFA}$ $\mathcal{A}$ makes a jump from the configuration
$pxay$ to the configuration $qyx$, written as
$pxay\circlearrowright_{\mathcal{A}}qyx$ or just $pxay\circlearrowright qyx$
if it is clear which $\it{ROWJFA}$ is being referred. Let
$\circlearrowright^{+}$ and $\circlearrowright^{*}$ denote the transitive and
reflexive-transitive closure of $\circlearrowright$, respectively. The
language accepted by the automaton $\mathcal{A}$ is

$L_{R}(\mathcal{A})=\\{w\in\Sigma^{*}:q_{0}w\circlearrowright^{*}q_{f}~{}for~{}some~{}q_{f}\in
F\\}.$

A left one-way jumping finite automaton $(\it{LOWJFA})$ is similar to that of
a $\it{ROWJFA}$ except that a configuration of $\it{LOWJFA}$ is a string of
$\Sigma^{*}Q$. By a rule $(q,a,p)\in R$, we mean that the automaton goes to
the state $q$ from the state $p$ after deleting the symbol ‘$a$’. For
$(q,a,p)\in R,x\in(\Sigma\setminus\Sigma_{p})^{*}$ and $y\in\Sigma^{*}$ the
$\it{LOWJFA}$ makes a jump from the configuration $yaxp$ to the configuration
$xyq$, written as $xyq\prescript{}{\mathcal{A}}{\circlearrowleft}$ $yaxp$ or
just $xyq\circlearrowleft yaxp$ if it is clear which $\it{LOWJFA}$ is being
referred. The language accepted by the automaton $\mathcal{A}$ is

$L_{L}(\mathcal{A})=\\{w\in\Sigma^{*}:q_{f}\prescript{*}{}{\circlearrowleft}~{}wq_{0}~{}for~{}some~{}q_{f}\in
F\\}.$

###### Example 1

Consider the $\it{ROWJFA}$

$q_{0}$start$q_{1}$$q_{2}$abc

$\mathcal{A}=(\\{a,b,c\\},\\{q_{0},q_{1},q_{2}\\},q_{0},\\{q_{2}\\},R)$, the
set of rules $R$ is $R=\\{(q_{0},a,q_{1}),$ $(q_{1},b,q_{1}),$
$(q_{1},c,q_{2})\\}$. Here, $\Sigma_{q_{0}}=\\{a\\}$,
$\Sigma_{q_{1}}=\\{b,c\\}$, $\Sigma_{q_{2}}=\emptyset$. Since
$\Sigma_{q_{0}}=\\{a\\}$, the automaton will jump over any word from
$(\Sigma\setminus\Sigma_{q_{0}})^{*}=\\{b,c\\}^{*}$ at $q_{0}$. Also, since
$\Sigma_{q_{1}}=\\{b,c\\}$, the automaton will jump over any word from
$(\Sigma\setminus\Sigma_{q_{1}})^{*}=\\{a\\}^{*}$ at $q_{1}$. It is clear from
the rules that if a word is in the language, then it will have exactly one
$`a$’ and one $`c$’. Moreover, the automaton has a loop labeled $`b$’ at
$q_{1}$. Therefore, the language will have the words of the form
$b^{l}ab^{m}cb^{n}$ or $b^{l}cb^{m}ab^{n}$. We can divide these words in 8
groups $\\{l=m=n=0\\}$, $\\{l=0,m=0,n\geq 1\\}$, $\\{l=0,m\geq 1,n=0\\}$,
$\\{l=0,m\geq 1,n\geq 1\\}$, $\\{l\geq 1,m=n=0\\}$, $\\{l\geq 1,m=0,n\geq
1\\}$, $\\{l\geq 1,m\geq 1,n=0\\}$, $\\{l\geq 1,m\geq 1,n\geq 1\\}$. Using
case-by-case analysis, we conclude that the words $ab^{m}c$, where $m\geq 0$
and $b^{l}cab^{n}$, where $l,n\geq 0$ are in the language. For example,
consider a string $b^{l}cab^{n}$, where $l,n\geq 0$. The sequence of
transitions is

$q_{0}b^{l}cab^{n}\circlearrowright
q_{1}b^{n}b^{l}c\circlearrowright^{*}q_{1}c\circlearrowright q_{2}.$

Hence, the language accepted by the automaton is

$L_{R}(\mathcal{A})=\\{ab^{m}c~{}:~{}m\geq
0\\}\cup\\{b^{l}cab^{n}~{}:~{}l,n\geq 0\\}.$

###### Note 1

The language of the automaton, when it is considered as jumping finite
automaton ([14]) is $\\{b^{l}ab^{m}cb^{n}~{}:~{}l,m,n\geq 0\\}$ $\cup$
$\\{b^{l}cb^{m}ab^{n}~{}:~{}l,m,n\geq 0\\}$.

A right one-way jumping finite automaton [5] can be interpreted in two ways:
one in which we think it working on linear tape and the other in which we
think it working on a tape in a circular manner. When it is thought working on
linear tape, in that case, the read head moves in one direction only and
starts from the leftmost symbol of an input word. It moves from left to right
(and possibly jumps over parts of the input) and upon reaching the end of the
input word the automaton jumps to the leftmost symbol of the remaining
concatenated word and starts deleting the word freshly from the last visited
state. If a transition is defined for the current state and the next letter to
be read, then the automaton deletes the letter. If not, but in the remaining
input there are letters for which a transition is defined from the current
state, the read head jumps to the nearest such letter to the right for its
reading. The computation continues until all the letters are deleted or the
automaton is stuck in a state in which it cannot delete any letter of the
remaining word.

In the light of this interpretation, an extension of $\it{ROWJFA}$ was given
based on reading length of a word and generalized right linear one-way jumping
finite automaton was defined in [15]. A generalized right linear one-way
jumping finite automaton($\it{GRLOWJFA}$) works on a linear tape and deletes
an input word from left to right. The automaton starts deleting the input word
with the reading head at the leftmost position of the input word. The
automaton can jump over a part of the input word which it cannot process in
its current state. It reads the nearest available subword of the word present
on the input tape. If there is no transition available for current state, the
automaton returns(head of the automaton returns) to the leftmost position of
the current input and continues its computation. The computation continues
until all the letters are deleted or the automaton is stuck in a state in
which it cannot delete any subword of the remaining word. The generalized left
linear one-way jumping finite automaton($\it{GLLOWJFA}$) work similar to
$\it{GRLOWJFA}$. The read head of a $\it{GLLOWJFA}$ moves from right to left.
We recall the formal definitions of generalized right linear one-way jumping
finite automaton and generalized left linear one-way jumping finite automaton
from [15], given below.

###### Definition 1

A generalized right linear one-way jumping finite automaton ($\it{GRLOWJFA}$)
is a tuple $\mathcal{A}=(\Sigma,Q,q_{0},F,R)$, where $\Sigma,Q,q_{0},F$ are
same as $\it{ROWJFA}$ and $R\subset Q\times\Sigma^{+}\times Q$ is a finite set
of rules, where for a state $p\in Q$ and a word $w\in\Sigma^{+}$, there is at
most one $q\in Q$ such that $(p,w,q)\in R$. By a rule $(p,w,q)\in R$, we mean
that the automaton goes to the state $q$ from the state $p$ after deleting the
word ‘$w$’. The automaton is deterministic in the sense that for a state $p$
and for a word $w\in\Sigma^{+}$ we have at most one $q\in Q$ such that
$(p,w,q)\in R$. A configuration of the automaton $\mathcal{A}$ is a string of
$\Sigma^{*}Q\Sigma^{*}$. The generalized right linear one-way jumping
relation, denoted as $\curvearrowright_{\mathcal{A}}$, or just
$\curvearrowright$ if it is clear which $\it{GRLOWJFA}$ is being referred,
over $\Sigma^{*}Q\Sigma^{*}$ is defined as follows: For a state $p\in Q$, set
$\Sigma_{p}=\Sigma_{R,p}=\\{w\in\Sigma^{+}:(p,w,q)\in R$ for some $q\in Q\\}$.

  * 1.

Let $t,u,v\in\Sigma^{*}$ and $(p,x,q)\in R$. Then the $\it{GRLOWJFA}$
$\mathcal{A}$ makes a jump from the configuration $tpuxv$ to the configuration
$tuqv$, written as

$tpuxv\curvearrowright tuqv$

if $u$ does not contain any word from $\Sigma_{p}$ as a subword, i.e., $u\neq
u^{\prime}wu^{\prime\prime}$, where
$u^{\prime},u^{\prime\prime}\in\Sigma^{*},~{}w\in\Sigma_{p}$ and
$u_{2}x_{1}\neq x$, where $u_{2},x_{1}\in\Sigma^{+}$ and
$u=u_{1}u_{2},~{}x=x_{1}x_{2}$ for some $u_{1},x_{2}\in\Sigma^{*}$. This is
what we mean by nearest available subword.

  * 2.

Let $x\in\Sigma^{+},y\in\Sigma^{*}$ and $y$ does not contain any word from
$\Sigma_{p}$ as a subword, i.e., $y\neq y_{1}wy_{2}$, where
$y_{1},y_{2}\in\Sigma^{*}$ and $w\in\Sigma_{p}$, then the $\it{GRLOWJFA}$
$\mathcal{A}$ makes a jump from the configuration $xpy$ to the configuration
$pxy$, written as

$xpy\curvearrowright pxy.$

The language accepted by the $\it{GRLOWJFA}$ $\mathcal{A}$ is

$L_{GRL}(\mathcal{A})=\\{w\in\Sigma^{*}:q_{0}w\curvearrowright^{*}q_{f}~{}for~{}some~{}q_{f}\in
F\\}.$

Similar to that of $\it{GRLOWJFA}$, the generalized left linear one-way
jumping finite automaton was defined.

###### Definition 2

A generalized left linear one-way jumping finite automaton denoted by
$\it{GLLOWJFA}$ is a tuple $\mathcal{A}=(\Sigma,Q,q_{0},F,R)$, where
$\Sigma,Q,q_{0},F$ are same as $\it{ROWJFA}$ and $R\subset
Q\times\Sigma^{+}\times Q$ is a finite set of rules, where for a state $p\in
Q$ and a word $w\in\Sigma^{+}$, there is at most one $q\in Q$ such that
$(q,w,p)\in R$. By a rule $(q,w,p)\in R$, we mean that the automaton goes to
the state $q$ from the state $p$ after deleting the word ‘$w$’. The automaton
is deterministic in the sense that for a state $p$ and for a word
$w\in\Sigma^{+}$ we have at most one $q\in Q$ such that $(q,w,p)\in R$. A
configuration of the automaton $\mathcal{A}$ is a string of
$\Sigma^{*}Q\Sigma^{*}$. The generalized left linear one-way jumping relation,
denoted as $\prescript{}{{\mathcal{A}}}{\curvearrowleft}$, or just
$\curvearrowleft$ if it is clear which $\it{GLLOWJFA}$ is being referred, over
$\Sigma^{*}Q\Sigma^{*}$ is defined as follows: For a state $p\in Q$, set
$\Sigma_{p}=\Sigma_{R,p}=\\{w\in\Sigma^{+}:(q,w,p)\in R$ for some $q\in Q\\}$.

  * 1.

Let $t,u,v\in\Sigma^{*}$ and $(q,x,p)\in R$. Then, the $\it{GLLOWJFA}$
$\mathcal{A}$ makes a jump from the configuration $vxupt$ to the configuration
$vqut$, written as

$vqut\curvearrowleft vxupt$

if $u$ does not contain any word from $\Sigma_{p}$ as a subword, i.e., $u\neq
u^{\prime}wu^{\prime\prime}$, where
$u^{\prime},u^{\prime\prime}\in\Sigma^{*},~{}w\in\Sigma_{p}$ and
$x_{2}u_{1}\neq x$, where $u_{1},x_{2}\in\Sigma^{+}$ and
$u=u_{1}u_{2},~{}x=x_{1}x_{2}$ for some $u_{2},x_{1}\in\Sigma^{*}$.

  * 2.

Let $x\in\Sigma^{+},y\in\Sigma^{*}$ and $y$ does not contain any word from
$\Sigma_{p}$ as a subword, i.e., $y\neq y_{1}wy_{2}$, where
$y_{1},y_{2}\in\Sigma^{*}$ and $w\in\Sigma_{p}$, then the $\it{GLLOWJFA}$
$\mathcal{A}$ makes a jump from the configuration $ypx$ to the configuration
$yxp$, written as

$yxp\curvearrowleft ypx.$

The language accepted by the $\it{GLLOWJFA}$ $\mathcal{A}$ is

$L_{GLL}(\mathcal{A})=\\{w\in\Sigma^{*}:q_{f}~{}\prescript{*}{}{\curvearrowleft}~{}wq_{0}~{}for~{}some~{}q_{f}\in
F\\}.$

We illustrate Definitions 1 and 2 with the following example.

###### Example 2

Consider the automaton
$\mathcal{A}=(\\{a,b,c\\},\\{q_{0},q_{1}\\},q_{0},\\{q_{1}\\},R)$, where $R$
is depicted in the figure below.

$q_{0}$start$q_{1}$cab

We first consider the automaton as a $\it{GRLOWJFA}$. Then, the set of rules
is $R=\\{(q_{0},c,q_{0}),(q_{0},ab,q_{1})\\}$. Hence,
$\Sigma_{q_{0}}=\\{c,ab\\}$ and $\Sigma_{q_{1}}=\emptyset$. Since
$\Sigma_{q_{0}}=\\{c,ab\\}$, the automaton at $q_{0}$ can neither jump over a
‘$c$’ nor over ‘$ab$’. The automaton can delete arbitrary number of $c$’s at
state $q_{0}$ and can jump $`a$’ or $`b$’ at $q_{0}$. Consider a word
$c^{l}ac^{m}bc^{n}$, where $l,n\geq 0,m\geq 1$. Then,
$q_{0}c^{l}ac^{m}bc^{n}\curvearrowright^{*}q_{0}ac^{m}bc^{n}\curvearrowright
aq_{0}c^{m-1}bc^{n}\curvearrowright^{*}aq_{0}bc^{n}\curvearrowright
abq_{0}c^{n-1}\curvearrowright^{*}abq_{0}\curvearrowright
q_{0}ab\curvearrowright q_{1}$ and hence,

$L_{GRL}(\mathcal{A})=\\{c^{l}ab~{}|~{}n\geq
0\\}\cup\\{c^{l}ac^{m}bc^{n}~{}|~{}l,n\geq 0,m\geq 1\\}.$

Now, consider the automaton as $\it{GLLOWJA}$. In this case, the set of rules
is $R=\\{(q_{0},c,q_{0}),(q_{1},ab,q_{0})\\}$. It can be shown, as explained
above, the language accepted by the automaton $\it{GLLOWJFA}$ is

$L_{GLL}(\mathcal{A})=\\{abc^{n}~{}|~{}n\geq
0\\}\cup\\{c^{l}ac^{m}bc^{n}~{}|~{}l,n\geq 0,m\geq 1\\}.$

##  3 Generalized Circular One-Way Jumping Finite Automata

The right one-way jumping automata [5] can also be thought/interpreted as
working on a tape in a circular manner. In this case, a right one-way jumping
finite automaton works on a circular tape and the read head moves in the
clockwise direction. The read head starts from the first symbol of an input,
i.e., read head is at $w_{1}$ of the input $w=w_{1}w_{2}\cdots w_{n}$. The
automaton can jump over parts of the input. If a transition is defined for a
current state and the next letter to be read, then the automaton deletes the
symbol. If not and in the remaining input there are letters for which a
transition is defined from the current state, the read head jumps to the
nearest such letter to delete it. The computation continues until all the
letters are deleted or the automaton is stuck in a state in which it cannot
delete any letter of the remaining word.

Keeping this interpretation in mind, we extend the definition of $\it{ROWJFA}$
based on reading length of a word and define generalized right circular one-
way jumping finite automata. A generalized right circular one-way jumping
finite automaton works on a circular tape and deletes an input word in the
clockwise direction. The automaton starts deleting the input word with the
reading head at the first symbol, the symbol at which reading head is present,
of the input, ie., $w_{1}$ of $w=w_{1}w_{2}\cdots w_{n}$. The automaton can
jump over a part of the input word that it cannot delete. After deleting a
subword of the word present on the input tape, the word is circularly permuted
and the reading head goes to the first symbol just after the deleted subword.
Suppose $uxv$ is present on the tape and the automaton deletes $x$, then the
word is circularly permuted to get $vu$ and the reading head goes to the first
symbol of $vu$. The computation continues until all the letters are deleted or
the automaton is stuck in a state in which it cannot delete any subword of the
remaining word present on the tape. The $\it{GLCOWJFA}$ works similar to that
of $\it{GRCOWJFA}$. The tape head of a $\it{GLCOWJFA}$ moves in the anti-
clockwise direction. The formal definitions of generalized right circular one-
way jumping finite automaton and generalized left circular one-way jumping
finite automaton are given below.

###### Definition 3

A generalized right circular one-way jumping finite automaton
($\it{GRCOWJFA}$) is a tuple $\mathcal{A}=(\Sigma,Q,q_{0},F,R)$, where
$\Sigma,Q,q_{0},F$ are same as $\it{ROWJFA}$ and $R\subset
Q\times\Sigma^{+}\times Q$ is a finite set of rules, where for a state $p\in
Q$ and a word $w\in\Sigma^{+}$, there is at most one $q\in Q$ such that
$(p,w,q)\in R$. By a rule $(p,w,q)\in R$, we mean that the automaton goes to
the state $q$ from the state $p$ after deleting the word ‘$w$’. The automaton
is deterministic in the sense that for a state $p$ and for a word
$w\in\Sigma^{+}$ we have at most one $q\in Q$ such that $(p,w,q)\in R$. A
configuration of the automaton $\mathcal{A}$ is a string of $Q\Sigma^{*}$. The
generalized right circular one-way jumping relation, denoted as
$\circlearrowright_{\mathcal{A}}$, or just $\circlearrowright$ if it is clear
which $\it{GRCOWJFA}$ is being referred, over $Q\Sigma^{*}$ is defined as
follows: For a state $p\in Q$, set
$\Sigma_{p}=\Sigma_{R,p}=\\{w\in\Sigma^{+}:(p,w,q)\in R$ for some $q\in Q\\}$.
Let $u,v\in\Sigma^{*}$ and $(p,x,q)\in R$. Then, the $\it{GRCOWJFA}$
$\mathcal{A}$ makes a jump from the configuration $puxv$ to the configuration
$qvu$, written as

$puxv\circlearrowright qvu$

if $u$ does not contain any word from $\Sigma_{p}$ as a subword, i.e., $u\neq
u^{\prime}wu^{\prime\prime}$, where
$u^{\prime},u^{\prime\prime}\in\Sigma^{*},~{}w\in\Sigma_{p}$ and
$u_{2}x_{1}\neq x$, where $u_{2},x_{1}\in\Sigma^{+}$ and
$u=u_{1}u_{2},~{}x=x_{1}x_{2}$ for some $u_{1},x_{2}\in\Sigma^{*}$. The
language accepted by the $\it{GRCOWJFA}$ $\mathcal{A}$ is

$L_{GRC}(\mathcal{A})=\\{w\in\Sigma^{*}:q_{0}w\circlearrowright^{*}q_{f}~{}for~{}some~{}q_{f}\in
F\\}.$

Similar to that of $\it{GRCOWJFA}$, we define the notion of a generalized left
circular one-way jumping finite automaton as below.

###### Definition 4

A generalized left circular one-way jumping finite automaton denoted by
$\it{GLCOWJFA}$ is a tuple $\mathcal{A}=(\Sigma,Q,q_{0},F,R)$, where
$\Sigma,Q,q_{0},F$ are same as $\it{ROWJFA}$ and $R\subset
Q\times\Sigma^{+}\times Q$ is a finite set of rules, where for a state $p\in
Q$ and a word $w\in\Sigma^{+}$, there is at most one $q\in Q$ such that
$(q,w,p)\in R$. By a rule $(q,w,p)\in R$, we mean that the automaton goes to
the state $q$ from the state $p$ after deleting the word ‘$w$’. The automaton
is deterministic in the sense that for a state $p$ and for a word
$w\in\Sigma^{+}$ we have at most one $q\in Q$ such that $(q,w,p)\in R$. A
configuration of the automaton $\mathcal{A}$ is a string of $\Sigma^{*}Q$. The
generalized left circular one-way jumping relation, denoted as
$\prescript{}{{\mathcal{A}}}{\circlearrowleft}$, or just $\circlearrowleft$ if
it is clear which $\it{GLCOWJFA}$ is being referred, over $\Sigma^{*}Q$ is
defined as follows: For a state $p\in Q$, set
$\Sigma_{p}=\Sigma_{R,p}=\\{w\in\Sigma^{+}:(q,w,p)\in R$ for some $q\in Q\\}$.
Let $u,v\in\Sigma^{*}$ and $(q,x,p)\in R$. Then, the $\it{GLCOWJFA}$
$\mathcal{A}$ makes a jump from the configuration $vxup$ to the configuration
$uvq$, written as

$uvq\circlearrowleft vxup$

if $u$ does not contain any word from $\Sigma_{p}$ as a subword, i.e., $u\neq
u^{\prime}wu^{\prime\prime}$, where
$u^{\prime},u^{\prime\prime}\in\Sigma^{*},~{}w\in\Sigma_{p}$ and
$x_{2}u_{1}\neq x$, where $u_{1},x_{2}\in\Sigma^{+}$ and
$u=u_{1}u_{2},~{}x=x_{1}x_{2}$ for some $u_{2},x_{1}\in\Sigma^{*}$. The
language accepted by the $\it{GLCOWJFA}$ $\mathcal{A}$ is

$L_{GLC}(\mathcal{A})=\\{w\in\Sigma^{*}:q_{f}~{}\prescript{*}{}{\circlearrowleft}~{}wq_{0}~{}for~{}some~{}q_{f}\in
F\\}.$

We give examples illustrating Definitions 3 and 4.

###### Example 3

Consider the automaton from Example 2.

$q_{0}$start$q_{1}$cab

We first consider the automaton as a $\it{GRCOWJFA}$. Then, the set of rules
is $R=\\{(q_{0},c,q_{0}),(q_{0},ab,q_{1})\\}.$ Hence,
$\Sigma_{q_{0}}=\\{c,ab\\}$ and $\Sigma_{q_{1}}=\emptyset$. Since
$\Sigma_{q_{0}}=\\{c,ab\\}$, the automaton at $q_{0}$ can neither jump over a
‘$c$’ nor over ‘$ab$’. The automaton can delete arbitrary number of $c$’s at
state $q_{0}$ and can jump over $`a$’ or $`b$’ at $q_{0}$. So any word in the
language will be of the form $c^{l}ac^{m}bc^{n}$ or $c^{l}bc^{m}ac^{n}$. We
can divide these words in 8 groups $\\{l=m=n=0\\}$, $\\{l=0,m=0,n\geq 1\\}$,
$\\{l=0,m\geq 1,n=0\\}$, $\\{l=0,m\geq 1,n\geq 1\\}$, $\\{l\geq 1,m=n=0\\}$,
$\\{l\geq 1,m=0,n\geq 1\\}$, $\\{l\geq 1,m\geq 1,n=0\\}$, $\\{l\geq 1,m\geq
1,n\geq 1\\}$. And using case-by-case analysis, we conclude that the language
accepted by the automaton is

$L_{GRC}(\mathcal{A})=\\{c^{l}ab~{}|~{}l\geq
0\\}\cup\\{c^{l}ac^{m}bc^{n}~{}|~{}l\geq 0,m,n\geq
1\\}\cup\\{c^{l}bc^{m}a~{}|~{}l\geq 0,m\geq 1\\}.$

Now, consider the automaton as $\it{GLCOWJA}$. In this case, the set of rules
is $R=\\{(q_{0},c,q_{0}),(q_{1},ab,q_{0})\\}$. It can be shown, using the
above technique, the language accepted by the automaton $\it{GLCOWJFA}$ is

$L_{GLC}(\mathcal{A})=\\{abc^{n}~{}|~{}n\geq
0\\}\cup\\{c^{l}ac^{m}bc^{n}~{}|~{}l,m\geq 1,n\geq
0\\}\cup\\{bc^{m}ac^{n}~{}|~{}m\geq 1,n\geq 0\\}.$

###### Note 2

Note that the language accepted by the automaton of Example 2, when it is
considered as $\it{GJFA}$ ([14]), is $L=\\{c^{l}ac^{m}bc^{n}~{}:~{}l,m,n\geq
0\\}$. The language accepted differs in $\it{GJFA}$, $\it{GRLOWJFA}$,
$\it{GRCOWJFA}$, $\it{GLLOWJFA}$, $\it{GLCOWJFA}$ because of different ways of
processing the same input.

Now, we give and example that shows that the language classes $\bf{GRCOWJ}$
and $\bf{GLCOWJ}$ are not disjoint, where $\bf{GRCOWJ}$ and $\bf{GLCOWJ}$ are
the language classes accepted by $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$
respectively.

###### Example 4

Consider the automaton

$q_{0}$start$q_{1}$abc

The automaton cannot make any move without deleting $ab$ and at the state
$q_{1}$ it can delete any number of $c$’s. Hence, the language accepted by the
automaton is

$L_{GRC}(\mathcal{A})=L_{GLC}(\mathcal{A})=L_{GRL}(\mathcal{A})=L_{GLL}(\mathcal{A})=c^{*}abc^{*}.$

Hence, we conclude the following.

###### Note 3

$\bf{GRCOWJ}\cap\bf{GLCOWJ}\cap\bf{GRLOWJ}\cap\bf{GLLOWJ}\neq\emptyset$.

From the Definition 3 of $\it{GRCOWJFA}$, we observe the following:

###### Lemma 1

Let $\mathcal{A}=(\Sigma,Q,q_{0},F,R)$ be a $\it{GRCOWJFA}$. Let
$w_{1},w_{2}\in\Sigma^{*}$ and $(p,x,q)\in R$. If the automaton goes from a
configuration $pw_{1}xw_{2}$ to a configuration $qw_{2}w_{1}$, then the
automaton also goes to the configuration $qw_{2}w_{1}$ from the configuration
$pxw_{2}w_{1}$, i.e., if $pw_{1}xw_{2}$ $\circlearrowright$ $qw_{2}w_{1}$,
then $pxw_{2}w_{1}$ $\circlearrowright$ $qw_{2}w_{1}$.

A similar observation can also be made for the model $\it{GLCOWJFA}$.

##  4 GCOWJFA and GLOWJFA

In this section, we compare the language class $\bf{GRCOWJ}$ with the language
classes $\bf{ROWJ}$ and $\bf{GRLOWJ}$, where $\bf{ROWJ}$ and $\bf{GRLOWJ}$ are
the language classes accepted by $\it{ROWJFA}$ and $\it{GRLOWJFA}$
respectively. The comparison between language classes $\bf{ROWJ}$ and
$\bf{GRLOWJ}$ was done in [15] and it was proved that $\bf{ROWJ\subset
GRLOWJ}$ [15]. Here, we show that the language class $\bf{ROWJ}$ is properly
contained in the language class $\bf{GRCOWJ}$. Similarly, it can be shown that
$\bf{LOWJ}\subset$ $\bf{GLCOWJ}$. We also show that $\bf{GRLOWJ}$ is not a
part of $\bf{GRCOWJ}$.

It is clear from the definitions of $\it{ROWJFA}$ and
$\it{GRCOWJFA}$/$\it{GRLOWJFA}$ that when the rules of a
$\it{GRCOWJFA}$/$\it{GRLOWJFA}$ satisfies the condition: if $(p,w,q)\in R$,
then $|w|=1$. Then, the $\it{GRCOWJFA}$/$\it{GRLOWJFA}$ is nothing but
$\it{ROWJFA}$. Hence, $\bf{ROWJ}$ $\subseteq$ $\bf{GRCOWJ}\cap\bf{GRLOWJ}$.
Similarly, $\bf{LOWJ}$ $\subseteq$ $\bf{GLCOWJ}$ $\cap$ $\bf{GLLOWJ}$. Now, we
give a language that is in the class $\bf{GRCOWJ}$ but not in the class
$\bf{ROWJ}$.

###### Example 5

([15]) Consider the $\it{GRCOWJFA}$
$\mathcal{A}=(\\{a,b\\},\\{q_{0},q_{1},q_{2},q_{3},q_{4}\\},q_{0},$
$\\{q_{0},q_{1},$ $q_{2},q_{4}\\},$ $R)$, where the set of rules is
$R=\\{(q_{0},a,q_{1}),(q_{1},b,q_{2}),(q_{2},a,q_{3}),$ $(q_{3},b,q_{2}),$
$(q_{0},aa,q_{4}),$ $(q_{4},a,q_{4})\\}$. The language accepted by the
automaton is

$L_{GRC}(\mathcal{A})=\\{w\in\\{a,b\\}^{*}~{}|~{}|w|_{a}=|w|_{b}$ or
$|w|_{b}=0\\}$.

It was proved in [3] that the language of Example 5 cannot be accepted by any
$\it{ROWJFA}$. It was shown in [15] that the language is in the class
$\bf{GRLOWJ}$. Hence, by Example 5 and definitions of $\it{GRCOWJFA}$ and
$\it{GRLOWJFA}$, we have the following result.

###### Note 4

$\bf{ROWJ}\subset\bf{GRCOWJ}\cap\bf{GRLOWJ}$.

Similarly, it can be shown that $\bf{LOWJ}\subset\bf{GLCOWJ}\cap\bf{GLLOWJ}$.

Now, we give a language that is in the language class $\bf{GRLOWJ}$ but not in
the class $\bf{GRCOWJ}$.

###### Example 6

([15]) Consider the $\it{GRLOWJFA}$ automaton
$\mathcal{A}=(\\{a,b\\},\\{q_{0}\\},q_{0},$ $\\{q_{0}\\},$
$\\{(q_{0},ab,q_{0})\\})$. The language accepted by the automaton is the Dyck
language, $D$. Hence, $D\in$ $\bf{GRLOWJ}$.

Now, we prove that the Dyck language cannot be accepted by any
$\it{GRCOWJFA}$.

###### Lemma 2

There does not exist any $\it{GRCOWJFA}$ that accepts the Dyck language, i.e.,
$D\notin\bf{GRCOWJ}.$

###### Proof

If $D\in\bf{GRCOWJ}$, then there exists a $\it{GRCOWJFA}$
$\mathcal{A}=(\Sigma,Q,$ $q_{0},$ $F,$ $R)$ such that $L(\mathcal{A})=D$. Let
$l=|Q|$ and $m=max\\{|w|~{}:~{}(p,w,q)\in R\\}$. Choose $n>lm$. We know
$a^{n}b^{n}\in D=L(\mathcal{A})$. Then, there exists a sequence of transitions
such that $q_{0}a^{n}b^{n}\circlearrowright^{*}q_{f}$, where $q_{f}\in F$. In
order to reach the final configuration $q_{f}$ from the initial configuration
$q_{0}a^{n}b^{n}$, there will be intermediate configurations of the form
$q^{\prime}w_{1}a$ or $q^{\prime\prime}w_{2}b$ or both, where
$q^{\prime},q^{\prime\prime}\in Q,w_{1},w_{2}\in\Sigma^{*}$.

  * Case 1.

If there is an intermediate configuration of the form $q^{\prime}w_{1}a$.
Then, the automaton will make the following sequence of transitions
$q_{0}a^{n}b^{n}\circlearrowright^{*}q^{\prime}w_{1}a\circlearrowright^{*}q_{f}$.
Then, by repeated application of Lemma 1, we have a word $w\in\Sigma^{*}$ such
that
$q_{0}ww_{1}a\circlearrowright^{*}q^{\prime}w_{1}a\circlearrowright^{*}q_{f}$.
Hence, $ww_{1}a\in L(\mathcal{A})$ but $ww_{1}a\not\in D$ because no word of
$D$ ends with ‘$a$’. Hence, there cannot be any intermediate configuration of
the form $q^{\prime}w_{1}a$.

  * Case 2.

Since there cannot be any intermediate configuration of the form
$q^{\prime}w_{1}a$, all intermediate configurations have the form
$q^{\prime\prime}w_{2}b$. In this case, the automaton will delete all $a$’s
first and then $b$’s, starting from the initial configuration
$q_{0}a^{n}b^{n}$, otherwise the automaton will go to a configuration of the
form $q^{\prime}w_{1}a$ because of Lemma 1. Because of the choice of $n$,
there will be a loop consisting of only $a$’s to delete all $a$’s without
deleting $b$’s, starting from the initial configuration. The same loop can be
used multiple times to create a mismatch in the indices of $`a$’ and $`b$’.
Hence, there will be a word of the form $a^{n_{1}}b^{n}$, $n_{1}\neq n$, in
$L(\mathcal{A})$ but $a^{n_{1}}b^{n}\not\in D$ for $n_{1}\neq n$.

From the above discussed cases, we conclude that $D\not\in\bf{GRCOWJ}$.

We conclude the following from Example 6 and Lemma 2.

###### Proposition 1

The language class $\bf{GRLOWJ}$ is not contained in the language class
$\bf{GRCOWJ}$, i.e., $\bf{GRLOWJ}$ $\not\subseteq$ $\bf{GRCOWJ}$. Similarly,
it can be proved that $\bf{GLLOWJ}$ $\not\subseteq$ $\bf{GLCOWJ}$.

##  5 GRCOWJFA and GLCOWJFA

In this section, the comparison between the language classes $\bf{GRCOWJ}$ and
$\bf{GLCOWJ}$ has been done. We begin the section with a relationship that
connects the languages of the class $\bf{GRCOWJ}$ and the languages of the
class $\bf{GLCOWJ}$.

First we recall a similar result from [15].

###### Lemma 3

For a language $L_{1}\in\bf{GRLOWJ}$, there exists a language
$L_{2}\in\bf{GLLOWJ}$ such that $L_{1}^{R}=L_{2}$ and vice versa.

Now, we show that for every language $L_{1}\in\bf{GRCOWJ}$ $(\bf{GLCOWJ})$,
there exists a language $L_{2}\in\bf{GLCOWJ}$ $(\bf{GRCOWJ}$ resp) such that
$L_{1}^{R}=L_{2}$.

###### Proposition 2

For a language $L_{1}\in\bf{GRCOWJ}$, there exists a language
$L_{2}\in\bf{GLCOWJ}$ such that $L_{1}^{R}=L_{2}$ and vice versa.

###### Proof

Let $L_{1}\in\bf{GRCOWJ}$. Then, there exists a $\it{GRCOWJFA}$, say
$\mathcal{A}_{1}=(\Sigma,Q,q_{0},F,R)$, such that $L_{1}=L(\mathcal{A}_{1})$.
We construct a $\it{GLCOWJFA}$, say $\mathcal{A}_{2}$, as:
$\mathcal{A}_{2}=(\Sigma,Q,q_{0},F,R^{\prime})$, where
$R^{\prime}=\\{(q,w^{R},p)~{}|~{}(p,w,q)\in R\\}$. Let
$L(\mathcal{A}_{2})=L_{2}$. Claim, $L_{1}^{R}=L_{2}$. We have the following
lemma:

###### Lemma 4

If $x,y\in\Sigma^{*}$, $u\in\Sigma^{+}$ and $p,q\in Q$, then
$pxuy\circlearrowright_{\mathcal{A}_{1}}qyx$ if and only if $x^{R}y^{R}q$
$\prescript{}{{\mathcal{A}_{2}}}{\circlearrowleft}$ $y^{R}u^{R}x^{R}p$.

###### Proof

Let $x,y\in\Sigma^{*}$, $u\in\Sigma^{+}$ and $p,q\in Q$. Now,
$pxuy\circlearrowright_{\mathcal{A}_{1}}qyx$ if and only if $(p,u,q)\in R$,
$x$ does not contain any word from $\Sigma_{R,p}$ as a subword and
$x^{\prime\prime}u^{\prime}\neq u$, where $x^{\prime\prime}$ is a nonempty
suffix of $x$ and $u^{\prime}$ is a nonempty prefix of $u$ if and only if
$(q,u^{R},p)\in R^{\prime}$, $x^{R}$ does not contain any word from
$\Sigma_{R^{\prime},p}$ as a subword and $u^{(2)}x^{(1)}\neq u^{R}$, where
$x^{(1)}$ is a nonempty prefix of $x^{R}$ and $u^{(2)}$ is a nonempty suffix
of $u^{R}$ if and only if $x^{R}y^{R}q$
$\prescript{}{{\mathcal{A}_{2}}}{\circlearrowleft}$ $y^{R}u^{R}x^{R}p$. Hence,
for $x,y\in\Sigma^{*}$, $u\in\Sigma^{+}$ and $p,q\in Q$,
$pxuy\circlearrowright_{\mathcal{A}_{1}}qyx$ if and only if $x^{R}y^{R}q$
$\prescript{}{{\mathcal{A}_{2}}}{\circlearrowleft}$ $y^{R}u^{R}x^{R}p$.

Now, from Lemma 4, $w\in L_{1}^{R}$ if and only if
$q_{0}w^{R}\circlearrowright_{\mathcal{A}_{1}}^{*}q_{f}$, where $q_{f}\in F$,
if and only if $q_{f}$ $\prescript{*}{{\mathcal{A}_{2}}}{\circlearrowleft}$
$wq_{0}$ if and only if $w\in L_{2}$. Hence, $L_{1}^{R}=L_{2}$.

###### Corollary 1

If a language $L\in\bf{GRCOWJ\cap GLCOWJ}$, then the reversal of the language
$L^{R}$ $\in$ $\bf{GRCOWJ\cap GLCOWJ}$.

Now, we compare the language class $\bf{GRCOWJ}$ with the language class
$\bf{GLCOWJ}$. We give a language that is in the language class $\bf{GLCOWJ}$.
We show that the language is not in the class $\bf{GRCOWJ}$. Hence, we
conclude $\bf{GLCOWJ}$ is not contained in $\bf{GRCOWJ}$. Similarly, it can be
shown that $\bf{GRCOWJ}$ is not contained in $\bf{GLCOWJ}$.

###### Example 7

Consider the $\it{GLCOWJFA}$
$\mathcal{A}=(\\{a,b,c\\},\\{q_{0},q_{1},q_{2}\\},q_{0},$ $\\{q_{1}\\},$ $R)$,
where
$R=\\{(q_{2},a,q_{0}),(q_{2},b,q_{0}),(q_{1},c,q_{0}),(q_{1},ba,q_{1})\\}$.
Here, $\Sigma_{q_{0}}=\\{a,b,c\\}$,
$\Sigma_{q_{1}}=\\{ba\\}$,$\Sigma_{q_{2}}=\emptyset$. We have the following
observations regarding the language $L(\mathcal{A})$ of the automaton. Let
$L(\mathcal{A})=L_{c}$.

  * $\bullet$

Note that all words of $L(\mathcal{A})$ will end with $c$. Suppose there is a
word $w\in\Sigma^{*}$ that ends with $a$. Then, $w=w_{1}a$, where
$w_{1}\in\Sigma^{*}$. Since $a\in\Sigma_{q_{0}}$, the automaton cannot jump
over ‘$a$’ at $q_{0}$ and hence, after deleting ‘$a$’ the automaton will go to
the state $q_{2}$, i.e., $w_{1}q_{2}$ $\circlearrowleft$ $w_{1}aq_{0}$. Hence,
$w=w_{1}a\not\in L(\mathcal{A})$. Same argument holds true for words ending
with $`b$’.

  * $\bullet$

Note that, $a^{n}b^{n}a^{n}b^{n}c\in L(\mathcal{A})$ for $n\geq 0$ since,
$q_{1}$ $\circlearrowleft$ $\cdots$ $\circlearrowleft$
$a^{n-1}b^{n-1}a^{n-1}b^{n-1}q_{1}$ $\circlearrowleft$
$a^{n-1}b^{n}a^{n}b^{n-1}q_{1}$ $\circlearrowleft$ $a^{n}b^{n}a^{n}b^{n}q_{1}$
$\circlearrowleft$ $a^{n}b^{n}a^{n}b^{n}cq_{0}$.

  * $\bullet$

If $w\in L(\mathcal{A})$, then $|w|_{a}=|w|_{b}$. This is because the deletion
of $a$ or $b$ will happen using the rule $(q_{1},ba,q_{1})$ only.

Now, we prove that the language $L_{c}$ is not in the language class
$\bf{GRCOWJ}$.

###### Lemma 5

The language $~{}L_{c}~{}$ of Example 7 cannot be accepted by any
$\it{GRCOWJFA}$.

###### Proof

Let $L_{c}$ be accepted by a $\it{GRCOWJFA}$
$\mathcal{A}=(\Sigma,Q,q_{0},F,R)$, then $L(\mathcal{A})=L_{c}$ and let
$l=|Q|$, $m=\\{|w|~{}:~{}(p,w,q)\in R\\}$ and $n>lm$. From Example 7, we have
$a^{n}b^{n}a^{n}b^{n}c\in L_{c}=L(\mathcal{A})$. Then, there would be a
sequence of transitions such that
$q_{0}a^{n}b^{n}a^{n}b^{n}c\circlearrowright^{*}q_{f}$, where $q_{f}\in F$.
The automaton can delete $a^{i}$, $a^{i}b^{j}$, $b^{j}$, $b^{j}a^{i}$,
$b^{j}c$ or $c$, where $i,j\geq 1$, from the initial configuration
$q_{0}a^{n}b^{n}a^{n}b^{n}c$.

If it deletes $a^{i}b^{j}$, $i,j\geq 1$, from the initial configuration, then
it follows the following sequence of transitions: $q_{0}a^{n}b^{n}a^{n}b^{n}c$
$\circlearrowright$ $q_{1}b^{n-j}a^{n}b^{n}ca^{n-i}$ $\circlearrowright^{*}$
$q_{f}$, where $q_{1}\in Q$. In this case, the automaton will also accept the
word $a^{i}b^{n}a^{n}b^{n}ca^{n-i}$ because
$q_{0}a^{i}b^{n}a^{n}b^{n}ca^{n-i}$ $\circlearrowright$
$q_{1}b^{n-j}a^{n}b^{n}ca^{n-i}$ $\circlearrowright^{*}$ $q_{f}$. Hence,
$a^{i}b^{n}a^{n}b^{n}ca^{n-i}$ $\in L(\mathcal{A})$ but
$a^{i}b^{n}a^{n}b^{n}ca^{n-i}$ $\not\in L_{c}$. Hence, it cannot delete
$a^{i}b^{j}$ from the initial configuration $q_{0}a^{n}b^{n}a^{n}b^{n}c$.
Similarly, it can be shown that it cannot delete $b^{j}$, $b^{j}a^{i}$,
$b^{j}c$ or $c$, where $i,j\geq 1$, from the initial configuration.

The automaton cannot delete all $a$’s starting from the initial configuration
$q_{0}a^{n}b^{n}a^{n}b^{n}c$ without deleting any $`b$’ or $`c$’ because in
this case the automaton will have to loop and the loop has only $a$’s. Then,
that loop can be used multiple times to create a mismatch in the indices of
$a$ and $b$. Hence, there would be a word $w\in L(\mathcal{A})$ such that
$|w|_{a}\neq|w|_{b}$ but $w\not\in L_{c}$. Hence, it cannot delete all $a$’s
starting from the initial configuration $q_{0}a^{n}b^{n}a^{n}b^{n}c$ without
deleting a $`b$’ or $`c$’.

Suppose the automaton deletes $a^{t}$ for $1\leq t<n$ without using loop, then
starting from the initial configuration $q_{0}a^{n}b^{n}a^{n}b^{n}c$, i.e.,
$q_{0}a^{n}b^{n}a^{n}b^{n}c$ $~{}\circlearrowright^{*}$
$q_{1}a^{n-t}b^{n}a^{n}b^{n}c$ $\circlearrowright^{*}$ $q_{f}$, where
$q_{1}\in Q$. Here, $q_{1}$ cannot delete only $a$’s and, hence, it will
delete $a^{i}b^{j}$, where $0\leq i<(n-t),1\leq j\leq m$, or $b^{j}a^{i}$,
where $1\leq j<m,1\leq i<m$, or $b^{j}c$, where $0\leq j<m$. Suppose it
deletes $a^{i}b^{j}$, where $0\leq i<(n-t),1\leq j\leq m$, then
$q_{0}a^{n}b^{n}a^{n}b^{n}c$ $\circlearrowright^{*}$
$q_{1}a^{n-t}b^{n}a^{n}b^{n}c$ $\circlearrowright$
$q_{2}b^{n-j}a^{n}b^{n}ca^{n-t-i}$ $\circlearrowright^{*}$ $q_{f}$, where
$q_{2}\in Q$. In this case, the automaton will also accept the word
$a^{t+i}b^{n}a^{n}b^{n}ca^{n-t-i}$ because
$q_{0}a^{t+i}b^{n}a^{n}b^{n}ca^{n-t-i}$ $\circlearrowright^{*}$
$q_{1}a^{i}b^{n}a^{n}b^{n}ca^{n-t-i}$ $\circlearrowright$
$q_{2}b^{n-j}a^{n}b^{n}ca^{n-t-i}$ $\circlearrowright^{*}$ $q_{f}$. Hence,
$a^{t+i}b^{n}a^{n}b^{n}ca^{n-t-i}$ $\in L(\mathcal{A})$ but
$a^{t+i}b^{n}a^{n}b^{n}ca^{n-t-i}$ $\not\in L_{c}$. Hence, $q_{1}$ cannot
delete $a^{i}b^{j}$. Similarly, it can be shown that $q_{1}$ cannot delete
$b^{j}a^{i}$ or $b^{j}c$.

Hence, we conclude $L_{c}\not\in$ $\bf{GRCOWJ}$.

From Example 7 and Lemma 5, we have that $\bf{GLCOWJ}$ $\not\subseteq$
$\bf{GRCOWJ}$. Similarly, it can be shown that $\bf{GRCOWJ\not\subseteq
GLCOWJ}$. Hence, we have the following result.

###### Proposition 3

The language classes $\bf{GRCOWJ}$ and $\bf{GLCOWJ}$ are incomparable.

##  6 $\bf{GCOWJFA}$ and $\bf{Chomsky~{}hierarchy}$

This section compares the language class $\bf{GRCOWJ}$ with the language
classes of Chomsky hierarchy. The class of regular languages, context free
languages and context sensitive languages are denoted by $\bf{REG}$, $\bf{CF}$
and $\bf{CS}$ respectively. The relation $\bf{REG\subset ROWJ}$ was proved in
[5] and in [15], the inclusion $\bf{ROWJ\subset GRLOWJ}$ was shown. Hence,
$\bf{REG\subset ROWJ}$ $\subset\bf{GRLOWJ}$. The class $\bf{CF}$ is
incomparable with both the language classes $\bf{ROWJ}$ [5] and $\bf{GRLOWJ}$
[15]. It was shown in [15] that $\bf{ROWJ\subset GRLOWJ}$ $\bf{\subset CS.}$
In this paper, we show that the language class $\bf{REG}$ is properly
contained in the class $\bf{GRCOWJ}$, the language classes $\bf{CF}$ and
$\bf{GRCOWJ}$ are incomparable and the class $\bf{GRCOWJ}$ is properly
contained in the class $\bf{CS}$. Same results hold good for the class
$\bf{GLCOWJ}$.

We recall some results from [5].

###### Lemma 6

$\bf{ROWJ}$ properly includes $\bf{REG}$, i.e., $\bf{REG\subset ROWJ}$.

###### Lemma 7

$\bf{CF}$ and $\bf{ROWJ}$ are incomparable.

From Lemma 6 and Note 4, we have the following result.

###### Proposition 4

$\bf{REG\subset GRCOWJ}$.

###### Proposition 5

The language classes $\bf{CF}$ and $\bf{GRCOWJ}$ are incomparable.

###### Proof

The Dyck language $D$ $\in$ $\bf{CF}$ but from Lemma 2 we have, $D\not\in$
$\bf{GRCOWJ}$. Hence, $\bf{CF}$ $\not\subseteq$ $\bf{GRCOWJ}$. From Lemma 7,
we conclude $\bf{ROWJ\not\subseteq CF}$ and hence, from Note 4, we have
$\bf{GRCOWJ}$ $\not\subseteq$ $\bf{CF}$.

###### Proposition 6

The language class $\bf{GRCOWJ}$ is a proper subset of the class $\bf{CS}$,
i.e., $\bf{GRCOWJ\subset CS}$.

###### Proof

Here, we give an idea on how the rules of a $\it{GRCOWJFA}$ are simulated by a
linear bounded automaton $(\it{LBA})$.

  1. 1.

For a word $w=w_{1}w_{2}\cdots w_{n}$ from the input alphabet, the tape of the
$LBA$ contains $w_{1}w_{2}\cdots w_{n}$, the tape head is at $w_{1}$ and the
$LBA$ is in the starting state $q_{0}$, the starting state of $\it{GRCOWJFA}$.
We assume, the tape is bounded from the left.

  2. 2.

Suppose the $LBA$ reaches in a state $p$ during its computation. Then, the
$LBA$ searches for the nearest subword, from $\Sigma_{p}$, of the word
available on the tape on the right side of the tape head.

  3. 3.

Suppose there is a nearest subword $x=x_{1}x_{2}\cdots x_{i}$ and the
corresponding rule of $\it{GRCOWJFA}$ is $(p,x,q)$. Then, the $LBA$ marks it
as $**\cdots*$ ($i$\- times). We assume $*$ is not a member of the alphabet
set. By nearest subword what we mean that suppose there is a word $uxv$ from
the input alphabet on the tape on the right side of the tape head, then $u$
does not contain any word from $\Sigma_{p}$ as a subword and
$u^{\prime}x^{\prime}\neq x$, where $u^{\prime}$ is a nonempty suffix of $u$
and $x^{\prime}$ is a nonempty prefix of $x$.

  4. 4.

If there is a word from the alphabet left side of $*$’s, then the $\it{LBA}$
cuts that word and pastes it right side of the word available right side of
$*$’s, i.e., suppose after marking $x_{1}x_{2}\cdots x_{i}$ as $**\cdots*$,
the tape contains $u**\cdots*v$. Then, the $LBA$ cuts $u$ and pastes after $v$
and it goes to the state $q$ and the tape head is at the first symbol of $vu$.

  5. 5.

Suppose there are no symbols from the alphabet set present on the tape and the
$LBA$ is in a state which is a final state of the $\it{GRCOWJFA}$, then the
$LBA$ accepts the input word.

Hence, we conclude that $\bf{GRCOWJ\subseteq CS}$. But from Lemma 2, we have
$D\not\in$ $\bf{GRCOWJ}$. Hence, $\bf{GRCOWJ\subset CS}$. Similarly, it can be
shown that $\bf{GLCOWJ\subset CS}$.

##  7 Closure Properties

In this section we discuss closure properties of the language classes
$\bf{GRCOWJ}$ and $\bf{GLCOWJ}$ under set theoretic as well as language
operations. The classes $\bf{ROWJ}$ [5] and $\bf{GRLOWJ}$ [15] are not closed
under intersection, concatenation and reversal. Moreover, $\bf{ROWJ}$ is not
closed under the operation Kleene star [5], union, complement and homomorphism
[3]. In the same line, we show that the class $\bf{GRCOWJ}$ is not closed
under intersection, concatenation, reversal and Kleene star. The same results
hold true for the class $\bf{GLCOWJ}$. We begin the section with an Example of
a $\it{GRCOWJFA}$. The language of the $\it{GRCOWJFA}$ will be used to prove
non-closure of the class $\bf{GRCOWJ}$ under intersection, concatenation and
Kleene star.

###### Example 8

Consider the $\it{GRCOWJFA}$
$\mathcal{A}=(\\{a,b\\},\\{q_{0},q_{1}\\},q_{0},\\{q_{0},q_{1}\\},R)$, where
$R=\\{(q_{0},ab,q_{1}),(q_{1},ba,q_{0})\\}.$ Words $a^{n}b^{n}\in
L(\mathcal{A})$ for all $n\geq 0$ because $q_{0}a^{n}b^{n}\circlearrowright
q_{1}b^{n-1}a^{n-1}\circlearrowright
q_{0}a^{n-2}b^{n-2}\circlearrowright\cdots\circlearrowright q_{1}/q_{0}$. If
$n$ is even, then the automaton will be in the state $q_{0}$ and if $n$ is
odd, then the automaton will be in the state $q_{1}$. Let
$L(\mathcal{A})=L_{ab}$.

First we prove that the class $\bf{GRCOWJ}$ is not closed under Kleene star.
We show that there exists a language $L$ in the class $\bf{GRCOWJ}$ but Kleene
star $L^{*}$ of $L$ is not in the class $\bf{GRCOWJ}$.

###### Proposition 7

The language class $\bf{GRCOWJ}$ is not closed under Kleene star.

###### Proof

It can be shown, by adding some new states and rules in Example 8, that the
language $cL_{ab}\in$ $\bf{GRCOWJ}$. Let $L=(cL_{ab})^{*}$. We show that
$L\not\in\bf{GRCOWJ}$. If $L\in\bf{GRCOWJ}$, then there exists a
$\it{GRCOWJFA}$ $\mathcal{A}=(\Sigma,Q,q_{0},F,R)$ such that
$L(\mathcal{A})=L$. Let $l=|Q|$, $m=max\\{|w|~{}:~{}(p,w,q)\in R\\}$ and
$n>lm.$ Clearly, $ca^{n}b^{n}c\in L=L(\mathcal{A}).$ Hence, there exists a
sequence of transitions such that
$q_{0}ca^{n}b^{n}c\circlearrowright^{*}q_{f}$, where $q_{f}\in F$. The
automaton can delete $c$, $ca^{i}$, $a^{i}$, $a^{i}b^{j}$, $b^{j}$ or
$b^{j}c$, where $i,j\geq 1$, from the initial configuration
$q_{0}ca^{n}b^{n}c$.

  * Case 1.

If it deletes $a^{i}$, then the automaton makes the following sequence of
transitions $q_{0}ca^{n}b^{n}c$ $\circlearrowright$ $q_{1}a^{n-i}b^{n}cc$
$\circlearrowright^{*}$ $q_{f}$, where $q_{1}\in Q$. Then, $a^{n}b^{n}cc\in
L(\mathcal{A})$ because of Lemma 1. But $a^{n}b^{n}cc\not\in L$. Hence, the
automaton cannot delete $a^{i}$ from the initial configuration. Similarly, it
can be shown that it cannot delete $a^{i}b^{j}$, $b^{j}$ or $b^{j}c$ from the
initial configuration $q_{0}ca^{n}b^{n}c$.

  * Case 2.

Hence, the automaton will have to delete $`c$’ or $ca^{i}$ from the initial
configuration $q_{0}ca^{n}b^{n}c$. We deal with the case $`c$’ only, the case
of $ca^{i}$ can be dealt similarly. If it deletes $c$ from the initial
configuration $q_{0}ca^{n}b^{n}c$. Then, $q_{0}ca^{n}b^{n}c$
$\circlearrowright$ $q_{1}a^{n}b^{n}c$ $\circlearrowright^{*}$ $q_{f}$, where
$q_{1}\in Q$. It can delete $a^{i_{1}}$, $a^{i_{1}}b^{j_{1}}$, $b^{j_{1}}$,
$b^{j_{1}}c$ or $c$, where $i_{1},j_{1}\geq 1$, from the configuration
$q_{1}a^{n}b^{n}c$.

  * Sub-Case 2.1.

If it deletes $a^{i_{1}}b^{j_{1}}$ from the configuration $q_{1}a^{n}b^{n}c$,
then $q_{0}ca^{n}b^{n}c$ $\circlearrowright$ $q_{1}a^{n}b^{n}c$
$\circlearrowright$ $q_{2}b^{n-j_{1}}ca^{n-i_{1}}$ $\circlearrowright^{*}$
$q_{f}$, where $q_{2}\in Q$. Then, $ca^{i_{1}}b^{n}ca^{n-i_{1}}\in
L(\mathcal{A})$ because of Lemma 1. But $ca^{i_{1}}b^{n}ca^{n-i_{1}}\not\in
L$. Similarly, it cannot delete $b^{j_{1}}$ or $b^{j_{1}}c$ from the
configuration $q_{1}a^{n}b^{n}c$.

  * Sub-Case 2.2.

If it deletes $c$ from the configuration $q_{1}a^{n}b^{n}c$. Then,
$q_{0}ca^{n}b^{n}c$ $\circlearrowright$ $q_{1}a^{n}b^{n}c$ $\circlearrowright$
$q_{2}a^{n}b^{n}$ $\circlearrowright^{*}$ $q_{f}$, where $q_{2}\in Q$. In this
case, $b^{k}\not\in\Sigma_{q_{1}}$ for $1\leq k\leq m$. Now, consider a word
$cb^{n}ca^{n}$. The word $cb^{n}ca^{n}\in L(\mathcal{A})$ because
$q_{0}cb^{n}ca^{n}$ $\circlearrowright$ $q_{1}b^{n}ca^{n}$ $\circlearrowright$
$q_{2}a^{n}b^{n}$ $\circlearrowright^{*}$ $q_{f}$. But $cb^{n}ca^{n}\not\in
L$.

  * Sub-Case 2.3.

Hence, the automaton will have to delete $a^{i_{1}}$ from the configuration
$q_{1}a^{n}b^{n}c$. The automaton cannot delete all $a$’s starting from the
configuration $q_{1}a^{n}b^{n}c$ without deleting $b$ or $c$ because in this
case it will use a loop, because of the choice of $n$, consisting of only
$a$’s to delete all $a$’s and the same loop can be used multiple times to
create a difference in the indices of $a$ and $b$ and, hence there will be a
word $w\in L(\mathcal{A})$ such that $|w|_{a}\neq|w|_{b}$ but, such $w\not\in
L$. Suppose it deletes $a^{t}$, $1\leq t<n$, without using loop, starting from
the configuration $q_{1}a^{n}b^{n}c$ without deleting $b$ or $c$, then
$q_{0}ca^{n}b^{n}c$ $\circlearrowright$ $q_{1}a^{n}b^{n}c$
$\circlearrowright^{*}$ $q_{2}a^{n-t}b^{n}c$ $\circlearrowright^{*}$ $q_{f}$.
From the configuration $q_{2}a^{n-t}b^{n}c$, it can delete
$a^{i^{\prime}}b^{j^{\prime}}$, where $0\leq i^{\prime}<(n-t),1\leq
j^{\prime}\leq m$, or $b^{j^{\prime}}c$, where $0\leq j^{\prime}<m$. In this
case, it will accept $ca^{t+i^{\prime}}b^{n}ca^{n-t-i^{\prime}}$ or
$ca^{t}b^{n}ca^{n-t}$, depending on the deletion of
$a^{i^{\prime}}b^{j^{\prime}}$ or $b^{j^{\prime}}c$ respectively. But neither
$ca^{t+i^{\prime}}b^{n}ca^{n-t-i^{\prime}}$ nor $ca^{t}b^{n}ca^{n-t}$ are
elements of $L$.

Hence, from above discussed cases, we conclude $cL_{ab}\in$ $\bf{GRCOWJ}$ but
$(cL_{ab})^{*}\not\in\bf{GRCOWJ}$.

To prove other closure properties of the class $\bf{GRCOWJ}$, we give a Lemma
which gives a language that is not in the class $\bf{GRCOWJ}$. The Lemma can
be proved similar to Lemma 2.

###### Lemma 8

There does not exist any $\it{GRCOWJFA}$ that accepts the language
$\\{a^{n}b^{n}~{}|~{}n\geq 0\\}$.

Now, we discuss other closure properties of the language class $\bf{GRCOWJ}$.

###### Proposition 8

$\bf{GRCOWJ}$ is not closed under

  * 1.

intersection;

  * 2.

concatenation;

  * 3.

reversal;

  * 4.

Kleene star.

###### Proof

From Proposition 4 and Example 8, we have $a^{*}b^{*},L_{ab}\in\bf{GRCOWJ}$.
But $a^{*}b^{*}\cap L_{ab}=\\{a^{n}b^{n}~{}|~{}n\geq 0\\}\not\in\bf{GRCOWJ}$,
by Lemma 8. Hence, $\bf{GRCOWJ}$ is not closed under intersection.

From Example 8 and Proposition 4, we have $L_{ab},\\{c\\}\in\bf{GRCOWJ}$.
Similar to Lemma 5, we can prove $L_{ab}\\{c\\}\not\in\bf{GRCOWJ}$. Hence,
$\bf{GRCOWJ}$ is not closed under concatenation.

It was shown in [5] that the languages
$c\\{w\in\\{a,b\\}^{*}~{}|~{}|w|_{a}=|w|_{b}\\}\in\bf{ROWJ}$. From Note 4, we
have $\bf{ROWJ\subset GRCOWJ}$ and hence
$c\\{w\in\\{a,b\\}^{*}~{}|~{}|w|_{a}=|w|_{b}\\}\in\bf{GRCOWJ}$. Similar to the
proof given in Lemma 5, one can show that
$\\{w\in\\{a,b\\}^{*}~{}|~{}|w|_{a}=|w|_{b}\\}c\not\in\bf{GRCOWJ}$, Hence,
$\bf{GRCOWJ}$ is not closed under reversal.

##  8 Conclusion

In this paper, we have introduced a new extended version of the model one-way
jumping finite automata ($\it{OWJFA}$) called generalized circular one-way
jumping finite automata ($\it{GCOWJFA}$). By extended version, we mean that
$\it{OWJFA}$ change its states by deleting a letter of an input word whereas
$\it{GCOWJFA}$ change its states by deleting a subword of an input word. The
newly introduced version $\it{GCOWJFA}$ is different from one of the extended
versions generalized linear one-way jumping finite automata ($\it{GLOWJFA}$)
of $\it{OWJFA}$. Like $\it{OWJFA}$ and $\it{GLOWJFA}$, $\it{GCOWJFA}$ also has
two variants called generalized right circular one-way jumping finite automata
($\it{GRCOJFA}$) and generalized left circular one-way jumping finite automata
($\it{GLCOWJFA}$). We have shown that the newly defined version $\it{GCOWJFA}$
is more powerful than $\it{OWJFA}$. We also show that its computational power
is distinct from that of $\it{GLOWJFA}$. We have compared the computational
power of the variants $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$. The language
classes of $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$ are compared with the language
classes of Chomsky hierarchy. Finally, closure properties of the language
classes of $\it{GRCOWJFA}$ and $\it{GLCOWJFA}$ have been investigated.

## References

  * [1] Beier, S., Holzer, M.: Decidability of Right One-Way Jumping Finite Automata. Proc. of LNCS 11088, pp. 109–120, Springer, Cham (2018)
  * [2] Beier, S., Holzer, M.: Nondeterministic Right One-Way Jumping Finite Automata. Proc. of LNCS 11612, pp. 74–85, Springer, Cham (2019)
  * [3] Beier, S., Holzer, M.: Properties of right one-way jumping finite automata. Theoretical Computer Science 798, 78–94 (2019)
  * [4] Beier, S., Holzer, M., Kutrib, M.: Operational State Complexity and Decidability of Jumping Finite Automata. International Journal of Foundations of Computer Science 30(1), 5–27 (2019)
  * [5] Chigahara, H., Fazekas, S. Z., Yamamura, A.: One-Way Jumping Finite Automata. International Journal of Foundations of Computer Science 27(3), 391–405 (2016)
  * [6] Fazekas, S. Z., Hoshi, K., Yamamura, A.: Enhancement of Automata with Jumping Modes. Proc. of LNCS 11525, pp. 62–76, Springer, Cham (2019)
  * [7] Fazekas, S. Z., Hoshi, K., Yamamura, A.: Two-Way Jumping Automata. Proc. of LNCS 12340, pp. 108–120, Springer, Cham (2020)
  * [8] Fernau, H., Paramasivan, M., Schmid, M. L., Vorel, V.: Characterization and complexity results on jumping finite automata. Theoretical Computer Science 679, 31–52 (2017)
  * [9] Kocman, R., Krivka, Z., Meduna, A.: On double-jumping finite automata and their closure properties. RAIRO - Theoretical Informatics and Applications 52(2-3-4), 185–199 (2018)
  * [10] Kocman, R., Meduna, A.: On Parallel Versions of Jumping Finite Automata. Proceedings of the 2015 Federated Conference on Software Development and Object Technologies, pp. 142–149, Springer, Cham (2017)
  * [11] Kocman, R., Nagy, B., Krivka, Z., Meduna, A.: A Jumping $5^{\prime}\rightarrow 3^{\prime}$ Watson-Crick Finite Automata Model. NCMA 2018, pp. 117–132, OCG<EMAIL_ADDRESS>Vienna (2018)
  * [12] Krithivasan, K., Rama, R.: Introduction to Formal Languages, Automata Theory and Computation. Pearson, India (2009)
  * [13] Mahalingam, K., Mishra, U. K., Raghavan, R.: Watson-Crick Jumping Finite Automata. International Journal of Foundations of Computer Science 31(7), 891–913 (2020)
  * [14] Meduna, A., Zemek, P.: Jumping Finite Automata. International Journal of Foundations of Computer Science 23(7), 1555–1578 (2012)
  * [15] Mishra, U. K., Mahalingam, K., Raghavan, R.: Generalized Linear One-Way Jumping Finite Automata. arXiv (2021)
  * [16] Vorel, V: On basic properties of jumping finite automata. International Journal of Foundations of Computer Science 29(1), 1–15 (2018)
  * [17] Vorel, V.: Two Results on Discontinuous Input Processing. Proc. of LNCS 9777, pp. 205–216, Springer, Cham (2016)