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

Ujjwal Kumar Mishra  Kalpana Mahalingam  Rama Raghavan

###### Abstract

A new 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. These automata read an input
symbol-by-symbol and jump only in one direction. A generalized linear one-way
jumping finite automaton makes jumps after deleting a substring of an input
string and then changes its state. These automata can make sequence of jumps
in only one direction on an input string either from left to right or from
right to left. We show that newly defined model is powerful than its original
counterpart. We define and compare the variants, generalized right linear one-
way jumping finite automata and generalized left linear one-way jumping finite
automata. We also compare the newly defined models 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.

##  1 Introduction

First discontinuous model of computation called general jumping finite
automata $\it{(GJFA)}$ was introduced in [13] by Meduna et. al. These automata
read the given input in a discontinuous manner. The automata can jump in
either direction to read the input. In [14], the author solved questions
related to closure properties of the model $\it{GJFA}$ which were left open in
[13]. The author showed that universality, equivalence and inclusion are
undecidable for $\it{GJFA}$, in [15]. Some decision problems of the model
jumping finite automata ($\it{JFA}$), which is a restricted version of
$\it{GJFA}$, had been discussed in [4]. Results related to the complexity of
the model $\it{JFA}$ were discussed in [7] and [4]. Following [13], several
other jumping transition models have been defined and studied in [9, 5, 2, 6,
8, 12, 10].

The model which is of our interest is one-way jumping finite automata
($\it{OWJFA}$), defined in [5]. The model $\it{OWJFA}$ is defined by giving a
restriction on jumping behaviour of the model $\it{JFA}$. 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 reading a symbol. We define a new jumping transition model called
generalized linear one-way jumping finite automata ($\it{GLOWJFA}$). These
automata can process a subword in a state. We show that this generalization
increases the power of $\it{OWJFA}.$ Similar to $\it{OWJFA}$, we define two
types of $\it{GLOWJFA}$: generalized right linear one-way jumping finite
automata ($\it{GRLOWJFA}$) and generalized left linear one-way jumping finite
automata ($\it{GLLOWJFA}$). $\it{GRLOWJFA}$ delete an input starting from the
leftmost end of the input. They can jump over a part of the input if they
cannot read it. These automata make jumps from left to right. But, if at any
stage, the present state cannot read any subwords to the right of it, then the
automaton makes a jump from right to left and jumps before the leftmost symbol
of the input tape. Similarly, $\it{GLLOWJFA}$ process an input from right to
left, starting from the rightmost end of the input. They can jump over a part
of the input if they cannot read. These automata jump from right to left. But,
if at any stage, the present state cannot read any subwords to the left of it,
then the automaton makes a jump from left to right and jumps before the
rightmost symbol of the input tape.

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

This 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}$
and give an example of $\it{ROWJFA}$, in this section. The models
$\it{GRLOWJFA}$ and $\it{GLLOWJFA}$ are defined in Section 3. We give examples
for our new definitions. In Section 4, we compare $\it{GRLOWJFA}$ with
$\it{ROWJFA}$ and $\it{GLLOWJFA}$ with $\it{LOWJFA}$. The models
$\it{GRLOWJFA}$ and $\it{GLLOWJFA}$ are compared in Section 5. In Section 6,
the language classes of the newly introduced models 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$. 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 a finite set $A$, $|A|$ denotes the number of elements in
$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 [11].

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
tuple $\mathcal{A}=(\Sigma,Q,q_{0},F,R)$, where $\Sigma$ is an alphabet set,
$Q$ is a finite set of states, $q_{0}$ is a 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 $\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 $\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}$
$\mathcal{A}=(\\{a,b\\},\\{q_{0},q_{1},q_{2},q_{3}\\},q_{0},\\{q_{2}\\},R)$,
where
$R=\\{(q_{0},b,q_{1}),(q_{0},a,q_{2}),(q_{2},a,q_{3}),(q_{3},b,q_{2})\\}$.
Here, $\Sigma_{q_{0}}=\\{a,b\\}$, $\Sigma_{q_{1}}=\emptyset$,
$\Sigma_{q_{2}}=\\{a\\},\Sigma_{q_{3}}=\\{b\\}$. Since
$\Sigma_{q_{0}}=\\{a,b\\}$, the automaton cannot jump over any symbol $`a$’ or
$`b$’ and hence, all strings starting with $`b$’ will reach the state $q_{1}$
and are rejected. Strings starting with $`a$’ will go to the state $`q_{2}$’
and since $\Sigma_{q_{2}}=\\{a\\}$, at the state $q_{2}$ the automaton can
jump over a sequence of $`b$’s and will delete an $`a$’ and go to the state
$q_{3}$. Similarly, since $\Sigma_{q_{3}}=\\{b\\}$, at state $q_{3}$ the
automaton can jump over a sequence of $`a$’s and will delete $`b$’ and go to
state $q_{2}$. For example, consider a string ‘$abbaa$’. The sequence of
transitions is

$q_{0}abbaa\circlearrowright q_{2}bbaa\circlearrowright
q_{3}abb\circlearrowright q_{2}ba\circlearrowright q_{3}b\circlearrowright
q_{2}.$

Hence, the language accepted by the automaton is

$L_{R}(\mathcal{A})=\\{aw~{}:~{}|w|_{a}=|w|_{b},w\in\\{a,b\\}^{*}\\}.$
$q_{0}$start$q_{2}$$q_{1}$$q_{3}$abab

##  3 Generalized Linear One-Way Jumping Finite Automata

In a right one-way jumping finite automaton, the read head moves in one
direction only and starts from the leftmost symbol of the 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 will start reading the
remaining concatenated input freshly from the last visited state. The
computation continues until all the letters are read or the automaton is stuck
in a state in which it cannot delete any letter of the remaining input. If a
transition is defined for the current state and the next letter to be read,
then the automaton deletes the symbol. 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.

We extend this definition based on reading length of a word and define a
generalized right/left linear one-way jumping finite automaton. A generalized
right linear one-way jumping finite automaton 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. It reads the nearest available subword of the word present
on the input tape. If there is no transition available for a state, the
automaton returns(head of the automaton returns) to the leftmost position of
the current input and continues its computation. The formal definitions of
generalized right linear one-way jumping finite automaton and generalized left
linear one-way jumping finite automaton are 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^{*}$.

  * 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 GRLOWJFA, we define the notion of a generalized left linear
one-way jumping finite automaton as below.

###### 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 Definition 1 with the following example.

###### Example 2

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

$q_{0}$start$q_{1}$abb

Here, $\Sigma_{q_{0}}=\\{a,bb\\}$ and $\Sigma_{q_{1}}=\emptyset$. We first
consider the automaton as a $\it{GRLOWJFA}$. The automaton can read arbitrary
number of $a$’s at state $q_{0}$ and can jump only one $b$ at $q_{0}$. Note
that as $\Sigma_{q_{0}}=\\{a,bb\\}$, the automaton at $q_{0}$ can neither jump
over an $a$ or $bb$. Once it reads $bb$, it reaches the final state $q_{1}$
and no more transition is possible. Consider the word $a^{l}ba^{m}ba^{n}$,
where $l,n\geq 0,m\geq 1$. Then,

$q_{0}a^{l}ba^{m}ba^{n}\curvearrowright^{*}q_{0}ba^{m}ba^{n}\curvearrowright
bq_{0}a^{m-1}ba^{n}$ $\curvearrowright^{*}bq_{0}ba^{n}\curvearrowright
bbq_{0}a^{n-1}\curvearrowright^{*}bbq_{0}\curvearrowright
q_{0}bb\curvearrowright q_{1}$

and,

$L_{GRL}(\mathcal{A})=\\{a^{n}bb~{}|~{}n\geq
0\\}\cup\\{a^{l}ba^{m}ba^{n}~{}|~{}l,n\geq 0,m\geq 1\\}.$

Similarly, the language accepted by the automaton when it is considered as
$\it{GLLOWJFA}$ is

$L_{GLL}(\mathcal{A})=\\{bba^{n}~{}|~{}n\geq
0\\}\cup\\{a^{l}ba^{m}ba^{n}~{}|~{}l,n\geq 0,m\geq 1\\}.$

Now, we give an example which shows that the intersection of the language
classes $\bf{GRLOWJ}$ and $\bf{GLLOWJ}$ is non empty, where $\bf{GRLOWJ}$ and
$\bf{GLLOWJ}$ represent the language classes accepted by $\it{GRLOWJFA}$ and
$\it{GLLOWJFA}$, respectively.

###### Example 3

$q_{0}$start$q_{1}$abb

When considered as $\it{GRLOWJFA}$, the automaton will jump to $ab$ from the
configuration $q_{0}b^{n}abb^{m}$, it will delete $ab$ and will go to the
configuration $b^{n}q_{1}b^{m}$. Then, it will go to the configuration
$b^{n}q_{1}$ using repeated application of the rule $(q_{1},b,q_{1})$. The
automaton will jump to the configuration $q_{1}b^{n}$ from the configuration
$b^{n}q_{1}$ and using the repeated application of the rule $(q_{1},b,q_{1})$
the automation will reach $q_{1}$ and hence, accepts the word $b^{n}ab^{m}$.
Consider a word $b^{m}abb^{n}$, where $m,n\geq 0$. Then,

$q_{0}b^{m}abb^{n}\curvearrowright
b^{m}q_{1}b^{n}\curvearrowright^{*}b^{m}q_{1}\curvearrowright
q_{1}b^{m}\curvearrowright^{*}q_{1}.$

Similarly, the case of $\it{GLLOWJFA}$ can be explained. Note that the set of
rules is $R=\\{(q_{1},ab,q_{0}),(q_{1},b,q_{1})\\}$, when the automaton is
considered as $\it{GLLOWJFA}$. Hence,

$L_{GRL}(\mathcal{A})=L_{GLL}(\mathcal{A})=\\{b^{m}abb^{n}~{}|~{}n,m\geq
0\\}.$

###### Note 1

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

##  4 GLOWJ and OWJ

In this section, we compare the language classes $\bf{ROWJ}$ and $\bf{GRLOWJ}$
as well as the language classes $\bf{LOWJ}$ and $\bf{GLLOWJ}$, here
$\bf{ROWJ}$ and $\bf{LOWJ}$ represent the language classes accepted by
$\it{ROWJFA}$ and $\it{LOWJFA}$, respectively. We show that the language class
$\bf{ROWJ}$ is a proper subset of the language class $\bf{GRLOWJ}$ and the
language class $\bf{LOWJ}$ is a proper subset of the language class
$\bf{GLLOWJ}$.

By definitions of $\it{GRLOWJFA}$ and $\it{ROWJFA}$, it is clear that when the
rules of a $\it{GRLOWJFA}$ satisfy the condition: if $(p,w,q)\in R$, then
$|w|=1$, then the $\it{GRLOWJFA}$ is same as $\it{ROWJFA}$. Hence, we have
$\bf{ROWJ}$ $\subseteq$ $\bf{GRLOWJ}$. Similarly, $\bf{LOWJ}$ $\subseteq$
$\bf{GLLOWJ}$. Now, we give a language which is accepted by the model
$\it{GRLOWJFA}$ but not by the model $\it{ROWJFA}$.

###### Example 4

Consider the generalized right linear one-way jumping finite automaton
$\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
$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_{GRL}(\mathcal{A})=\\{w\in\\{a,b\\}^{*}~{}|~{}|w|_{a}=|w|_{b}$ or
$|w|_{b}=0\\}$.

It was proved in [3] that the language of Example 4 cannot be accepted by any
$\it{ROWJFA}$. Hence, we have the following result.

###### Lemma 1

There exists a language which is accepted by a $\it{GRLOWJFA}$ but not by any
$\it{ROWJFA}$ and hence, $\bf{ROWJ\subset GRLOWJ}$.

Now, we give an example of a $\it{GLLOWJFA}$ and we show that the language of
the automaton cannot be accepted by any $\it{LOWJFA}$.

###### Example 5

Consider a $\it{GLLOWJFA}$
$\mathcal{A}=(\\{a,b\\},\\{q_{0}\\},q_{0},\\{q_{0}\\},\\{(q_{0},ab,q_{0})\\})$.
One can verify that the language accepted by the automaton is the Dyck
language, $D$.

We show the Dyck language cannot be accepted by any $\it{LOWJFA}$.

###### Lemma 2

The Dyck language cannot be accepted by any $\it{LOWJFA}$.

###### Proof

Let the Dyck language, $D$, accepted by a $\it{LOWJFA}$, say
$\mathcal{A}=(\Sigma,$ $Q,q_{0},F,R)$. Then $L(\mathcal{A})=D$. Take a
positive integer $k$, where $k>|Q|$. Since $a^{n}b^{n}\in D$ for all $n\geq
0$, therefore $a^{k}b^{k}\in D$ and hence, $a^{k}b^{k}\in L(\mathcal{A})$.
Then there exists a sequence of transitions such that
$q_{f}\prescript{*}{}{\circlearrowleft}~{}a^{k}b^{k}q_{0}$, where $q_{f}\in
F$.

First we show the automaton cannot delete any ‘$a$’ without deleting a $`b$’
from the configuration $a^{k}b^{k}q_{0}$. Suppose the automaton deletes an
$`a$’ from the configuration $a^{k}b^{k}q_{0}$, then there exist a state
$q^{\prime}\in Q$ and $(q^{\prime},a,q_{0})\in R$, $b\not\in\Sigma_{q_{0}}$
such that
$q_{f}\prescript{*}{}{\circlearrowleft}~{}b^{k}a^{k-1}q^{\prime}\circlearrowleft
a^{k}b^{k}q_{0}$. Then, the word $b^{k}a^{k}\in L(\mathcal{A})$ because
$q_{f}\prescript{*}{}{\circlearrowleft}~{}b^{k}a^{k-1}q^{\prime}\circlearrowleft
b^{k}a^{k}q_{0}$. But $b^{k}a^{k}\not\in D$.

Now, we show that the automaton will have to delete all $b$’s before deleting
any $`a$’ starting from the configuration $a^{k}b^{k}q_{0}$. Suppose the
automaton deletes $t$ $b$’s starting from the configuration $a^{k}b^{k}q_{0}$
before deleting an ‘$a$’, where $1\leq t<k$. Then there exists a sequence of
transitions such that
$q_{f}\prescript{*}{}{\circlearrowleft}~{}b^{k-t}a^{k-1}q^{\prime\prime}\circlearrowleft
a^{k}b^{k-t}q^{\prime}\prescript{*}{}{\circlearrowleft}~{}a^{k}b^{k}q_{0}$,
where $q^{\prime},q^{\prime\prime}\in Q$, $(q^{\prime\prime},a,q^{\prime})\in
R$ and $b\not\in\Sigma_{q^{\prime}}$. Then, the word $b^{k-t}a^{k}b^{t}$ will
also be in $L(\mathcal{A})$ because
$q_{f}\prescript{*}{}{\circlearrowleft}~{}b^{k-t}a^{k-1}q^{\prime\prime}\circlearrowleft
b^{k-t}a^{k}q^{\prime}\prescript{*}{}{\circlearrowleft}~{}b^{k-t}a^{k}b^{t}q_{0}$.
But $b^{k-t}a^{k}b^{t}\not\in D$.

Hence, the automaton will have to delete all $b$’s starting from the
configuration $a^{k}b^{k}q_{0}$ before deleting any ‘$a$’. But in that case
the automaton will have to loop because $|a^{k}b^{k}|_{b}>|Q|$ and hence, the
words of the form $a^{k}b^{k+l}$ will be in $L(\mathcal{A})$, where $l\geq 0$.
But $a^{k}b^{k+l}\not\in D$ for all $l\geq 0$.

Hence, the Dyck language cannot be accepted by any $\it{LOWJFA}.$

From the above Lemma we have the following result.

###### Lemma 3

There exists a language which is accepted by a $\it{GLLOWJFA}$ but not by any
$\it{LOWJFA}$ and hence, $\bf{LOWJ\subset GLLOWJ}$.

##  5 $\it{GRLOWJFA}$ and $\it{GLLOWJFA}$

In this section, we compare the language classes $\bf{GRLOWJ}$ and
$\bf{GLLOWJ}$. We also establish a relationship between the languages of the
class $\bf{GRLOWJ}$ and the languages of the class $\bf{GLLOWJ}$.

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

###### Proposition 1

For a given 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.

###### Proof

Let $L_{1}\in\bf{GRLOWJ}$. Then there exists a $\it{GRLOWJFA}$, say
$\mathcal{A}_{1}=(\Sigma,Q,q_{0},F,R)$, such that $L_{1}=L(\mathcal{A}_{1})$.
We construct a $\it{GLLOWJFA}$, 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}$. Under this construction
we have the following lemmas:

###### Lemma 4

If $x,y,z\in\Sigma^{*}$, $u\in\Sigma^{+}$ and $p,q\in Q$, then
$xpyuz\curvearrowright_{\mathcal{A}_{1}}xyqz$ if and only if
$z^{R}qy^{R}x^{R}$ $\prescript{}{{\mathcal{A}_{2}}}{\curvearrowleft}$
$z^{R}u^{R}y^{R}px^{R}$.

###### Proof

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

###### Lemma 5

If $x\in\Sigma^{+}$, $y\in\Sigma^{*}$ and $p\in Q$, then
$xpy\curvearrowright_{\mathcal{A}_{1}}pxy$ if and only if $y^{R}x^{R}p$
$\prescript{}{{\mathcal{A}_{2}}}{\curvearrowleft}$ $y^{R}px^{R}$.

###### Proof

Let $x\in\Sigma^{+}$, $y\in\Sigma^{*}$ and $p\in Q$. Now,
$xpy\curvearrowright_{\mathcal{A}_{1}}pxy$ if and only if $y$ does not contain
any word from $\Sigma_{R,p}$ as a subword if and only if $y^{R}$ does not
contain any word $\Sigma_{R^{\prime},p}$ as a subword if and only if
$y^{R}x^{R}p$ $\prescript{}{{\mathcal{A}_{2}}}{\curvearrowleft}$
$y^{R}px^{R}$. Hence, for $x\in\Sigma^{+}$, $y\in\Sigma^{*}$ and $p\in Q$,
$xpy\curvearrowright_{\mathcal{A}_{1}}pxy$ if and only if $y^{R}x^{R}p$
$\prescript{}{{\mathcal{A}_{2}}}{\curvearrowleft}$ $y^{R}px^{R}$.

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

###### Corollary 1

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

Now, we compare the language classes $\bf{GRLOWJ}$ and $\bf{GLLOWJ}$. We give
a language which is in the class $\bf{GLLOWJ}$ and prove that the language is
not in the class $\bf{GRLOWJ}$ which proves $\bf{GLLOWJ}$ $\not\subseteq$
$\bf{GRLOWJ}$. Similarly, it can be proved $\bf{GRLOWJ}$ $\not\subseteq$
$\bf{GLLOWJ}$. Hence, we conclude the language classes $\bf{GRLOWJ}$ and
$\bf{GLLOWJ}$ are incomparable.

###### Example 6

Consider the $\it{GLLOWJFA}$
$\mathcal{A}=(\\{a,b,c\\},\\{q_{0},q_{1},q_{2}\\},q_{0},\\{q_{1}\\},R)$, where
$R=\\{(q_{1},c,q_{0}),(q_{1},ab,q_{1}),(q_{2},a,q_{0}),(q_{2},b,q_{0})\\}$.
The language accepted by the automaton is $L_{GLL}(\mathcal{A})=Dc$, where $D$
is the Dyck language.

Now, we prove that the language $Dc$ is not in the class $\bf{GRLOWJ}$.

###### Lemma 6

There does not exist any $\it{GRLOWJFA}$ that accepts the language $Dc$, where
$D$ is the Dyck language.

###### Proof

If $Dc\in\bf{GRLOWJ}$, then there exists a $\it{GRLOWJFA}$, say
$\mathcal{A}=(\Sigma,Q,q_{0},$ $F,R)$, such that $L(\mathcal{A})=Dc$. Let
$l=|Q|$ and $m=max\\{|w|~{}|~{}(p,w,q)$ $\in R\\}$. Choose a natural number
$n>5lm$. Clearly, $a^{n}b^{n}c\in Dc=L(\mathcal{A})$. Hence, there exists a
sequence of transitions such that $q_{0}a^{n}b^{n}c\curvearrowright^{*}q_{f}$,
where $q_{f}\in F$.

From the configuration $q_{0}a^{n}b^{n}c$, the automaton can go to one of the
following configurations: $qa^{n-i}b^{n}c$, $a^{n-i}qb^{n-j}c$,
$a^{n}qb^{n-j}c$, $a^{n}b^{n-j}q$, $a^{n}b^{n}q$, where $i,j\geq 1$, $q\in Q$.

The ‘$c$’ cannot be deleted by the automaton before deleting all $a$’s and
$b$’s. If this happens, then there would be a sequence of transitions such
that
$q_{0}a^{n}b^{n}c\curvearrowright^{*}a^{n-k_{1}}b^{n-k_{2}}q\curvearrowright
qa^{n-k_{1}}b^{n-k_{2}}\curvearrowright^{*}q_{f}$, where $k_{1},k_{2}\geq 0$
and at least one of them not equal to $n$, $q\in Q$. But then, the following
sequence is also possible: $q_{0}a^{i_{1}}b^{j_{1}}a^{i_{2}}b^{j_{2}}\cdots
a^{i_{t}}b^{j_{t}}ca^{n-k_{1}}b^{n-k_{2}}\curvearrowright^{*}qa^{n-k_{1}}b^{n-k_{2}}\curvearrowright^{*}q_{f}$,
where $\sum_{k=1}^{t}i_{k}=k_{1},\sum_{k=1}^{t}j_{k}=k_{2}$. Hence, the word
$a^{i_{1}}b^{j_{1}}a^{i_{2}}b^{j_{2}}\cdots
a^{i_{t}}b^{j_{t}}ca^{n-k_{1}}b^{n-k_{2}}$ $\in L(\mathcal{A})$. Since at
least one of $(n-k_{1})$ and $(n-k_{2})$ is non-zero, therefore
$a^{i_{1}}b^{j_{1}}a^{i_{2}}b^{j_{2}}\cdots
a^{i_{t}}b^{j_{t}}ca^{n-k_{1}}b^{n-k_{2}}\not\in Dc$. Hence, the ‘$c$’ cannot
be deleted by the the automaton before deleting all $a$’s and $b$’s.

Therefore, the automaton cannot go to the configuration $a^{n}b^{n-j}q$ or
$a^{n}b^{n}q$ from the configuration $q_{0}a^{n}b^{n}c$.

If the automaton goes to the configuration $a^{n}qb^{n-j}c$. The automaton
cannot delete all $b$’s starting from the configuration $a^{n}qb^{n-j}c$
because in order to delete all $b$’s it will have to loop and in that case
mismatch in the indices of $`a$’ and $`b$’ can be created. Therefore, the
automaton will use the following sequence of transitions to accept the word
$a^{n}b^{n}c$: $q_{0}a^{n}b^{n}c$ $\curvearrowright$ $a^{n}qb^{n-j}c$
$\curvearrowright^{*}$ $a^{n}q^{\prime}b^{n-j-j^{\prime}}c$ $\curvearrowright$
$q^{\prime}a^{n}b^{n-j-j^{\prime}}c$ $\curvearrowright^{*}$ $q_{f}$, where
$j^{\prime}\geq 0$, $q^{\prime}\in Q$ and $b^{t}\not\in\Sigma_{q^{\prime}}$
for $1\leq t\leq n-j-j^{\prime}$, $b^{t}c\not\in\Sigma_{q^{\prime}}$ for
$0\leq t\leq n-j-j^{\prime}$. But, then the following sequence of transitions
is also possible: $q_{0}b^{j+j^{\prime}}a^{n}b^{n-j-j^{\prime}}c$
$\curvearrowright$ $qb^{j^{\prime}}a^{n}b^{n-j-j^{\prime}}c$
$\curvearrowright^{*}$ $q^{\prime}a^{n}b^{n-j-j^{\prime}}c$
$\curvearrowright^{*}$ $q_{f}$. Hence, the word
$b^{j+j^{\prime}}a^{n}b^{n-j-j^{\prime}}c$ $\in L(\mathcal{A)}$ but
$b^{j+j^{\prime}}a^{n}b^{n-j-j^{\prime}}c$ $\not\in Dc$. Hence, the automaton
cannot go to the configuration $a^{n}qb^{n-j}c$ from the configuration
$q_{0}a^{n}b^{n}c$.

If the automaton goes to the configuration $a^{n-i}qb^{n-j}c$ from the
configuration $q_{0}a^{n}b^{n}c$, then $q_{0}a^{n}b^{n}c$ $\curvearrowright$
$a^{n-i}qb^{n-j}c$ $\curvearrowright^{*}$ $a^{n-i}q^{(1)}b^{n-j-j_{1}}c$,
where $q^{(1)}\in Q,j_{1}\geq 0$. Since ‘$c$’ cannot be deleted before
deleting all $a$’s and $b$’s, therefore $q_{0}a^{n}b^{n}c$ $\curvearrowright$
$a^{n-i}qb^{n-j}c$ $\curvearrowright^{*}$ $a^{n-i}q^{(1)}b^{n-j-j_{1}}c$
$\curvearrowright$ $q^{(1)}a^{n-i}b^{n-j-j_{1}}c$, where
$b^{t}\not\in\Sigma_{q^{(1)}}$ for $1\leq t\leq n-j-j_{1}$ and
$b^{t}c\not\in\Sigma_{q^{(1)}}$ for $0\leq t\leq n-j-j_{1}$. From the
configuration $q^{(1)}a^{n-i}b^{n-j-j_{1}}c$ the automaton can go to the
configuration $q^{(2)}a^{n-i-i_{1}}b^{n-j-j_{1}}c$, where $q^{(2)}\in
Q,i_{1}\geq 1$ or $a^{n-i-i_{1}}q^{(2)}b^{n-j-j_{1}-j_{2}}c$, where
$q^{(2)}\in Q$, $i_{1},j_{2}\geq 1$, $a^{t}\not\in\Sigma_{q^{(1)}}$ for $1\leq
t\leq n-i-i_{1}$. Hence, we have the following two sequence of transitions:

$1.$ $q_{0}a^{n}b^{n}c$ $\curvearrowright$ $a^{n-i}qb^{n-j}c$
$\curvearrowright^{*}$ $a^{n-i}q^{(1)}b^{n-j-j_{1}}c$ $\curvearrowright$
$q^{(1)}a^{n-i}b^{n-j-j_{1}}c$ $\curvearrowright$
$q^{(2)}a^{n-i-i_{1}}b^{n-j-j_{1}}c$ $\curvearrowright^{*}$ $q_{f}$. But, then
the following sequence is also possible: $q_{0}a^{n-i_{1}}b^{n}ca^{i_{1}}$
$\curvearrowright$ $a^{n-i_{1}-i}qb^{n-j}ca^{i_{1}}$ $\curvearrowright^{*}$
$a^{n-i_{1}-i}q^{(1)}b^{n-j-j_{1}}ca^{i_{1}}$ $\curvearrowright$
$a^{n-i_{1}-i}b^{n-j-j_{1}}cq^{(2)}$ $\curvearrowright$ $q^{(2)}a^{n-i-
i_{1}}b^{n-j-j_{1}}c$ $\curvearrowright^{*}$ $q_{f}$. Hence, the word
$a^{n-i_{1}}b^{n}ca^{i_{1}}$ $\in$ $L(\mathcal{A})$ but
$a^{n-i_{1}}b^{n}ca^{i_{1}}$ $\not\in$ $Dc$.

$2.$ $q_{0}a^{n}b^{n}c$ $\curvearrowright$ $a^{n-i}qb^{n-j}c$
$\curvearrowright^{*}$ $a^{n-i}q^{(1)}b^{n-j-j_{1}}c$ $\curvearrowright$
$q^{(1)}a^{n-i}b^{n-j-j_{1}}c$ $\curvearrowright$
$a^{n-i-i_{1}}q^{(2)}b^{n-j-j_{1}-j_{2}}c$ $\curvearrowright^{*}$ $a^{n-i-
i_{1}}q^{(3)}b^{n-j-j_{1}-j_{2}-j_{3}}c$ $\curvearrowright$ $q^{(3)}a^{n-i-
i_{1}}b^{n-j-j_{1}-j_{2}-j_{3}}c$, where $j_{3}\geq 0,q^{(3)}\in Q$,
$b^{t}\not\in\Sigma_{q^{(3)}}$ for $1\leq t\leq n-j-j_{1}-j_{2}-j_{3}$ and
$b^{t}c\not\in\Sigma_{q^{(3)}}$ for $0\leq t\leq n-j-j_{1}-j_{2}-j_{3}$. If
$q^{(3)}$ deletes only $a$’s, then this case becomes similar to case $1.$ and
hence, there exists a word $w\in L(\mathcal{A})$ but $w\not\in Dc$. Therefore,
$q^{(3)}$ will have to delete $a^{i_{2}}b^{j_{4}}$, where $i_{2},j_{4}\geq 1$
and hence, $q_{0}a^{n}b^{n}c$ $\curvearrowright$ $a^{n-i}qb^{n-j}c$
$\curvearrowright^{*}$ $a^{n-i}q^{(1)}b^{n-j-j_{1}}c$ $\curvearrowright$
$q^{(1)}a^{n-i}b^{n-j-j_{1}}c$ $\curvearrowright$
$a^{n-i-i_{1}}q^{(2)}b^{n-j-j_{1}-j_{2}}c$ $\curvearrowright^{*}$ $a^{n-i-
i_{1}}q^{(3)}b^{n-j-j_{1}-j_{2}-j_{3}}c$ $\curvearrowright$ $q^{(3)}a^{n-i-
i_{1}}b^{n-j-j_{1}-j_{2}-j_{3}}c$ $\curvearrowright$ $a^{n-i-
i_{1}-i_{2}}q^{(4)}b^{n-j-j_{1}-j_{2}-j_{3}-j_{4}}c$ $\curvearrowright^{*}$
$a^{n-i-i_{1}-i_{2}}q^{(5)}b^{n-j-j_{1}-j_{2}-j_{3}-j_{4}-j_{5}}c$
$\curvearrowright$
$q^{(5)}a^{n-i-i_{1}-i_{2}}b^{n-j-j_{1}-j_{2}-j_{3}-j_{4}-j_{5}}c$
$\curvearrowright^{*}$ $q_{f}$, where $j_{5}\geq 0,q^{(4)},q^{(5)}\in Q$,
$b^{t}\not\in\Sigma_{q^{(5)}}$ for $1\leq t\leq n-j-
j_{1}-j_{2}-j_{3}-j_{4}-j_{5}$ and $b^{t}c\not\in\Sigma_{q^{(5)}}$ for $0\leq
t\leq n-j-j_{1}-j_{2}-j_{3}-j_{4}-j_{5}$. But, then the following sequence of
transition is also possible:
$q_{0}a^{n-i_{1}-i_{2}}b^{n-j_{2}-j_{3}-j_{4}-j_{5}}a^{i_{1}}b^{j_{2}+j_{3}}ca^{i_{2}}b^{j_{4}+j_{5}}$
$\curvearrowright$
$a^{n-i_{1}-i_{2}-i}qb^{n-j_{2}-j_{3}-j_{4}-j_{5}-j}a^{i_{1}}b^{j_{2}+j_{3}}ca^{i_{2}}b^{j_{4}+j_{5}}$
$\curvearrowright^{*}$
$a^{n-i_{1}-i_{2}-i}q^{(1)}b^{n-j_{2}-j_{3}-j_{4}-j_{5}-j-j_{1}}a^{i_{1}}b^{j_{2}+j_{3}}ca^{i_{2}}b^{j_{4}+j_{5}}$
$\curvearrowright$
$a^{n-i_{1}-i_{2}-i}b^{n-j_{2}-j_{3}-j_{4}-j_{5}-j-j_{1}}q^{(2)}b^{j_{3}}ca^{i_{2}}b^{j_{4}+j_{5}}$
$\curvearrowright^{*}$
$a^{n-i_{1}-i_{2}-i}b^{n-j_{2}-j_{3}-j_{4}-j_{5}-j-j_{1}}q^{(3)}ca^{i_{2}}b^{j_{4}+j_{5}}$
$\curvearrowright$
$a^{n-i_{1}-i_{2}-i}b^{n-j_{2}-j_{3}-j_{4}-j_{5}-j-j_{1}}cq^{(4)}b^{j_{5}}$
$\curvearrowright^{*}$
$a^{n-i_{1}-i_{2}-i}b^{n-j_{2}-j_{3}-j_{4}-j_{5}-j-j_{1}}cq^{(5)}$
$\curvearrowright$
$q^{(5)}a^{n-i_{1}-i_{2}-i}b^{n-j_{2}-j_{3}-j_{4}-j_{5}-j-j_{1}}c$
$\curvearrowright^{*}$ $q_{f}$.
Hence, the word
$w=a^{n-i_{1}-i_{2}}b^{n-j_{2}-j_{3}-j_{4}-j_{5}}a^{i_{1}}b^{j_{2}+j_{3}}ca^{i_{2}}b^{j_{4}+j_{5}}$
$\in$ $L(\mathcal{A})$ but $w\not\in Dc$.

If the automaton goes to the configuration $qa^{n-i}b^{n}c$ from the
configuration $q_{0}a^{n}b^{n}c$. The automaton cannot delete all $a$’s from
the configuration $qa^{n-i}b^{n}c$ otherwise the automation will have to loop
and in this case mismatch in the indices of ‘$a$’ and ‘$b$’ can be created.
Hence, the automaton will make the following sequence of transitions:
$q_{0}a^{n}b^{n}c$ $\curvearrowright$ $qa^{n-i}b^{n}c$ $\curvearrowright^{*}$
$q^{(1)}a^{n-i-i_{1}}b^{n}c$ $\curvearrowright$
$a^{n-i-i_{1}-i_{2}}q^{(2)}b^{n-j_{1}}c$ $\curvearrowright^{*}$ $a^{n-i-
i_{1}-i_{2}}q^{(3)}b^{n-j_{1}-j_{2}}c$ $\curvearrowright$ $q^{(3)}a^{n-i-
i_{1}-i_{2}}b^{n-j_{1}-j_{2}}c$, where $i_{1},i_{2},j_{2}\geq 0$, $j_{1}\geq
1$, $b^{t}\not\in\Sigma_{q^{(3)}}$ for $1\leq t\leq n-j_{1}-j_{2}$ and
$b^{t}c\not\in\Sigma_{q^{(3)}}$ for $0\leq t\leq n-j_{1}-j_{2}$. From the
configuration $q^{(3)}a^{n-i-i_{1}-i_{2}}b^{n-j_{1}-j_{2}}c$ the automaton can
go to the configuration $q^{(4)}a^{n-i-i_{1}-i_{2}-i_{3}}b^{n-j_{1}-j_{2}}c$,
where $q^{(4)}\in Q,i_{3}\geq 1$ or $a^{n-i-
i_{1}-i_{2}-i_{3}}q^{(4)}b^{n-j_{1}-j_{2}-j_{3}}c$, where $q^{(4)}\in Q$,
$i_{3},j_{3}\geq 1$, $a^{t}\not\in\Sigma_{q^{(3)}}$ for $1\leq t\leq n-i-
i_{1}-i_{2}-i_{3}$. These cases are similar to the above cases 1. and 2.
Hence, there will be word $w\in\Sigma^{*}$ such that $w$ $\in$
$L(\mathcal{A})$ but $w\not\in$ $Dc$.

Hence, the language $Dc\not\in\bf{GRLOWJ}$.

From Example 6 and Lemma 6, we conclude $\bf{GLLOWJ\not\subseteq GRLOWJ}$.
Similarly, it can be shown that $\bf{GRLOWJ\not\subseteq GLLOWJ}$. Hence, we
have the following result.

###### Proposition 2

The language classes $\bf{GRLOWJ}$ and $\bf{GLLOWJ}$ are incomparable.

##  6 GLOWJFA and Chomsky hierarchy

In this section, we compare the language classes $\bf{GRLOWJ}$ with the
language classes of Chomsky hierarchy. $\bf{REG}$, $\bf{CF}$ and $\bf{CS}$
represent the class of regular languages, context free languages and context
sensitive languages, respectively. We show that the language class $\bf{REG}$
is a proper subset of the class $\bf{GRLOWJ}$, the language classes $\bf{CF}$
and $\bf{GRLOWJ}$ are incomparable and the class $\bf{GRLOWJ}$ is a proper
subset of the class $\bf{CS}$. Same results hold true for the class
$\bf{GLLOWJ}$.

We recall some results from [5].

###### Lemma 7

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

###### Lemma 8

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

From Lemma 7 and 1, we have the following result.

###### Proposition 3

$\bf{REG\subset GRLOWJ}$.

###### Proposition 4

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

###### Proof

Being concatenation of two context-free languages, the language $Dc$ $\in$
$\bf{CF}$ but from Lemma 6, $Dc\not\in$ $\bf{GRLOWJ}$. Hence, $\bf{CF}$
$\not\subseteq$ $\bf{GRLOWJ}$. From Lemma 8, we conclude
$\bf{ROWJ\not\subseteq CF}$ and hence, from Lemma 1, we have $\bf{GRLOWJ}$
$\not\subseteq$ $\bf{CF}$.

###### Proposition 5

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

###### Proof

For a given $\it{GRLOWJFA}$, we give a sketch of the construction of an
equivalent Linear bounded automaton($LBA$).

  1. 1.

For a given word $w=w_{1}w_{2}\cdots w_{n}$ from the input alphabet $\Sigma$,
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}$.

  2. 2.

Suppose the $LBA$ is in a state $p$. For a rule $(p,x=x_{1}x_{2}\cdots
x_{i},q)$ of $\it{GRLOWJFA}$, the $LBA$ search for nearest subword $x$ of the
word available between the tape head and the right end marker $\\#$. By
nearest subword we mean that suppose tape head and the right end marker
contains $uxv$, then $x$ is not a subword of $u$ 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$.

  3. 2.a.

If there is a subword $x$, then the $LBA$ marks it as $X_{1}X_{2}\cdots
X_{i}$.

  4. 2.a.a

If there are symbols from $\Sigma$ to the right of $X_{i}$, then the tape head
is at the first symbol right to $X_{i}$ and the $LBA$ goes to the state $q$.

  5. 2.a.b.

If there are no symbols from $\Sigma$ to the right of $X_{i}$, then the $LBA$
concatenates all the subwords of $w$ that are not marked in capitals such as
$X_{1}X_{2}\cdots X_{i}$. Without loss of generality, we assume the input
alphabet contains symbol that are in small letters such as $w_{1},w_{2}$ etc.
and for marking it uses symbols that are in capital such as $W_{1},W_{2}$ etc.

  6. 2.b.

If there is no $x$, then the $LBA$ concatenates all the subwords of $w$ that
are not marked in capitals such as $X_{1}X_{2}\cdots X_{i}$.

  7. 2.c.

Suppose we get a new word $w^{\prime}$ from $\Sigma^{*}$, after concatenation.
Then, the $LBA$ adjust the end markers such that there is only $w^{\prime}$
between end markers, i.e. $\$w^{\prime}\\#$. If the $LBA$ uses 2.a. and
2.a.b., then it goes to the state $q$ and if it uses 2.b., then it stays in
the state $p$.

  8. 2.c.a.

If $w^{\prime}=\lambda$, then the $LBA$ accepts the given word $w$ if the
$LBA$ is one of the final states of $\it{GRLOWJFA}$.

  9. 2.c.b.

If $w^{\prime}\neq\lambda$, then the tape head of the $LBA$ is at the first
symbol of $w^{\prime}$. And it repeats the above steps.

Hence, we conclude that $\bf{GRLOWJ\subseteq CS}$. But from Lemma 6, we have
$Dc\not\in$ $\bf{GRLOWJ}$. Hence, $\bf{GRLOWJ\subset CS}$. Similarly, it can
be shown that $\bf{GLLOWJ\subset CS}$.

$\bf{CS}$$\bf{CF}$$\bf{REG}$$\bf{GLLOWJ}$$\bf{GRLOWJ}$$\bf{ROWJ}$$\bf{LOWJ}$
Figure 1: GLOWJFA language family and Chomsky hierarchy.

The results, related to comparability of language classes of language families
$\it{GRLOWJFA/GLLOWJFA}$ and Chomsky hierarchy, presented in this and above
sections are depicted in Fig 1. The arrows represent that one language class
is a proper subset of other. If two language classes are not joined by an
arrow or a sequence of arrows, then they are incomparable.

##  7 Closure Properties

In this section, we explore closure properties of the language class
$\bf{GRLOWJ}$. We show that the class $\bf{GRLOWJ}$ is not closed under
intersection, concatenation and reversal. Same results hold true for the class
$\bf{GLLOWJ}$.

###### Note 2

The Dyck language is in the language class $\bf{GRLOWJ}$. An automaton can be
constructed similar to the automaton of Example 5.

Now, we give a lemma which we will use to show that the class $\bf{GRLOWJ}$ is
not closed under intersection.

###### Lemma 9

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

###### Proof

If $L=\\{a^{n}b^{n}~{}|~{}n\geq 0\\}$ $\in$ $\bf{GRLOWJ}$, then there exists a
$\it{GRLOWJFA}$, $\mathcal{A}=(\Sigma,Q,q_{0},F,R)$ such that
$L(\mathcal{A})=L.$ Let $l=|Q|$ and $k$ $=$ $max\\{|w|~{}|~{}(p,w,q)$ $\in
R\\}$. Consider a natural number $t>lk$. Clearly, $a^{t}b^{t}\in
L=L(\mathcal{A})$. Then, there exists a sequence of transitions such that
$q_{0}a^{t}b^{t}\curvearrowright^{*}q_{f}$, where $q_{f}\in F$.

###### Case 1

The automaton cannot delete all $a$’s starting from the configuration
$q_{0}a^{t}b^{t}$ before deleting a ‘$b$’. Because in this case the automaton
will have to loop to delete all $a$’s and the same loop can be used multiple
times to delete more $a$’s than $b$’s and then there would be a mismatch in
the indices of ‘$a$’ and ‘$b$’.

###### Case 2

Since, the automaton cannot delete all $a$’s starting from the configuration
$q_{0}a^{t}b^{t}$ before reading a ‘$b$’, let the automaton deletes $t_{1}$
$a$’s before deleting a ‘$b$’, where $0\leq t_{1}<t$. In this case, we have
$q_{0}a^{t}b^{t}\curvearrowright^{*}q^{\prime}a^{t-t_{1}}b^{t}\curvearrowright^{*}q_{f}$,
where $q^{\prime}\in Q$. The automaton cannot delete all $b$’s starting from
the configuration $q^{\prime}a^{t-t_{1}}b^{t}$, same argument would be given
as given in case 1. So, let
$q_{0}a^{t}b^{t}\curvearrowright^{*}q^{\prime}a^{t-t_{1}}b^{t}\curvearrowright^{*}a^{t-t_{1}-t_{2}}q^{\prime\prime}b^{t-t_{3}}\curvearrowright
q^{\prime\prime}a^{t-t_{1}-t_{2}}b^{t-t_{3}}\curvearrowright^{*}q_{f}$, where
$q^{\prime\prime}\in Q$, $0\leq t_{2}<k$, $1\leq t_{3}<t$ and
$b^{i}\not\in\Sigma_{q^{\prime\prime}}$ for $1\leq i\leq t-t_{3}$. But in this
case, the automaton will also delete the word
$a^{t_{1}+t_{2}}b^{t_{3}}a^{t-t_{1}-t_{2}}b^{t-t_{3}}$ using the following
sequence of transitions:
$q_{0}a^{t_{1}+t_{2}}b^{t_{3}}a^{t-t_{1}-t_{2}}b^{t-t_{3}}\curvearrowright^{*}q^{\prime}a^{t_{2}}b^{t_{3}}a^{t-t_{1}-t_{2}}b^{t-t_{3}}$
$\curvearrowright^{*}q^{\prime\prime}a^{t-t_{1}-t_{2}}b^{t-t_{3}}$
$\curvearrowright^{*}$ $q_{f}$ and hence
$a^{t_{1}+t_{2}}b^{t_{3}}a^{t-t_{1}-t_{2}}b^{t-t_{3}}$ $\in$ $L(\mathcal{A})$.
But the word $a^{t_{1}+t_{2}}b^{t_{3}}a^{t-t_{1}-t_{2}}b^{t-t_{3}}\not\in L$,
therefore this case is also not possible.

###### Case 3

From the previous two cases, we conclude the automaton cannot delete any ‘$a$’
from the configuration $q_{0}a^{t}b^{t}$. So, the only remaining case is that
the automaton will delete $b$’s from the configuration $q_{0}a^{t}b^{t}$
without deleting any ‘$a$’. Using a similar argument as in case 1, one can
show that the automaton cannot delete all $b$’s starting from the
configuration $q_{0}a^{t}b^{t}$ before deleting an ‘$a$’. So, let the
automaton deletes first $t_{1}$ $b$’s with $1\leq t_{1}<t$, i.e.,
$q_{0}a^{t}b^{t}\curvearrowright^{*}a^{t}q^{\prime}b^{t-t_{1}}\curvearrowright
q^{\prime}a^{t}b^{t-t_{1}}\curvearrowright^{*}q_{f}$, where $q^{\prime}\in Q$
and $b^{i}\not\in\Sigma_{q^{\prime}}$ for $1\leq i\leq t-t_{1}$. But in this
case, the automaton will also delete the word $b^{t_{1}}a^{t}b^{t-t_{1}}$
using the sequence of transitions:
$q_{0}b^{t_{1}}a^{t}b^{t-t_{1}}\curvearrowright^{*}q^{\prime}a^{t}b^{t-t_{1}}\curvearrowright^{*}q_{f}$
and hence, $b^{t_{1}}a^{t}b^{t-t_{1}}\in L(\mathcal{A})$. But,
$b^{t_{1}}a^{t}b^{t-t_{1}}\not\in L$, therefore this case is also not
possible.

From the above three cases, we conclude $\\{a^{n}b^{n}~{}|~{}n\geq
0\\}\not\in\bf{GRLOWJ}.$

###### Proposition 6

$\bf{GRLOWJ}$ is not closed under

  * 1.

intersection,

  * 2.

concatenation,

  * 3.

reversal.

###### Proof

From Proposition 3, we have $\bf{REG\subset GRLOWJ}$. Hence, the language
$a^{*}b^{*}$ $\in$ $\bf{GRLOWJ}$. Also, from Note 2, the Dyck language
$D\in\bf{GRLOWJ}$. But, $a^{*}b^{*}\cap D=\\{a^{n}b^{n}~{}|~{}n\geq
0\\}\not\in\bf{GRLOWJ}$, by Lemma 9. Hence, $\bf{GRLOWJ}$ is not closed under
intersection.

From Lemma 6, we have $Dc$ $\not\in$ $\bf{GRLOWJ}$, but $D,\\{c\\}$ $\in$
$\bf{GRLOWJ}$. Hence, $\bf{GRLOWJ}$ is not closed under concatenation.

An $\it{GRLOWJFA}$ automaton, similar to that of Example 6, can be constructed
that accepts the language $cD$ and hence, $cD\in\bf{GRLOWJ}$. We have
$(cD)^{R}=D^{R}c$ and $D^{R}$ is the language obtained by interchanging $a$
and $b$ in $D$. Hence, it can be proved, similar to Lemma 6, that
$D^{R}c\not\in\bf{GRLOWJ}$. Hence, $\bf{GRLOWJ}$ is not closed under reversal.

##  8 Conclusion

In this paper, we propose a general one-way jumping automata to understand the
discontinuous reading of an input in parts of its substrings. We have defined
a new jumping transition model of computation which is names as generalized
linear one-way jumping finite automata. It is a generalization of the model
one-way jumping finite automata in deleting words, i.e., unlike $\it{OWJFA}$,
the new generalized model can delete words during computation. We have shown
that this new generalization is more powerful than $\it{OWJFA}$. The variants
$\it{GRLOWJFA}$ and $\it{GLLOWJFA}$ are compared for their computational
power. The language class of $\it{GRLOWJFA}$ has been compared with the
language classes of Chomsky hierarchy. Our study on the power of the new
generalized model is exhaustive. Closure properties of the language class of
$\it{GRLOWJFA}$ have been explored. The study is theoretical in nature.

## 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] Fernau, H., Paramasivan, M., Schmid, M. L., Vorel, V.: Characterization and complexity results on jumping finite automata. Theoretical Computer Science 679, 31–52 (2017)
  * [8] 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)
  * [9] 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)
  * [10] 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)
  * [11] Krithivasan, K., Rama, R.: Introduction to Formal Languages, Automata Theory and Computation. Pearson, India (2009)
  * [12] Mahalingam, K., Mishra, U. K., Raghavan, R.: Watson-Crick Jumping Finite Automata. International Journal of Foundations of Computer Science 31(7), 891–913 (2020)
  * [13] Meduna, A., Zemek, P.: Jumping Finite Automata. International Journal of Foundations of Computer Science 23(7), 1555–1578 (2012)
  * [14] Vorel, V: On basic properties of jumping finite automata. International Journal of Foundations of Computer Science 29(1), 1–15 (2018)
  * [15] Vorel, V.: Two Results on Discontinuous Input Processing. Proc. of LNCS 9777, pp. 205–216, Springer, Cham (2016)


# The Braess’s Paradox in Dynamic Traffic

Dingyi Zhuang1∗, Yuzhu Huang1∗, Vindula Jayawardana23, Jinhua Zhao1, Dajiang
Suo24, Cathy Wu12 *Dingyi Zhuang and Yuzhu Huang have contributed equally.1
Department of Civil and Environmental Engineering, Massachusetts Institute of
Technology<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Laboratory for
Information and Decision Systems, Massachusetts Institute of Technology
<EMAIL_ADDRESS><EMAIL_ADDRESS>Department of Electrical Engineering and
Computer Science, Massachusetts Institute of Technology4 Department of
Mechanical Engineering, Massachusetts Institute of Technology<EMAIL_ADDRESS>
###### Abstract

The Braess’s Paradox (BP) is the observation that adding one or more roads to
the existing road network will counter-intuitively increase traffic congestion
and slow down the overall traffic flow. Previously, the existence of the BP is
modeled using the static traffic assignment model, which solves for the user
equilibrium subject to network flow conservation to find the equilibrium state
and distributes all vehicles instantaneously. Such approach neglects the
dynamic nature of real-world traffic, including vehicle behaviors and the
interaction between vehicles and the infrastructure. As such, this article
proposes a dynamic traffic network model and empirically validates the
existence of the BP under dynamic traffic. In particular, we use
microsimulation environment to study the impacts of an added path on a grid
network. We explore how the network flow, vehicle travel time, and network
capacity respond, as well as when the BP will occur.

##  I Introduction

###  I-A Background

Dietrich Braess, a German mathematician, discovered that adding a new road to
an existing road network, although increasing capacity, could actually
exacerbate overall congestion. He argued that if each vehicle is making self-
interested routing decisions, the shortest path would be frequently selected,
which will lead to impedance on a shortcut and slow down overall traffic speed
in the end [1, 2]. A classical approach to formulating this problem usually
involves using road cost function related to the number of vehicles on each
road to solve for the traffic equilibrium equations and demonstrate the BP
[3].

To see how to solve the equilibrium for the BP, consider a classical static
traffic assignment example. As shown in Fig. 1a, the four-edge diamond-shaped
network, suppose there are six cars that whish to travel from point A to point
B via routes ACB or ADB. The travel cost (usually means travel time)
associated with each road segment is marked beside the edge, where $N$ is the
number of vehicles in the same road segment. Intuitively, that means that if
there are more vehicles in the same road, traffic tends to congest and travel
time is consequently larger. Since the cost function of each route is the same
for routes ACB and ADB (if CD is not connected), the demand is evenly
distributed because using one route is just as good as using the other. The
user equilibrium reaches when three cars use route ACB and the other three
choose ADB with travel cost $C_{ACB}=30+53=83=C_{ADB}$. Now, suppose a new
shortcut CD connecting the two routes is constructed, as shown in Fig. 1b. The
four-edge network is reformed to the five-edge one. Vehicles will shift to the
shortcut until a new user equilibrium is reached when
$C_{ACDB}=C_{ACB}=C_{ADB}$, when two vehicles are assigned to each route and
the travel cost is 92 for each route, larger than the previous case without
the shortcut. From this example, we could see that adding a new road to the
network could in fact increase the travel time for everybody, which is the
Braess’s Paradox.

ACDB10NN+50N+5010N (a) The basic four-edge network

ACDBN+1010NN+50N+5010N (b) The five-edge network

Figure 1: The classical Braess’s Paradox example with static traffic
assignment, where $N$ represents the number of vehicles on the edge. If
vehicles reach equilibrium, adding a path (i.e. connection CD in b) will make
the traffic worse.

###  I-B Motivation

The application of static traffic assignment on the four-edge and five-edge
networks is widely discussed in previous literature on Braess’s Paradox [4,
nagurney2010negation, 5]. These works analyze the BP from the network science
perspective. For the convenience of optimization, the vehicle behaviors and
the routing strategy are usually simplified. Vehicles are homogeneous and
their route choices are assigned instantaneously after solving the flow
conservation and user equilibrium. Wolf et al. [6] proposed the TASEP
framework to study the BP, but only discuss the random and fixed routing of
vehicles. The lack of consideration of vehicle behaviors makes the results
less empirical in real-world scenario. Colombo, Rinaldo M., Helge Holden, and
Francesca Marcellini modeled the BP from the microscopic vehicular traffic,
but still requires a lot of constraints and assumptions to solve the Nash
equilibrium [7]. Recently, Belov, Aleksandr, et al. [8] studied the price of
anarchy from the Braess network using the microsimulation. The price of
anarchy is the index between the user equilibrium and the system optimal. They
have also discussed the network parameters and their impacts on the price of
anarchy and related it with the BP. To be differentiated, our work has
designed a estimated travel time based routing strategy and discuss directly
the added path’s impact on the network and the BP.

Moreover, under a static traffic assignment model, another crucial hidden
assumption is that vehicles are assigned instantaneously. This assumption is
impractical as in the real world, vehicle behaviors are dynamically changing
with the surrounding environment rather than instantaneously determined.
Moreover, the junction effects and the interactions of human drivers are not
fully studied. Therefore, we wish to examine whether BP exists in dynamic
setting. Our approach is to mimic the vehicle behaviors and analyze the
network performance from the microscopic perspective. In this paper, we use
the Flow project and SUMO [9, 10] as the microsimulation environment to design
minimalistic scenarios and explore the characteristics of BP in the dynamic
setting. Our main contributions include two parts:

  * •

We extend the static traffic assignment problem formulation into the
microsimulation context to model the BP

  * •

Under dynamic traffic, we empirically explore the impacts of an added path on
the network flow, network capacity, and vehicle travel time, and confirm the
existence of BP in dynamic traffic

To our best knowledge, we are the first to analyze the BP from the dynamic
microsimulation setting.

##  II A Dynamic Braess’s Paradox Model

###  II-A Preliminaries

Fig. 1 example shows the idea of static traffic assignment model. We briefly
review its formulation and relevant extension in the dynamic traffic
assignment context, before extending it to a dynamic microsimulation context
[5, nagurney2010negation]. It assumes that the traffic network contains a set
$\mathcal{S}$ of origin-destination pairs with $n_{\mathcal{S}}$ elements, the
edge set $\mathcal{L}$ and the path route set $\mathcal{P}$ [5,
nagurney2010negation]. Shown in Fig. 1 example, each route $p\in\mathcal{P}$
has cost function $C_{p}$, whose mathematical formulation of the user
equilibrium is given as [11, 12, 13, 14]:

$\begin{aligned} C_{p}(x_{p}^{*}(t))&=\lambda_{s}(t),\text{ if
}x_{p}^{*}(t)>0\\\ C_{p}(x_{p}^{*}(t))&\geq\lambda_{s}(t),\text{ if
}x_{p}^{*}(t)=0\end{aligned},$ (1)

where $C_{p}(\cdot)$ defines the user (travel) cost on path $p$,
$\lambda_{s}(t)$ is the minimal path costs at time $t$, and $x_{p}^{*}(t)$ is
the path flow assignment that fulfills flow conservation. In static
assignment, $C_{p}$ is fixed while in dynamic assignment, $C_{p}(t)$ varies at
different time. To help keep the notation consistency when it is extended to
the dynamic traffic assignment, we keep all the variable dependent on time.
The flow conservation is in the form as:

$\begin{aligned}
f_{e}(t)=\sum_{p\in\mathcal{P}}x_{p}(t)\delta_{ep}\end{aligned},$ (2)

where $f_{e}(t)$ is the flow of the edge $e$ at time $t$, $x_{p}(t)$ is the
flow on route $p$, and $\delta_{ep}$ is a binary indicator for whether edge
$e$ is included in route $p$. The traffic demand $d_{s}(t)$ at time $t$ must
also follow flow conservation constraints:

$\begin{aligned} \sum_{p\in\mathcal{P}}x_{p}(t)=d_{s}(t),\quad\forall
s\in\mathcal{S},\forall t\end{aligned}.$ (3)

Similarly, denote the user cost on the edge $e$ as $C_{e}(\cdot)$. The user
costs on paths are defined as:

$\begin{aligned}
C_{p}(t)=\sum_{a\in\mathcal{L}}C_{e}(t)\delta_{ep},\quad\forall
p\in\mathcal{P},\forall t\end{aligned}.$ (4)

Dynamic traffic assignment takes as $C_{p}(t),C_{e}(t),d_{s}(t)$ as inputs and
distributes vehicles by computing the flow conservation, minimizing each
user’s (travel) costs $\sum_{p\in\mathcal{P}}C_{p}(t)$, and ensuring user
travel costs reach equilibrium at every time step. As shown in the Fig. 1
example, $\sum_{p\in\mathcal{P}}C_{p}$ is also used to show the existence of
Braess’s Paradox in the static setting. The design of $C_{p}$ is tricky and
usually simplified to depend on only the flow on the edge. Solving the user
equilibrium takes longer when the traffic network size is large or when
simplifying assumptions are relaxed. We try to replace it with dynamic
microsimulation, where we can capture the microscopic vehicle behaviors and
understand how equilibrium and the BP naturally form.

###  II-B Problem Formulation

In order to mimic the real-world driving behaviors, we take a microsimulation
perspective. We wish to replace the flow conservation and user equilibrium
optimization with the designed routing strategy for each vehicle. Denote the
driver set $\mathcal{U}=\\{d_{s}(t)\\}$ that contains the demand at time $t$.
When choosing the route, we consider each vehicle $u\in\mathcal{U}$ has
potential travel cost function $C_{u}$ correlated to designed function
$g(\cdot)$ of route flow, travel time, edge information:

$C_{u}(t)=g(x_{p}(t),e,p),\quad\forall e\in\mathcal{L},\forall
p\in\mathcal{P}.$ (5)

We formulate the microscopic traffic assignment model by equalizing
$\sum_{u\in\mathcal{U}}C_{u}$ instead of $\sum_{p\in\mathcal{P}}C_{p}$ by
solving user equilibrium, and consider the existence of the BP under this more
realistic model. The introduction of $C_{u}$ provides us with the microscopic
leverage to discuss the important factors that will influence the vehicle
routing decisions, as well as the potential impacts on the whole network.

###  II-C Network Design

The classical diamond-shaped networks in Fig. 1 have some distinct
characteristics. Traffic enters the network from node A, and leaves at node B.
Before a new path is added, each route from node A to node B
(A$\rightarrow$C$\rightarrow$B, or A$\rightarrow$D$\rightarrow$B, shown in
Fig. 1a) has the same overall cost function; after the new path is added, the
third route (A$\rightarrow$C$\rightarrow$D$\rightarrow$B, shown in Fig. 1b)
has a different cost function that makes it more preferable than the original
routes.

To model this classical network under the microsimulation setting, we designed
a grid network that resembles the diamond network, as shown in Fig. 2. There
are a total of 6 intersections, all are controlled with all-way stops except
for intersection A. Arrows denote the directions of traffic flow. In the basic
design, shown in Fig. 2a, two routes are available, namely
A$\rightarrow$C$\rightarrow$M$\rightarrow$B and
A$\rightarrow$N$\rightarrow$D$\rightarrow$B. With an additional path added, as
shown in Fig. 2b, a third route A$\rightarrow$C$\rightarrow$D$\rightarrow$B
becomes available.

(a) Gird network with 2 routes (the baseline network/scenario).

(b) Grid network with an added path (the add-path network/scenario).

Figure 2: A 2-by-3 grid network resembling the classical diamond network.

###  II-D Cost Function $C_{u}$

Unlike the classical diamond network that has a pre-defined linear cost
function $C_{p}$ and $C_{e}$ assigned to each edge and route, the cost $C_{u}$
in a dynamic microsimulation setting is the real-time travel time for each
vehicle using the edge. When a vehicle is making the decision of which route
to take, it predicts the travel time it might experience on all possible
routes, and chooses the one that would result in the lowest travel time.

In a microsimulation environment, each vehicle operates with its own
acceleration/deceleration controller that determines the vehicle kinematics
conditioned on its surrounding traffic, for example, following the IDM model
that is described in Equation 6:

$s^{*}(v,\Delta v)=s_{0}+max[0,(vT+\frac{v\Delta v}{2\sqrt{ab}})],$ (6)

where the desired distance $s^{*}$ is the sum of minimum spacing $s_{0}$ and
the acceleration/braking distance that is determined by the current vehicle
speed $v$, desired headway $T$, relative speed $\Delta v$, maximum vehicle
acceleration $a$, and a comfortable braking deceleration $b$ [15].

In addition, each vehicle has its own routing controller that decides which
route to take based on the real-time prediction of travel times of all
potential routes. This is equivalent to the situation where all vehicles are
equipped with a traveler information system that could provide information on
estimated travel times (e.g. Google Maps).

There are many ways to estimate the real-time travel time of a route. The
method that is developed in this study is to use the position and speed of all
vehicles on an edge to estimate the travel time of each edge, then summing up
the travel times of all edges along the route to get the estimated time of the
route. The idea behind this method is to estimate the travel time on an edge
at each time step $t$ using only readily-available information (speed,
acceleration) without solving ODEs, providing each vehicle making the routing
decision an estimation of the current traffic condition on each route.

The travel time of an edge is estimated as illustrated in Fig. 3, where
$d_{0}$ is the distance between the beginning of the edge and vehicle $1$ (the
last vehicle on the edge), $d_{i}$ is the distance between vehicle $i$ and
$i+1$, and $d_{n}$ is the distance between vehicle $n$ (the front vehicle on
the edge) and the stop sign.

Figure 3: Example of a stop-controlled edge with n vehicles.

Therefore, the total length of the edge should be:

$L_{edge}=\sum_{i=0}^{n}d_{i},$ (7)

Estimated travel time of an edge:

$C_{e}(edge)=\begin{cases}\frac{L_{edge}}{v_{max}}&\text{if edge is empty}\\\
\sum_{i=0}^{n}t_{i}&\text{otherwise}\end{cases},$ (8)

where $v_{max}$ is the speed limit of the edge, $t_{0}$ is the estimated time
for a vehicle to travel from the beginning of the edge to the position of
vehicle $1$, $t_{i}$ is the estimated travel time for vehicle $i$ to travel to
the position of vehicle $i+1$ and $t_{n}$ is the estimated time for vehicle
$n$ to travel to the stop sign.

The decomposed travel times $t_{i}(i\in\\{0,1,...,n\\})$ as labeled in Fig. 3
are calculated using a simplified estimation method. Using vehicle kinematics
equations and assuming that vehicles have constant acceleration/deceleration
rates, the travel time between two points (e.g. ego vehicle and a target
vehicle) can be calculated as described in Algorithm 1.

Algorithm 1 Estimate Travel Time from Current Position to Target Position
($\bf{est\\_tt}$)

Given: speed at current position $v_{ego}$, current acceleration $a_{ego}$,
speed at target position $v_{target}$, maximum possible speed on edge
$v_{max}$, constant acceleration $a$, distance between current and target
positions $d$

1:if $a_{ego}$ is small then

2: assume that vehicle travels at constant speed until it has to accelerate to
reach $v_{target}$

3: $v_{final}\leftarrow$ realized speed at target position,

4: $=min(\sqrt{v_{ego}^{2}+2ad},v_{target})$

5: $d_{accel}\leftarrow$ acceleration distance
$|\frac{v_{ego}^{2}-v_{final}^{2}}{2*a}|$

6: $t_{est}\leftarrow$ time spent traveling at $v_{ego}$ \+ acceleration time

7: $=\frac{max(d-d_{accel},0)}{v_{ego}}+\frac{2*d_{accel}}{v_{ego}+v_{final}}$

8:else

9: assume that vehicle accelerates to an intermediate speed $v_{i}$ before it
has to decelerates to reach $v_{target}$

10: $v_{i}=min(\sqrt{\frac{1}{2}(2*a*d+v_{ego}^{2}+v_{target}^{2})},v_{max})$

11:
$d_{accel}=|\frac{v_{ego}^{2}-v_{i}^{2}}{2*a}|+|\frac{v_{i}^{2}-v_{target}^{2}}{2*a}|$

12:
$t_{est}=|\frac{v_{max}-v_{ego}}{a}|+|\frac{v_{max}-v_{target}}{a}|+\frac{max(d-d_{accel},0)}{v_{max}}$

13:end if

14:return $t_{est}$

The decomposed travel times $t_{i}$ can then be calculated as follows:

$t_{i}=\begin{cases}\mathbf{est\\_tt}(v_{start},a_{i},v_{1},v_{max},a,d_{i})&i=0\\\
\mathbf{est\\_tt}(v_{i},a_{i},v_{end},v_{max},a,d_{i})&i=n\\\
\mathbf{est\\_tt}(v_{i},a_{i},v_{i+1},v_{max},a,d_{i})&\text{otherwise}\\\
\end{cases},$ (9)

where $v_{i}$ is the traveling speeds of vehicle $i$; $a_{i}$ is the
acceleration of vehicle $i$; $v_{max}$ is the maximum possible speed on the
edge (Equation 10); $v_{start}$ is the assumed speed at the start of the edge,
so the speed limit of the edge is used; $v_{end}$ is the assumed speed at the
end of the edge, so $1m/s$ is used since edges are controlled with stop signs;
and $a$ is the absolute value of the assumed constant acceleration or
deceleration rate (a value of $3m/s^{2}$ is used).

The maximum possible speed is different on turning connections than on a
through connection or a straight road segment. The value of $v_{max}$ is
defined as follows:

$v_{max}=\begin{cases}10m/s&\text{left turn (LT)}\\\ 8m/s&\text{right turn
(RT)}\\\ \sqrt{2*a*length}&\text{through (TH)}\end{cases},\\\ $ (10)

and note that the maximum speed on left turns and right turns is determined
based on empirical observations.

Then, the cost function (travel time) of each of the 3 routes shown in Fig. 2b
is

$\begin{aligned} C&{}_{p,A\rightarrow C\rightarrow M\rightarrow B}(t)\\\
&=C_{e,TH}(t)+C_{e,a}(t)+C_{e,TH}(t)+C_{e,b}(t)\\\
&+C_{e,RT}(t)+C_{e,b}(t)+C_{e,LT}(t)\\\ C&{}_{p,A\rightarrow N\rightarrow
D\rightarrow B}(t)\\\ &=C_{e,RT}(t)+C_{e,b}(t)+C_{e,LT}(t)+C_{e,b}(t)\\\
&+C_{e,TH}(t)+C_{e,a}(t)+C_{e,TH}(t)\\\ C&{}_{p,A\rightarrow C\rightarrow
D\rightarrow B}(t)\\\ &=C_{e,TH}(t)+C_{e,a}(t)+C_{e,RT}(t)+C_{e,c}(t)\\\
&+C_{e,LT}(t)+C_{e,a}(t)+C_{e,TH}(t)\\\ \end{aligned}.$ (11)

Based on the estimated real-time travel time of each route, each user (driver)
will then select the the route that results in the lowest cost:

$\displaystyle\\{C_{p}(t)\\}=\\{$ $\displaystyle C_{p,A\rightarrow
C\rightarrow M\rightarrow B}(t),$ (12) $\displaystyle C_{p,A\rightarrow
N\rightarrow D\rightarrow B}(t),$ $\displaystyle C_{p,A\rightarrow
C\rightarrow D\rightarrow B}(t)\\}$ $\displaystyle\text{selected\\_route}(t)$
$\displaystyle=argmin\\{C_{p}(t)\\}$ (13) $\displaystyle C_{u}(t)$
$\displaystyle=min\\{C_{p}(t)\\}$

##  III Experiment Setup

In order to numerically characterize the existence of the BP in the
microsimulation environment, several parameters of the baseline and the added-
path scenarios are modified to compare the performance of the networks.

First, different inflow rates of vehicles entering the network from Node 1
(Fig. 2), at 50, 200, 400, 600, 800, 900 veh/hr, are used to simulate the
operations of the network with varying demand. Increasing the inflow rate
would result in increased density in the system, allowing us to understand how
adding a path to the network changes the ability of the system to process
demands.

Second, different speed limits combinations and edge lengths are used to
increase or decrease the level of attractiveness of the added path. In
addition to using different lengths (50, 200, 300 and 400 meters) of all edges
in the network, the speed limits of the edges other than the added path are
changed from 35 m/s to 15 and 10 m/s, while fixing the speed limit of the
added path ($C\rightarrow D$) to 35 m/s. The combination of edge length and
speed limit determine the maximum allowable speed on the edge given a maximum
acceleration. When the allowable speed on the added path is much higher than
those on the other edges, the added path becomes more attractive, thus
allowing us to explore how varying levels of attractiveness of the added path
could impact the onset of the BP.

Lastly, in addition to using only one inflow node at Node 1 in Fig. 4,
multiple inflow nodes (e.g. Node 2, 3, 5, and 7) are used to add additional
demand to the network at once. Since each route is made of a series of edges
and intersections controlled by stop signs, the flow of vehicles on each edge
is dominated by the processing rate of the upstream stop sign. With multiple
inflow nodes, vehicles fill up the network faster than with only one node,
allowing us to compare the performance of the networks when the demand reaches
near-capacity levels.

(a) Gird network with 2 routes with multiple inflow nodes (the baseline
network/scenario).

(b) Grid network with an added path and multiple inflow nodes (the add-path
network/scenario).

Figure 4: A 2-by-3 grid network resembling the classical diamond network with
multiple inflow nodes.

##  IV Results

We present how adding a path changes the overall vehicle flow, vehicle travel
time and capacity of the network compared to the baseline network without any
added path.

###  IV-A Impact on the Network Flow

As introduced in the experiment setup above, we explored the impact of the
added path to the overall output flow of the network. Specifically, we
compared how the output flow rate (measured in veh/hr) of networks, given
various levels of inflow demand, differs between the baseline scenario without
any additional path and the scenario with an added path.

Fig. 5 shows a comparison of the flow rates of vehicles leaving the network at
different demand levels. First, we could see that when the edge length is 50
meters with speed limit variations at 35 m/s, 15 m/s, and 10 m/s (Fig. 5a),
the output flow rate of the baseline scenario and the added-path scenarios are
almost equal at most demand levels except for the highest one. This is because
when the edge lengths are 50 meters, even though the speed limit of edges vary
at different levels, the maximum achievable speed on each edge is roughly the
same due to the limited distance for acceleration and deceleration. Therefore,
the three plots shown in Fig. 5a are very similar. In particular, vehicle
throughput is not increased despite the addition of a new road and route
option.

Moreover, when the edge length is increased from 50 meters to 400 meters (Fig.
5b), the output flow of the added-path network becomes even lower than that of
the baseline network as the speed limit on edges other than the added path
varies from 35 m/s to 10 m/s.

(a) Output Flow vs. Demand for networks with 50-meter edges.

(b) Output Flow vs. Demand for networks with 400-meter edges.

Figure 5: Comparison of output flow vs. demand for baseline and added-path
networks.

Overall, the analysis of output flow rate at various demand levels in
different networks shows that adding a path to the network reduces the ability
of the system to process vehicles. This reduction in output flow is more
significant when the added path is more preferable and the demand level is
high.

A more detailed breakdown of vehicle flow on each route in the added-path
network is presented in Figure 6. When the speed limit on edges other than the
added path varies from 35m/s to 10m/s while the speed limit on the added path
is fixed at 35m/s, the added path becomes increasingly attractive. As shown in
the stacked plot, although flow on each one of the original routes ($A-C-M-B$
and $A-N-D-B$) increases and converges to a constant as demand level
increases, the flow on the shortcut route ($A-C-D-B$) increases and then
decreases at an inflection point. The inflection point occurs at lower demand
level as the added path becomes more attractive.

Figure 6: Vehicle flow on each route in the added-path network with different
speed limits. Each subplot shows the flow per route in added-path networks
averaged over different edge length scenarios (50, 200, 300, and 400m) and the
same speed limit (35m/s, 15m/s and 10m/s, respectively) on edges other than
the added path, while the speed limit is fixed at 35m/s on the added path.

###  IV-B Impact on Vehicle Travel Time

In addition to comparing the output flow rate in the baseline network and the
added-path one, we also compared the average travel time of vehicles in either
type of the networks to determine how adding a path in the network impacts
vehicle travel time.

As shown in Fig. 7, in all scenarios of different combinations of edge length
and speed limits on edges other than the added path, the average travel time
in the added-path network results in larger values than the baseline network
when demand is large, and the added shortcut brings advantage to travel times
when demand is low.

Figure 7: Comparison of travel times at different demand level in different
networks. Critical points, or the crossing points, of the lines indicate when
the BP appears. An additional experiment on 500m edge length are added to test
whether its critical point is the same line as the other edge length
scenarios.

The microsimulation environment provides additional insight into the impacts
of the added path on travel times. When the level of demand is low, meaning
that fewer vehicles enter the system in a given time, vehicles making the
routing decision will almost always choose to use the shortcut route (i.e. the
route with the added path), as demonstrated in Fig. 8. These vehicles complete
their trips and exit the system without generating much congestion on the
shortcut route, giving opportunities for future vehicles to repeat the
behavior and take advantage of the shortcut route. On the other hand, when the
demand level is high, vehicles enter the system at a denser rate. Since the
shortcut is occupied faster and becomes less advantageous faster, the
following vehicles are forced to use the other routes and the advantage of
using the shortcut diminishes.

Figure 8: Percentage of vehicles using each route with various edge lengths
(50, 200, 300, and 400m) when speed limit is 15m/s on edges other than the
added path while the speed limit is fixed at 35m/s on the added path.

It is also worth noting that, for networks with the same speed limit on edges
other than the added path, the ”critical point” (i.e. where the BP shows up)
appears at higher demand level as the edge length becomes longer. Critical
points show strong linearity with the edge length and the demand level. As
shown in Fig. 7, the fitted line from the critical points of 50, 200, 300, and
400m cases cross the critical point of the addtional 500m case.

###  IV-C Impact on Network Capacity

Although as discussed above, the results of microsimulation have shown that
adding a path to the network could worsen the network performance, it is
reasonable for one to wonder whether the additional physical capacity brought
by the added path actually increases the operational capacity of the network.
As described in experiment setup, in order to accelerate the rate at which the
network approaches capacity, we added input flow to the network at Node 2, 3,
5, 7, in addition to Node 1, as labeled in Fig. 2b. We then plot the flow-
density curves of the networks and compare how the capacity of the baseline
and added-path networks differs.

As shown in Fig. 9, although adding a path adds more physical space to the
network, the actual capacity of the added-path network is almost the same as
that of the baseline network in all scenarios. This result is explained by an
observation of the microsimulation runs, which reveals that even though the
added path provides additional physical capacity, the attractiveness of the
shortcut route results in the downstream edge of the added path (edge D
$\rightarrow$ B in Fig. 2b) getting filled up faster than other edges,
consequently making the shortcut route undesirable. Therefore, even though
vehicles will choose to use the shortcut route at the beginning, when it is
chosen by too many vehicles, the road segments upstream and downstream of the
added path becomes congested, making it increasingly harder to get to the
added path, thus resulting in the added path being under-utilized.

Figure 9: Comparison of flow-density curves of both types of networks with
different edge lengths and a speed limit of 15m/s on edges other than the
added path.

##  V Conclusion and Discussion

In this paper, we have designed a grid network with and without an added path
to explore the Braess’s Paradox in the dynamic microsimulation environment.
Different from existing research about BP that assigns traffic on possible
routes instantaneously, we use the Flow Project and SUMO to simulate the
vehicle behaviors, allowing each vehicle to dynamically choose the route with
the lowest estimated travel time evaluated. By varying the edge length and
speed limit, we discuss the impact of the added path on network flow, vehicle
travel time, and network capacity. We find that adding a path to the network
results in reduced network flow rate and vehicle flow on the added path
decreases after a inflection point. In all scenarios, the added path increases
the average travel times experienced by vehicles traveling through the
network. Moreover, the increased congestion resulted from vehicles using the
added path makes the additional physical room brought by the added path
underutilized so that it does not provide more capacity to the system.

Since we discuss the BP from the microsimulation environment, we could explore
how different parameters of the infrastructure affect the network performance
more precisely. This is what previous dynamic traffic assignment related
models can not present. A microscopic perspective provides a more advanced
view on the BP, in which the impact of an added path can be characterized more
finely in terms of the network characteristics. For example, while the edge
costs of the static model (Fig. 1) may not be intuitively correspond to real
networks, a microscopic model permits capturing realistic travel time cost
functions. In the future, we would like to 1) give sensitivity analysis the
design of user travel cost function; 2) explore how real-world traffic
networks might suffer from the BP; 3) how traffic control strategies could
bring a difference. We are also interested to more closely consider the
theoretical and conceptual differences between the static and dynamic
formulations.

## References

  * [1] R. Steinberg and W. I. Zangwill, “The prevalence of braess’ paradox,” _Transportation Science_ , vol. 17, no. 3, pp. 301–318, 1983.
  * [2] M. Frank, “The braess paradox,” _Mathematical Programming_ , vol. 20, no. 1, pp. 283–302, 1981.
  * [3] A. Nagurney and L. S. Nagurney, “The braess paradox,” _International Encyclopedia of Transportation. Elsevier, forthcoming. Invited chapter, pre-print available at https://supernet. isenberg. umass. edu/articles/braess-encyc. pdf_ , 2021.
  * [4] S. Bittihn and A. Schadschneider, “Braess paradox in a network with stochastic dynamics and fixed strategies,” _Physica A: Statistical Mechanics and its Applications_ , vol. 507, pp. 133–152, 2018.
  * [5] B.-B. Fu, C.-X. Zhao, and S.-b. Li, “The analysis of braess’ paradox and robustness based on dynamic traffic assignment models,” _Discrete Dynamics in Nature and Society_ , vol. 2013, 2013.
  * [6] D. E. Wolf, M. Schreckenberg, and A. Bachem, _Traffic and granular flow_. World Scientific, 1996.
  * [7] R. M. Colombo, H. Holden, and F. Marcellini, “On the microscopic modeling of vehicular traffic on general networks,” _SIAM Journal on Applied Mathematics_ , vol. 80, no. 3, pp. 1377–1391, 2020.
  * [8] A. Belov, K. Mattas, M. Makridis, M. Menendez, and B. Ciuffo, “A microsimulation based analysis of the price of anarchy in traffic routing: The enhanced braess network case,” _Journal of Intelligent Transportation Systems_ , pp. 1–16, 2021.
  * [9] C. Wu, A. R. Kreidieh, K. Parvate, E. Vinitsky, and A. M. Bayen, “Flow: A modular learning framework for mixed autonomy traffic,” _IEEE Transactions on Robotics_ , 2021.
  * [10] E. Vinitsky, A. Kreidieh, L. Le Flem, N. Kheterpal, K. Jang, C. Wu, F. Wu, R. Liaw, E. Liang, and A. M. Bayen, “Benchmarks for reinforcement learning in mixed-autonomy traffic,” in _Conference on robot learning_. PMLR, 2018, pp. 399–409.
  * [11] S. C. Dafermos and F. T. Sparrow, “The traffic assignment problem for a general network,” _Journal of Research of the National Bureau of Standards B_ , vol. 73, no. 2, pp. 91–118, 1969.
  * [12] M. J. Smith, “The existence, uniqueness and stability of traffic equilibria,” _Transportation Research Part B: Methodological_ , vol. 13, no. 4, pp. 295–304, 1979.
  * [13] M. Ng and S. T. Waller, “A dynamic route choice model considering uncertain capacities,” _Computer-Aided Civil and Infrastructure Engineering_ , vol. 27, no. 4, pp. 231–243, 2012.
  * [14] Q. Meng and H. L. Khoo, “A computational model for the probit-based dynamic stochastic user optimal traffic assignment problem,” _Journal of Advanced Transportation_ , vol. 46, no. 1, pp. 80–94, 2012.
  * [15] M. Treiber, A. Hennecke, and D. Helbing, “Congested traffic states in empirical observations and microscopic simulations,” _Physical review E_ , vol. 62, no. 2, p. 1805, 2000.