# A Note on Inextensible Flows of Curves in $E^{n}$

Önder Gökmen Yıldız, Murat Tosun, Sıddıka Özkaldı Karakuş  1 Bilecik
University, Faculty of Sciences and Arts, Department of Mathematics, 11210,
Bilecik, Turkey<EMAIL_ADDRESS><EMAIL_ADDRESS>2 Sakarya, Faculty of Sciences and Arts, Department of Mathematics, Sakarya,
Turkey<EMAIL_ADDRESS>
###### Abstract.

In this paper, we investigate the general formulation for inextensible flows
of curves in $E^{n}$. The necessary and sufficient conditions for inextensible
curve flow are expressed as a partial differential equation involving the
curvatures.

###### Key words and phrases:

Curvature flows, inextensible, Euclidean n-space.

2000 Mathematics Subject Classification: 53C44, 53a04, 53A05, 53A35.

##  1\. Introduction

It is well known that many nonlinear phenomena in physics, chemistry and
biology are described by dynamics of shapes, such as curves and surfaces. The
evolution of curve and surface has significant applications in computer vision
and image processing. The time evolution of a curve or surface generated by
its corresponding flow in -for this reason we shall also refer to curve and
surface evolutions as flows throughout this article- is said to be
inextensible if, in the former case, its arclength is preserved, and in the
latter case, if its intrinsic curvature is preserved [8]. Physically,
inextensible curve flows give rise to motions in which no strain energy is
induced. The swinging motion of a cord of fixed length, for example, or of a
piece of paper carried by the wind, can be described by inextensible curve and
surface flows. Such motions arise quite naturally in a wide range of a
physical applications. For example, both Chirikjian and Burdick [1] and
Mochiyama et al. [10] study the shape control of hyper-redundant, or snake-
like robots.

Inextinsible curve and surface flows also arise in the context of many
problems in computer vision [7][9] and computer animation [2], and even
structural mechanics [11].

There have been a lot of studies in the literature on plane curve flows,
particularly on evolving curves in the direction of their curvature vector
field (referred to by various names such as “curve shortening”, flow by
curvature” and “heat flow”). Particularly relevant to this paper are the
methods developed by Gage and Hamilton [3] and Grayson [5] for studying the
shrinking of closed plane curves to circle via heat equation.

In this paper, we develop the general formulation for inextensible flows of
curves in $E^{n\text{ }}$. Necessary and sufficient conditions for an
inextensible curve flow are expressed as a partial differential equation
involving the curvatures.

##  2\. Preliminary

To meet the requirements in the next sections, the basic elements of the
theory of curves in the Euclidean n-space $E^{n}$ are briefly presented in
this section (A more complete elementary treatment can be found in [4][6]).

Let $\alpha:I\subset R\mathbb{\longrightarrow}E^{n\text{ }}$be an arbitrary
curve in $E^{n\text{ }}$ Recall that the curve $\alpha$ is said to be a unit
speed curve (or parameterized by arclength functions) if
$\left\langle\alpha^{\prime}(s),\alpha^{\prime}(s)\right\rangle=1$, where
$\left\langle.,.\right\rangle$ denotes the standard inner product of given by

$\left\langle X,Y\right\rangle={\displaystyle\sum\limits_{i=1}^{n}}x_{i}y_{i}$

for each
$X=\left(x_{1},x_{2},...,x_{n}\right),Y=\left(y_{1},y_{2},...,y_{n}\right)\in
R^{n}$. In particular, norm of a vector $X\in R^{n}$ is given by
$\left\|X\right\|=\sqrt{\left\langle X,Y\right\rangle}$. Let
$\left\\{V_{1},V_{2},...,V_{n}\right\\}$ be the moving Frenet frame along the
unit speed curve $\alpha$, where $V_{i}\left(i=1,2,...,n\right)$ denotes the
$i^{th}$ Frenet vector field. Then Frenet formulas are given by

$\left[\begin{array}[c]{c}V_{1}^{\prime}\\\ V_{2}^{\prime}\\\
V_{3}^{\prime}\\\ \vdots\\\ V_{n-2}^{\prime}\\\ V_{n-1}^{\prime}\\\
V_{n}^{\prime}\end{array}\right]=\left[\begin{array}[c]{cccccccc}0&k_{1}&0&0&\cdots&0&0&0\\\
-k_{1}&0&k_{2}&0&\cdots&0&0&0\\\ 0&-k_{2}&0&k_{3}&\cdots&0&0&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&0&0&\cdots&0&k_{n-2}&0\\\ 0&0&0&0&\cdots&-k_{n-2}&0&k_{n-1}\\\
0&0&0&0&\cdots&0&-k_{n-1}&0\end{array}\right]\left[\begin{array}[c]{c}V_{1}\\\
V_{2}\\\ V_{3}\\\ \vdots\\\ V_{n-2}\\\ V_{n-1}\\\ V_{n}\end{array}\right]$

where $k_{i}\left(i=1,2,...,n\right)$ denotes the $i^{th}$ curvature function
of the curve [4][6]. If all of the curvatures $k_{i}\left(i=1,2,...,n\right)$
of the curve vanish nowhere in $I\subset R$, it is called a non-degenerate
curve.

##  3\. Inextinsible Flows of Curve in $E^{n}$

Throughout this paper, we suppose that

$\alpha:\left[0,l\right]\times\left[0,w\right)\mathbb{\longrightarrow}E^{n\text{
}}$

is a one parameter family of smooth curves in $E^{n\text{ }}$, where $l$ is
the arclength of the initial curve. Let $u$ be the curve parameterization
variable, $0\leq u\leq l$. If the speed curve $\alpha$ is denoted by
$v=\left\|\frac{d\alpha}{du}\right\|$ then the arclength of $\alpha$ is

$S(u)={\displaystyle\int\limits_{0}^{u}}\left\|\frac{\partial\alpha}{\partial
u}\right\|du={\displaystyle\int\limits_{0}^{u}}vdu.$

The operator $\frac{\partial}{\partial s}$ is given with respect to $u$ by

$\frac{\partial}{\partial s}=\frac{1}{v}\frac{\partial}{\partial u}.$ (3.1)

Thus, the arclength is $ds=vdu$.

######  Definition 3.1.

Any flow of the curve can be expressed following form:

$\frac{\partial\alpha}{\partial
t}={\displaystyle\sum\limits_{i=1}^{n}}f_{i}V_{i}$

where $f_{i}$ denotes the $i^{th}$ scalar speed of the curve Let the arclength
variation be

$S(u,t)={\displaystyle\int\limits_{0}^{u}}vdu.$

In the Euclidean space the requirement that the curve not be subject to any
elongation or compression can be expressed by the condition

$\frac{\partial}{\partial
t}S(u,t)={\displaystyle\int\limits_{0}^{u}}\frac{\partial v}{\partial
t}du=0,\text{ \ }u\in\left[0,l\right].$ (3.2)

######  Definition 3.2.

A curve evolution $\alpha(u,t)$ and its flow $\frac{\partial\alpha}{\partial
t}$ are said to be inextensible if

$\frac{\partial}{\partial t}\left\|\frac{\partial\alpha}{\partial
u}\right\|=0.$

Now, we research the necessary and sufficient condition for inelastic curve
flow. For this reason, we need to the following Lemma.

######  Lemma 3.3.

Let $\frac{\partial\alpha}{\partial
t}={\displaystyle\sum\limits_{i=1}^{n}}f_{i}V_{i}$ be a smooth flow of the
curve $\alpha$. The flow is inextensible if and only if

$\frac{\partial v}{\partial t}=\frac{\partial f_{1}}{\partial u}-f_{2}vk_{1}.$
(3.3)

###### Proof.

Since $\frac{\partial}{\partial u}$ and $\frac{\partial}{\partial t}$ commute
and $v^{2}=\left\langle\frac{\partial\alpha}{\partial
u},\frac{\partial\alpha}{\partial u}\right\rangle,$ we have

$\displaystyle 2v\frac{\partial v}{\partial t}$
$\displaystyle=\frac{\partial}{\partial
t}\left\langle\frac{\partial\alpha}{\partial u},\frac{\partial\alpha}{\partial
u}\right\rangle$ $\displaystyle=2\left\langle\frac{\partial\alpha}{\partial
u},\frac{\partial}{\partial
u}\left({\displaystyle\sum\limits_{i=1}^{n}}f_{i}V_{i}\right)\right\rangle$
$\displaystyle=2\left\langle
vV_{1},{\displaystyle\sum\limits_{i=1}^{n}}\frac{\partial f_{i}}{\partial
u}V_{i}+{\displaystyle\sum\limits_{i=1}^{n}}f_{i}\frac{\partial
V_{i}}{\partial u}\right\rangle$ $\displaystyle=2\left\langle
vV_{1},\frac{\partial f_{1}}{\partial u}V_{1}+f_{1}\frac{\partial
V_{1}}{\partial u}+...+\frac{\partial f_{n}}{\partial
u}V_{n}+f_{n}\frac{\partial V_{n}}{\partial u}\right\rangle$
$\displaystyle=2\left\langle vV_{1},\frac{\partial f_{1}}{\partial
u}V_{1}+f_{1}vk_{1}V_{2}+...+\frac{\partial f_{n}}{\partial
u}V_{n}-f_{n}vk_{n-1}V_{n-1}\right\rangle$
$\displaystyle=2\left(\frac{\partial f_{1}}{\partial u}-f_{2}vk_{1}\right).$

Thus, we reach

$\frac{\partial v}{\partial t}=\frac{\partial f_{1}}{\partial u}-f_{2}vk_{1}.$

∎

######  Theorem 3.4.

Let $\left\\{V_{1},V_{2},...,V_{n}\right\\}$ be the moving Frenet frame of the
curve $\alpha$ and $\frac{\partial\alpha}{\partial
t}={\displaystyle\sum\limits_{i=1}^{n}}f_{i}V_{i}$ be a differentiable flow of
$\alpha$ in $E^{n\text{ }}$.Then the flow is inextensible if and only if

$\frac{\partial f_{1}}{\partial s}=f_{2}k_{1}.$ (3.4)

###### Proof.

Suppose that the curve flow is inextensible. From equations (3.2) and (3.3)
for $u\in\left[0,l\right]$, we see that

$\frac{\partial}{\partial
t}S(u,t)={\displaystyle\int\limits_{0}^{u}}\frac{\partial v}{\partial
t}du={\displaystyle\int\limits_{0}^{u}}\left(\frac{\partial f_{1}}{\partial
u}-f_{2}vk_{1}\right)du=0.$

Thus, it can be see that

$\frac{\partial f_{1}}{\partial u}-f_{2}vk_{1}=0.$

Considering the last equation and (3.1), we reach

$\frac{\partial f_{1}}{\partial s}=f_{2}k_{1}.$

Conversely, following similar way as above, the proof is completed.

Now, we restrict ourselves to arclength parameterized curves. That is, $v=1$
and the local coordinate $u$ corresponds to the curve arclength $s$. We
require the following Lemma

######  Lemma 3.5.

Let $\left\\{V_{1},V_{2},...,V_{n}\right\\}$ be the moving Frenet frame of the
curve $\alpha$. Then, the differentions of
$\left\\{V_{1},V_{2},...,V_{n}\right\\}$ with respect to $t$ is

$\displaystyle\frac{\partial V_{1}}{\partial t}$
$\displaystyle=\left[{\displaystyle\sum\limits_{i=2}^{n-1}}\left(f_{i-1}k_{i-1}+\frac{\partial
f_{i}}{\partial
s}-f_{i+1}k_{i}\right)V_{i}\right]+\left(f_{n-1}k_{n-1}+\frac{\partial
f_{n}}{\partial s}\right)V_{n},$ $\displaystyle\frac{\partial V_{j}}{\partial
t}$ $\displaystyle=-\left(f_{j-1}k_{j-1}+\frac{\partial f_{j}}{\partial
s}-f_{j+1}k_{j}\right)V_{1}+\left[{\displaystyle\sum\limits_{\begin{subarray}{c}k=2\\\
k\neq i\end{subarray}}^{n}}\Psi_{kj}V_{k}\right],\text{ \ }1<j<n,$
$\displaystyle\frac{\partial V_{n}}{\partial t}$
$\displaystyle=-\left(f_{n-1}k_{n-1}+\frac{\partial f_{n}}{\partial
s}\right)V_{1}+\left[{\displaystyle\sum\limits_{k=2}^{n-1}}\Psi_{kn}V_{k}\right],$

where $\Psi_{kj}=\left\langle\frac{\partial V_{j}}{\partial
t},V_{k}\right\rangle$ and $\Psi_{kn}=\left\langle\frac{\partial
V_{n}}{\partial t},V_{k}\right\rangle$.

###### Proof.

For $\frac{\partial}{\partial t}$ and $\frac{\partial}{\partial s}$ commute,
it seen that

$\displaystyle\frac{\partial V_{1}}{\partial t}$
$\displaystyle=\frac{\partial}{\partial t}\left(\frac{\partial\alpha}{\partial
s}\right)=\frac{\partial}{\partial s}\left(\frac{\partial\alpha}{\partial
t}\right)=\frac{\partial}{\partial
s}\left({\displaystyle\sum\limits_{i=1}^{n}}f_{i}V_{i}\right)={\displaystyle\sum\limits_{i=1}^{n}}\frac{\partial
f_{i}}{\partial
s}V_{i}+{\displaystyle\sum\limits_{i=1}^{n}}f_{i}\frac{\partial
V_{i}}{\partial s}$ $\displaystyle=\frac{\partial f_{1}}{\partial
s}V_{1}+f_{1}\frac{\partial V_{1}}{\partial s}+\frac{\partial f_{2}}{\partial
s}V_{2}+f_{2}\frac{\partial V_{2}}{\partial s}+...+\frac{\partial
f_{n}}{\partial s}V_{n}+f_{n}\frac{\partial V_{n}}{\partial s}$
$\displaystyle=\frac{\partial f_{1}}{\partial
s}V_{1}+f_{1}k_{1}V_{2}+\frac{\partial f_{2}}{\partial
s}V_{2}+f_{2}\left(-k_{1}V_{1}+k_{2}V_{3}\right)+...+\frac{\partial
f_{n}}{\partial s}V_{n}-f_{n}k_{n-1}V_{n-1}.$

Substituting the equation (3.4) into the last equation and using Theorem 3.4.,
we have

$\frac{\partial V_{1}}{\partial
t}=\left[{\displaystyle\sum\limits_{i=2}^{n-1}}\left(f_{i-1}k_{i-1}+\frac{\partial
f_{i}}{\partial
s}-f_{i+1}k_{i}\right)V_{i}\right]+\left(f_{n-1}k_{n-1}+\frac{\partial
f_{n}}{\partial s}\right)V_{n}.$

Now, let us differentiate the Frenet frame with respect to $t$ for $1<j<n$ as
follows;

$\displaystyle 0$ $\displaystyle=\frac{\partial}{\partial t}\left\langle
V_{1},V_{j}\right\rangle=\left\langle\frac{\partial V_{1}}{\partial
t},V_{j}\right\rangle+\left\langle V_{1},\frac{\partial V_{j}}{\partial
t}\right\rangle$ $\displaystyle=\left(f_{i-1}k_{i-1}+\frac{\partial
f_{i}}{\partial s}-f_{i+1}k_{i}\right)+\left\langle V_{1},\frac{\partial
V_{j}}{\partial t}\right\rangle.$ (3.5)

From (3.5), we have obtain

$\frac{\partial V_{j}}{\partial t}=-\left(f_{j-1}k_{j-1}+\frac{\partial
f_{j}}{\partial
s}-f_{j+1}k_{j}\right)V_{1}+\left[{\displaystyle\sum\limits_{\begin{subarray}{c}k=2\\\
k\neq j\end{subarray}}^{n}}\Psi_{kj}V_{k}\right].$

Lastly, considering $\left\langle V_{1},V_{n}\right\rangle=0$ and following
similar way as above, we reach

$\frac{\partial V_{n}}{\partial t}=-\left(f_{n-1}k_{n-1}+\frac{\partial
f_{n}}{\partial
s}\right)V_{1}+\left[{\displaystyle\sum\limits_{k=2}^{n-1}}\Psi_{kn}V_{k}\right].$

######  Theorem 3.6.

Suppose that the curve flow $\frac{\partial\alpha}{\partial
t}={\displaystyle\sum\limits_{i=1}^{n}}f_{i}V_{i}$ is inextensible. Then the
following system of partial differential equations holds:

$\displaystyle\frac{\partial k_{1}}{\partial t}$
$\displaystyle=f_{2}k_{1}^{2}+f_{1}\frac{\partial k_{1}}{\partial
s}+\frac{\partial^{2}f_{2}}{\partial s^{2}}-2\frac{\partial f_{2}}{\partial
s}k_{2}-f_{3}\frac{\partial k_{2}}{\partial s}-f_{2}k_{2}^{2}-f_{4}k_{3}k_{2}$
$\displaystyle\frac{\partial k_{i-1}}{\partial t}$
$\displaystyle=-\frac{\partial\Psi_{(i-1)i}}{\partial s}-\Psi_{(i-2)i}k_{i-2}$
$\displaystyle\frac{\partial k_{i}}{\partial t}$
$\displaystyle=\frac{\partial\Psi_{(i-1)i}}{\partial s}-\Psi_{(i+2)i}k_{i+2}$
$\displaystyle\frac{\partial k_{n-1}}{\partial t}$
$\displaystyle=-\frac{\partial\Psi_{(n-1)n}}{\partial
s}-\Psi_{(n-2)n}k_{n-2}.$

∎

∎

###### Proof.

Since $\frac{\partial}{\partial s}\frac{\partial V_{1}}{\partial
t}=\frac{\partial}{\partial t}\frac{\partial V_{1}}{\partial s}$, we get

$\displaystyle\frac{\partial}{\partial s}\frac{\partial V_{1}}{\partial t}$
$\displaystyle=\frac{\partial}{\partial
s}\left[{\displaystyle\sum\limits_{i=2}^{n-1}}\left(f_{i-1}k_{i-1}+\frac{\partial
f_{i}}{\partial
s}-f_{i+1}k_{i}\right)V_{i}+\left(f_{n-1}k_{n-1}+\frac{\partial
f_{n}}{\partial s}\right)V_{n}\right]$
$\displaystyle={\displaystyle\sum\limits_{i=2}^{n-1}}\left[\left(\frac{\partial
f_{i-1}}{\partial s}k_{i-1}+f_{i-1}\frac{\partial k_{i-1}}{\partial
s}+\frac{\partial^{2}f_{i}}{\partial s^{2}}-\frac{\partial f_{i+1}}{\partial
s}k_{i}-f_{i+1}\frac{\partial k_{i}}{\partial s}\right)V_{i}\right]$
$\displaystyle+{\displaystyle\sum\limits_{i=2}^{n-1}}\left[\left(f_{i-1}k_{i-1}+\frac{\partial
f_{i}}{\partial s}-f_{i+1}k_{i}\right)\frac{\partial V_{i}}{\partial
s}\right]$ $\displaystyle+\left(\frac{\partial f_{n-1}}{\partial
s}k_{n-1}+f_{n-1}\frac{\partial k_{n-1}}{\partial
s}+\frac{\partial^{2}f_{n}}{\partial
s^{2}}\right)V_{n}+\left(f_{n-1}k_{n-1}+\frac{\partial f_{n}}{\partial
s}\right)\frac{\partial V_{n}}{\partial s}$

while

$\frac{\partial}{\partial t}\frac{\partial V_{1}}{\partial
s}=\frac{\partial}{\partial t}\left(k_{1}V_{2}\right)=\frac{\partial
k_{1}}{\partial t}V_{2}+k_{1}\frac{\partial V_{2}}{\partial t}.$

Thus, from the both of above two equations, we reach

$\frac{\partial k_{1}}{\partial t}=f_{2}k_{1}^{2}+f_{1}\frac{\partial
k_{1}}{\partial s}+\frac{\partial^{2}f_{2}}{\partial s^{2}}-2\frac{\partial
f_{3}}{\partial s}k_{2}-f_{3}\frac{\partial k_{2}}{\partial
s}-f_{2}k_{2}^{2}-f_{4}k_{3}k_{2}.$

For $1<i<n$, noting that $\frac{\partial}{\partial s}\frac{\partial
V_{i}}{\partial t}=\frac{\partial}{\partial t}\frac{\partial V_{i}}{\partial
s}$, it is seen that

$\displaystyle\frac{\partial}{\partial s}\frac{\partial V_{i}}{\partial t}$
$\displaystyle=\frac{\partial}{\partial
s}\left[-\left(f_{i-1}k_{i-1}+\frac{\partial f_{i}}{\partial
s}-f_{i+1}k_{i}\right)V_{1}+{\displaystyle\sum\limits_{k=2}^{n}}\Psi_{kj}V_{k}\right]$
$\displaystyle=-\left(\frac{\partial f_{i-1}}{\partial
s}k_{i-1}+f_{i-1}\frac{\partial k_{i-1}}{\partial
s}+\frac{\partial^{2}f_{i}}{\partial s^{2}}-\frac{\partial f_{i+1}}{\partial
s}k_{i}-f_{i+1}\frac{\partial k_{i}}{\partial s}\right)V_{1}$
$\displaystyle+\left(f_{i-1}k_{i-1}+\frac{\partial f_{i}}{\partial
s}-f_{i+1}k_{i}\right)\frac{\partial V_{1}}{\partial
s}+{\displaystyle\sum\limits_{\begin{subarray}{c}k=2\\\ k\neq
i\end{subarray}}^{n}}\left(\frac{\partial\Psi_{ki}}{\partial
s}V_{k}+\Psi_{ki}\frac{\partial V_{k}}{\partial s}\right)$

while

$\frac{\partial}{\partial t}\frac{\partial V_{i}}{\partial
s}=\frac{\partial}{\partial
t}\left(-k_{i-1}V_{i-1}+k_{i}V_{i+1}\right)=-\frac{\partial k_{i-1}}{\partial
t}V_{i-1}-k_{i-1}\frac{\partial V_{i-1}}{\partial t}+\frac{\partial
k_{i}}{\partial t}V_{i+1}+k_{i}\frac{\partial V_{i+1}}{\partial t}.$

Thus, we obtain

$\frac{\partial k_{i-1}}{\partial t}=-\frac{\partial\Psi_{(i-1)i}}{\partial
s}-\Psi_{(i-2)i}k_{i-2}$

and

$\frac{\partial k_{i}}{\partial t}=\frac{\partial\Psi_{(i+1)i}}{\partial
s}-\Psi_{(i+2)i}k_{i+1}.$

Lastly, considering $\frac{\partial}{\partial s}\frac{\partial V_{n}}{\partial
t}=\frac{\partial}{\partial t}\frac{\partial V_{n}}{\partial s}$ and following
similar way as above, we reach

$\frac{\partial k_{n-1}}{\partial t}=-\frac{\partial\Psi_{(n-1)n}}{\partial
s}-\Psi_{(n-2)n}k_{n-2}.$

∎

## References

  * [1] G. Chirikjian, J. Burdick, A modal approach to hyper-redundant manipulator kinematics, IEEE Trans. Robot. Autom. 10, 343–354 (1994).
  * [2] M. Desbrun, M.-P. Cani-Gascuel, Active implicit surface for animation, in: Proc. Graphics Interface Canadian Inf. Process. Soc., 143–150 (1998).
  * [3] M. Gage, R.S. Hamilton, The heat equation shrinking convex plane curves, J. Differential Geom. 23, 69–96 (1986).
  * [4] H. Gluk, Higher curvatures of curves in Euclidean space, Amer. Math. Month. 73(1966), 699-704.
  * [5] M. Grayson, The heat equation shrinks embedded plane curves to round points, J. Differential Geom. 26, 285–314 (1987).
  * [6] H. H. Hacisalihoğlu, Differential Geometry, University of İnönü Press, Malatya, 1983.
  * [7] M. Kass, A. Witkin, D. Terzopoulos, Snakes: active contour models, in: Proc. 1st Int. Conference on Computer Vision, 259–268 (1987).
  * [8] D. Y. Kwon, F.C. Park, D.P. Chi, Inextensible flows of curves and developable surfaces, Appl. Math. Lett. 18 (2005) 1156-1162.
  * [9] H.Q. Lu, J.S. Todhunter, T.W. Sze, Congruence conditions for nonplanar developable surfaces and their application to surface recognition, CVGIP, Image Underst. 56, 265–285 (1993).
  * [10] H. Mochiyama, E. Shimemura, H. Kobayashi, Shape control of manipulators with hyper degrees of freedom, Int. J. Robot.Res., 18, 584–600 (1999).
  * [11] D.J. Unger, Developable surfaces in elastoplastic fracture mechanics, Int. J. Fract. 50, 33–38 (1991).
  * [12] O. G. Yildiz, S. Ersoy, M. Masal, A Note on Inextensible Flows of Curves on Oriented Surface, arXiv:1106.2012v1.
  * [13] O. G. Yildiz, Minkowski Uzayında Yüzey Üzerinde Eğrilerin elastik Olmayan Hareketleri, Sakarya Üniversitesi Fen Bilimleri Enstitüsü Yüksek Lisans Tezi, 2011.


# Time-Quantitatively Nonblocking Supervisory Control of Timed Discrete-Event
Systems

Renyuan Zhang1, Jiale Wu1, Junhua Gou1, Yabo Zhu1 and Kai Cai2 *This work was
supported in part by the Natural Science Foundation of Shaanxi Province,
China, Grant no. 2021JM-072.1R. Zhang, J. Wu, J. Gou and Y. Zhu are with the
School of Automation, Northwestern Polytechnical University, Xi’an, China
(ryzhang@nwpu.edu.cn).2K. Cai is with the Control and Artificial Intelligence
Group, Department of Core Informatics, Osaka Metropolitan University, Osaka,
Japan (kai.cai@eng.osaka-cu.ac.jp).

###### Abstract

Recently we proposed an automaton property of quantitative nonblockingness in
supervisory control of discrete-event systems, which quantifies the standard
nonblocking property by capturing the practical requirement that all tasks be
completed within a bounded number of steps. However, in practice tasks may be
further required to be completed in specific time; this requirement cannot be
fulfilled by the quantitatively nonblocking supervisor. To meet this new
requirement, in this paper we introduce the concept of time-quantitative
nonblockingness, which extends the concept of quantitative nonblockingness
from untimed discrete-event systems (DES) to timed DES. This property requires
that each task must be completed within a bounded time. Accordingly, we
formulate a new time-quantitatively nonblocking supervisory control problem of
TDES, and characterize its solvability in terms of a new concept of time-
quantitative language completability. It is proved that there exists a unique
supremal time-quantitatively completable sublanguage of a given language, and
we develop an automaton-based algorithm to compute the supremal sublanguage.
Finally, we present an approach to compute a maximally permissive supervisory
control solution to the new time-quantitative nonblocking supervisory control
problem.

##  I Introduction

In standard supervisory control of (timed) discrete-event systems (DES) [1, 2,
3, 4, 5, 6, 7, 8], and other extensions and applications on nonblocking
supervisory control, e.g. [9, 10, 11, 12, 13, 14, 15], the plant to be
controlled is modeled by finite-state automata and marker states are used to
represent ‘desired states’. A desired state can be a goal location, a
start/home configuration, or a task completion [16, 4]. Besides enforcing all
imposed control specifications, a nonblocking supervisor ensures that every
system trajectory can reach a marker state (in a finite number of steps). As a
result, the system under supervision may always be able to reach a goal,
return home, or complete a task.

The nonblocking property only qualitatively guarantees finite reachability of
marker states. There is no given bound on the number of steps or time for
reaching marker states, so it can take an arbitrarily large (though finite)
number of steps or time before a marker state is reached. Consequently, this
qualitatively nonblocking property might not be sufficient for many practical
purposes, especially when there are prescribed bounds (of transition steps or
time) for reaching desired states. To address this issue, recently in [17,
18], we proposed a quantitatively nonblocking property to capture the
practical requirement that marker states be reached within a prescribed number
of (transition) steps. By this property, in the worst case, each reachable
state can reach a marker state in no more than bounded number of steps.
However, in many practical cases, tasks (represented by marker states) are
further required to be completed in specific bounded time. For example, a
rescue vehicle is required not only to reach a goal location but to do so
within a given time; a warehouse AGV is expected not only to return to a self-
charging area but to do so periodically with a predetermined period; and a
production machine is required not only to complete a task (e.g. processing a
workpiece) but also to do so within a prescribed time. In Section II below, we
will present a more detailed motivation example.

With the above motivation, we extend the concept of quantitative
nonblockingness from untimed DES (the elapse of time is not modeled) to the
framework of timed discrete event systems (TDES) [4, 8], where the occurrence
of a time unit is described by the execution of a $tick$ event. Thus the bound
of time for reaching a subset of marker states can be represented by some
integer $N_{i}$ $ticks$. In this framework, we measure the ‘maximal time’
between the reachable states and the specific subset of marker states, and
this is done by counting the number of $ticks$ (rather than the number of all
events) in every string leading a reachable state to one of the marker states
in the specified subset. More specifically, assume that the marker states of
the plant is partitioned according to $\\{Q_{m,i}|i\in\mathcal{I}\\}$
($\mathcal{I}$ is an index set), and let $N_{i}$ be a finite positive integer
which denotes the required number of $ticks$ to reach marker states in
$Q_{m,i}$. We define a _time-quantitatively nonblocking property_ (with
respect to $\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$) of an automaton if from
every reachable state of this automaton, the number of $ticks$ included in
each string that leads the reachable state to marker states in $Q_{m,i}$ is
smaller or equal to $N_{i}$. That is, in the worst case, for every marker
state subset $Q_{m,i}$, every reachable state can reach $Q_{m,i}$ in no more
than $N_{i}$ $ticks$ following any string.

Moreover, we formulate a new _time-quantitatively nonblocking supervisory
control problem_ by requiring a supervisory control solution to be
implementable by a time-quantitatively nonblocking automaton. To solve this
problem, we present a new necessary and sufficient condition by identifying a
language property called _time-quantitative completability_. The latter
roughly means that in the worst case, for every sublanguage $K_{i}$
($i\in\mathcal{I}$) (defined according to a particular type of task
corresponding to $Q_{m,i}$) of a given language $K$, every string in the
closure of $K$ can be extended to a string in the sublanguage $K_{i}$ in no
more than $N_{i}$ $ticks$. Further we show that this time-quantitative
language completability is closed under arbitrary set unions, and together
with language controllability which is also closed under unions, a maximally
permissive solution exists for the newly formulated time-quantitatively
nonblocking supervisory control problem. Finally we design effective
algorithms for the computation of such an optimal solution.

Detailed literature review on quantitative nonblockingness of untimed DES are
referred in [17, 18]. For the timed systems, time-bounded liveness is similar
to our concept of time-quantitative nonblockingness; time-bounded liveness is
introduced in [19] to express and verify constraints on the delays described
by exact time, and there are algorithms (e.g. [20]) and tools (e.g. KRONORS
[21]) that can verify the bounded liveness. However, unlike our considered
supervisory control problems, uncontrollable events and maximal permissiveness
of strategies are not considered.

The rest of this paper is organized as follows. Section II reviews the
nonblocking supervisory control theory of TDES and presents a motivating
example for this work. Section III introduces the new concept of time-
quantitatively nonblocking TDES, and formulates the time-quantitatively
nonblocking supervisory control problem (TQNSCP). Section IV presents a
necessary and sufficient condition for the solvability of TQNSCP in terms of a
new concept of time-quantitative language completability, and develops an
algorithm to compute the supremal time-quantitatively completable sublanguage.
Section V presents a solution to the time-quantitatively nonblocking
supervisory control problem. Finally Section VI states our conclusions.

##  II Preliminaries and Motivating Example

In this section, we review the standard nonblocking supervisory control theory
of TDES in the Brandin-Wonham framework [8],[4, Chapter 9], and present a
motivating example for our work.

###  II-A Nonblocking Supervisory Control of TDES

First consider the untimed DES model ${\bf
G}_{act}=(A,\Sigma_{act},\delta_{act},a_{0},A_{m})$; here $A$ is the finite
set of activities, $\Sigma_{act}$ the finite set of events,
$\delta_{act}:A\times\Sigma_{act}\to A$ the (partial) transition function,
$a_{0}\in A$ the initial activity, and $A_{m}\subseteq A$ the set of marker
activities. Let $\mathbb{N}$ denote the set of natural numbers
$\\{0,1,2,...\\}$, and introduce _time_ into ${\bf G}_{act}$ by assigning to
each event $\sigma\in\Sigma_{act}$ a lower bound $l_{{\bf
G},\sigma}\in\mathbb{N}$ and an upper bound $u_{{\bf
G},\sigma}\in\mathbb{N}\cup\\{\infty\\}$, such that $l_{{\bf G},\sigma}\leq
u_{{\bf G},\sigma}$. Also introduce a distinguished event, written $tick$, to
represent “tick of the global clock”. Then a TDES model

${\bf G}:=(Q,\Sigma,\delta,q_{0},Q_{m}),$ (1)

is constructed from ${\bf G}_{act}$ (the detailed construction rules are
referred to [8], [4, Chapter 9] for detailed construction) such that $Q$ is
the finite set of _states_ , $\Sigma:=\Sigma_{act}\dot{\cup}\\{tick\\}$ the
finite set of events, $\delta:Q\times\Sigma\rightarrow Q$ the (partial) state
transition function, $q_{0}$ the initial state, and $Q_{m}$ the set of marker
states.

Let $\Sigma^{*}$ be the set of all finite strings of elements in
$\Sigma=\Sigma_{act}\dot{\cup}\\{tick\\}$, including the empty string
$\epsilon$. The transition function $\delta$ is extended to
$\delta:Q\times\Sigma^{*}\rightarrow Q$ in the usual way. The closed behavior
of $\bf G$ is the language $L({\bf G}):=\\{s\in\Sigma^{*}|\delta(q_{0},s)!\\}$
and the marked behavior is $L_{m}({\bf G}):=\\{s\in L({\bf
G})|\delta(q_{0},s)\in Q_{m}\\}\subseteq L({\bf G})$. Let
$K\subseteq\Sigma^{*}$ be a language; its prefix closure is
$\overline{K}:=\\{s\in\Sigma^{*}|(\exists t\in\Sigma^{*})~{}st\in K\\}$. $K$
is said to be $L_{m}({\bf G})$-closed if $\overline{K}\cap L_{m}({\bf G})=K$.

For TDES $\bf G$ as in (1), a state $q\in Q$ is _reachable_ if there is a
string $s\in L({\bf G})$ such that $q=\delta(q_{0},s)$; state $q\in Q$ is
_coreachable_ if there is a string $s\in\Sigma^{*}$ such that $\delta(q,s)!$
and $\delta(q,s)\in Q_{m}$. We say that ${\bf G}$ is _nonblocking_ if every
reachable state in ${\bf G}$ is coreachable. In fact ${\bf G}$ is
_nonblocking_ if and only if $\overline{L_{m}({\bf G})}=L({\bf G})$.

A TDES $\bf G$ can be graphically represented by both its activity transition
graph (ATG), namely the ordinary transition graph of ${\bf G}_{act}$, and its
timed transition graph (TTG), namely the ordinary transition graph of $\bf G$,
incorporating the $tick$ transition explicitly.

To use TDES $\bf G$ in (1) for supervisory control, first designate a subset
of events, denoted by $\Sigma_{hib}\subseteq\Sigma_{act}$, to be the
prohibitible events which can be disabled by an external supervisor. Next, and
specific to TDES, specify a subset of forcible events, denoted by
$\Sigma_{for}\subseteq\Sigma_{act}$, which can preempt the occurrence of event
$tick$.

Now it is convenient to define the controllable event set
$\Sigma_{c}:=\Sigma_{hib}~{}\dot{\cup}~{}\\{tick\\}$. The uncontrollable event
set is $\Sigma_{uc}:=\Sigma\setminus\Sigma_{c}$. A supervisory control for
$\bf G$ is any map $V:L({\bf G})\rightarrow\Gamma$, where
$\Gamma:=\\{\gamma\subseteq\Sigma\mid\gamma\supseteq\Sigma_{uc}\\}$. Then the
closed-loop system is denoted by $V/{\bf G}$, with closed behavior $L(V/{\bf
G})$ defined as follows:

$\displaystyle\mbox{(i) }\epsilon\in L(V/{\bf G});$ $\displaystyle\mbox{(ii)
}s\in L(V/{\bf G})\ \&\ \sigma\in V(s)\ \&\ s\sigma\in L({\bf G})\Rightarrow$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}s\sigma\in
L(V/{\bf G});$ $\displaystyle\mbox{(iii) no other strings belong to }L(V/{\bf
G}).$

On the other hand, for any sublanguage $K\subseteq L_{m}({\bf G})$, the
closed-loop system’s marked behavior $L_{m}(V/{\bf G})$ is given by111With
this definition of $L_{m}(V/{\bf G})$, the supervisory control $V$ is also
known as a marking supervisory control for $(K,{\bf G})$ [4].

$\displaystyle L_{m}(V/{\bf G}):=K\cap L(V/{\bf G}).$

The closed behavior $L(V/{\bf G})$ represents the strings generated by the
plant ${\bf G}$ under the control of $V$, while the marked behavior
$L_{m}(V/{\bf G})$ represents the strings that have some special significance,
for instance representing ‘task completion’. We say that $V$ is nonblocking if

$\displaystyle\overline{L_{m}(V/{\bf G})}=L(V/{\bf G}).$ (2)

A sublanguage $K\subseteq L_{m}({\bf G})$ is controllable if, for all
$s\in\overline{K}$,

$\displaystyle Elig_{K}(s)\supseteq\left\\{\begin{array}[]{lcl}Elig_{\bf
G}(s)\cap(\Sigma_{uc}\dot{\cup}\\{tick\\})\\\
~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{if}~{}~{}Elig_{K}(s)\cap\Sigma_{for}=\emptyset,\\\
Elig_{\bf G}(s)\cap\Sigma_{uc}\\\
~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{if}~{}~{}Elig_{K}(s)\cap\Sigma_{for}\neq\emptyset,\end{array}\right.$

where $Elig_{\bf G}(s):=\\{\sigma\in\Sigma|s\sigma\in L({\bf G})\\}$ and
$Elig_{K}(s):=\\{\sigma\in\Sigma|s\sigma\in\overline{K}\\}$ are the subset of
eligible events after string $s$ in $L({\bf G})$ and $K$ respectively.

The following is a central result of nonblocking supervisory control theory
[8, 4].

###### Theorem 1

Let $K\subseteq L_{m}({\bf G})$, $K\neq\emptyset$. There exists a nonblocking
(marking) supervisory control $V$ (for $(K,{\bf G})$) such that $L_{m}(V/{\bf
G})=K$ if and only if $K$ is controllable. Moreover, if such a nonblocking
supervisory control $V$ exists, then it may be implemented by a nonblocking
supervisor222$\bf SUP$ need not be a (strict) TDES as defined in (1). It can
be any automaton whose event set contains $tick$. ${\bf SUP}$, i.e.
$L_{m}({\bf SUP})=L_{m}(V/{\bf G})$. $\diamond$

Further, the property of language controllability is closed under set union.
Hence for any language $K\subseteq L_{m}({\bf G})$ (whether or not
controllable), the set $\mathcal{C}(K)=\\{K^{\prime}\subseteq K\mid
K^{\prime}~{}\text{is controllable wrt.}~{}{\bf G}\\}$ contains a unique
supremal element denoted by $\sup\mathcal{C}(K)$. Whenever
$\sup\mathcal{C}(K)$ is nonempty, by Theorem 1 there exists a nonblocking
supervisory control $V_{\sup}$ that satisfies $L_{m}(V_{\sup}/{\bf
G})=\sup\mathcal{C}(K)$ and may be implemented by a nonblocking supervisor
${\bf SUP}$ with $L_{m}({\bf SUP})=L_{m}(V_{\sup}/{\bf G})$.

###  II-B Motivating Example

Nonblockingness of supervisory control $V$ describes a general requirement
that every string generated by the closed-loop system $V/{\bf G}$ can be
completed to a marked string in indefinite (finite but unbounded) number of
transitions, which may include indefinite number of $ticks$. Namely, the time
needed for completing a task is unbounded. However, in many real-world
applications, it is often required that a task be completed in a prescribed,
bounded time. As an illustration, we present the following example (adapted
from Example 1 in [17]).

Figure 1: Routes of the vehicle

###### Example 1

Consider an autonomous vehicle for package collecting and delivery in a local
region. The vehicle can move in five zones numbered 0–4, following the routes
displayed in Fig. 1. Zone 0 is the charging area for the vehicle to charging
its battery. Zones 1 and 2 are two service areas for customers where the
customers can both receive packages from the vehicle and call the vehicle to
come to collect packages to be sent. Zones 3 and 4 are the storage areas for
incoming and outgoing packages. Namely, the task of the vehicle is to send
packages in the storage areas (zones 3 and 4) to the service areas (zones 1
and 2), and collect packages from the service areas and store them into the
storage areas. Also, the vehicle must be able to make a self-charging when it
is running out of battery.

Each movement of the vehicle from one zone to the next is represented by two
timed events: one represents the leaving from one zone and the other
represents the arriving to the next. Both of the two events have lower and
upper bound. For one example, assuming that the lower and upper bounds for the
vehicle leaving from zone 1 for zone 0 are 1 ($ticks$) and $\infty$
respectively and one time unit (a $tick$) represents 2 minutes, the vehicle
may start to move from zone 1 at any time after 1 $tick$ elapsed. For another
example, assuming that the lower and upper bounds for the vehicle arriving
zone 0 from zone 1 are 1 ($ticks$) and 2 respectively, the vehicle may arrive
zone 0 in 1 or 2 $ticks$ if it has left zone 1. Similarly, we assign lower and
upper times bounds to other timed events, as displayed in Table I.

TABLE I: Event representations of each vehicle route, and the corresponding lower and upper bounds. Notation: $Zi$ ($i=0,1,2,3,4,5$) represents zone $i$. route | event label | (lower bound, upper bound)
---|---|---
Leave $Z0$ for $Z1$ | 1 |  (1,$\infty$)
Arrive $Z1$ from $Z0$ | 2 | (1,1)
Leave $Z1$ for $Z0$ | 11 |  (0,$\infty$)
Arrive $Z0$ from $Z1$ | 12 | (1,1)
Leave $Z1$ for $Z2$ | 13 |  (0,$\infty$)
Arrive $Z2$ from $Z1$ | 14 | (1,2)
Leave $Z1$ for $Z4$ | 15 |  (0,$\infty$)
Arrive $Z4$ from $Z1$ | 16 | (1,1)
Leave $Z2$ for $Z1$ | 21 |  (0,$\infty$)
Arrive $Z1$ from $Z2$ | 22 | (1,2)
Leave $Z2$ for $Z3$ | 23 |  (0,$\infty$)
Arrive $Z3$ from $Z2$ | 24 | (1,1)
Leave $Z3$ for $Z1$ | 31 |  (0,$\infty$)
Arrive $Z1$ from $Z3$ | 32 | (1,2)
Leave $Z3$ for $Z2$ | 33 |  (0,$\infty$)
Arrive $Z2$ from $Z3$ | 34 | (1,1)
Leave $Z3$ for $Z4$ | 35 |  (0,$\infty$)
Arrive $Z4$ from $Z3$ | 36 | (1,2)
Leave $Z4$ for $Z0$ | 41 |  (0,$\infty$)
Arrive $Z0$ from $Z4$ | 42 | (2,2)
Leave $Z4$ for $Z1$ | 43 |  (0,$\infty$)
Arrive $Z1$ from $Z4$ | 44 | (1,1)
Leave $Z4$ for $Z3$ | 45 |  (0,$\infty$)
Arrive $Z3$ from $Z4$ | 46 | (1,1)

We model the movement of the autonomous vehicle by a ATG ${G}_{act}$ with
transition graph displayed in Fig. 2. States 0 (charging area Z0), 2 and 5
(service areas Z1 and Z2) are chosen to be the marker states, and the reaching
of marker states represents that the vehicle arrives the corresponding areas.
The TDES model of the vehicle can be generated according to the construction
rules in [8, 4]; its transition graph is displayed as in Fig. 3. Assume that
events 1, 11, 13, 15, 21, 23, 31, 33, 35, 41, 43 and 45 are both prohibitible
and forcible.

Figure 2: Activity transition graph (ATG) of the vehicle Figure 3: Timed
transition graph (TTG) of the vehicle (including all the transitions) and
transition graph of $\bf SUP$ (not including the transitions and states with
dashed lines)

Suppose that due to road maintenance, the (directed) route

zone 3 $\rightarrow$ zone 4 $\rightarrow$ zone 1

is not usable. This constraint is imposed as a specification. To satisfy this
specification, a nonblocking supervisory control can be synthesized [8, 4],
and implemented by a nonblocking supervisor SUP as displayed in Fig. 3. This
${\bf SUP}$ needs to disable event 35 at state 22 (zone 3), and event 43 at
state 12 (zone 4). Moreover, since ${\bf SUP}$ is nonblocking, every reachable
state can reach the marker states 0, 4, 11 (representing zones 0, 1 and 2
respectively) in finite number of $ticks$.

Now consider two additional requirements:

  1. (i)

Every package sent to customers must be delivered by the vehicle to either one
of the two service areas (zone 1 or 2) within 10 minutes (5 $ticks$); and
whenever a customer calls for package collection, the vehicle must reach zone
1 or 2 within 10 minutes;

  2. (ii)

The vehicle must be able to return to zone 0 for charging its battery within
18 minutes (9 $ticks$).

The nonblocking supervisor $\bf SUP$ in Fig. 3 fails to fulfill this
requirement, because if the vehicle is at zone 3, it is not guaranteed that
the vehicle can move to zone 1 in 5 $ticks$. Moreover, the quantitatively
nonblocking supervisory control algorithms proposed in [17] also cannot
directly synthesize a supervisor satisfying the above requirement, because the
$N_{i}$-step transitions include not only $tick$-transitions, but also other
non-$tick$-transitions, and the algorithm will cause the behavior of the
vehicle being too restrictive. Hence intuitively we need a new method that can
quantify the time (number of $ticks$) needed for completing each task, and
design a supervisor to satisfy the time-quantitative requirement. This is the
motivation for our study in this work.

##  III Time-Quantitatively Nonblocking Supervisory Control Problem
Formulation

We start by introducing a new concept that quantifies the nonblocking property
of an automaton.

Let ${\bf G}=(Q,\Sigma,\delta,q_{0},Q_{m})$ be a TDES (modelling the plant to
be controlled) as in (1) and assume that ${\bf G}$ is nonblocking (i.e. every
reachable state of ${\bf G}$ is also coreachable). Bring in a partition
$\mathcal{Q}_{\bf G}$ on the marker state set $Q_{m}$ as follows:

$\displaystyle\mathcal{Q}_{\bf G}:=\\{Q_{m,i}\subseteq
Q_{m}|i\in\mathcal{I}\\}.$ (4)

Here $\mathcal{I}$ is an index set, $Q_{m,i}\neq\emptyset$ for each
$i\in\mathcal{I}$, $Q_{m,i}\cap Q_{m,j}=\emptyset$ for all $i\neq j$, and
$\bigcup\\{Q_{m,i}|i\in\mathcal{I}\\}$ $=Q_{m}$. This partition
$\mathcal{Q}_{\bf G}$ represents a classification of different types of marker
states. For example, the three marker states 0, 1, 2 in Example 1 can be
classified into two types: $Q_{m,1}=\\{1,2\\}$ meaning completion of a package
collecting/delivery task, whereas $Q_{m,2}=\\{0\\}$ meaning battery charging.

Fix $i\in\mathcal{I}$ and let $q\in Q\setminus Q_{m,i}$ be an arbitrary state
in $Q$ but not in $Q_{m,i}$. We define the set of all strings that lead $q$ to
$Q_{m,i}$ for the first time, namely

$\displaystyle
C(q,Q_{m,i}):=\\{s\in\Sigma^{*}|\delta(q,s)!~{}\&~{}\delta(q,s)\in
Q_{m,i}~{}\&$ $\displaystyle(\forall
s^{\prime}\in\overline{s}\setminus\\{s\\})\delta(x,s^{\prime})\notin
Q_{m,i}\\}.$

Note that $C(q,Q_{m,i})$ may be empty even though G is nonblocking. If $q\in
Q_{m,i}$, we define $C(q,Q_{m,i}):=\\{\epsilon\\}$.

Now associate $Q_{m,i}$ with a finite positive integer $N_{i}$, and consider
an arbitrary state in $q\in Q$. Represent by $\\#s(tick)$ the number of $tick$
occurred in string $s$. We say that state $q$ is $N_{i}-tick$ coreachable
(wrt. $Q_{m,i}$) if

$\displaystyle{\rm(i)}~{}~{}$ $\displaystyle C(q,Q_{m,i})\neq\emptyset;\mbox{
and}$ $\displaystyle{\rm(ii)}~{}~{}$ $\displaystyle(\forall s\in
C(q,Q_{m,i}))~{}\\#s(tick)\leq N_{i}.$

Condition (i) requires that there exists at least one string $s\in\Sigma^{*}$
leading $q$ to a marker state in $Q_{m,i}$. Condition (ii) means that all
strings that lead $q$ to $Q_{m,i}$ for the first time include at most $N_{i}$
$ticks$. Intuitively, condition (ii) means that in the worst case, it takes
$N_{i}$ $ticks$ from state $q$ to arrive a marker state in $Q_{m,i}$. Hence if
$Q_{m,i}$ represents a task completion, then condition (ii) means that in the
worst case, it takes $N$ $ticks$ from state $q$ to complete the task.

###### Remark 1

We remark here that since a TDES $\bf G$ is _activity-loop-free_ [4] (i.e
$(\forall q\in Q)(\forall
s\in\Sigma_{act}^{*}\setminus\\{\epsilon\\})\delta(q,s)\neq q$). Thus all
loops (the strings visit a state repeatedly) will include at least one $tick$.
It is easily verified that all the automata representing the sublanguages of
$L_{m}({\bf G})$ is also activity-loop-free, and thus the automata mentioned
in this paper is activity-loop free. $\diamond$

Now we introduce the new concept of time-quantitative nonblockingness of an
automaton.

###### Definition 1

Let ${\bf G}=(Q,\Sigma,\delta,q_{0},Q_{m})$ be a TDES plant, $\mathcal{Q}_{\bf
G}=\\{Q_{m,i}|i\in\mathcal{I}\\}$ a partition on $Q_{m}$ as defined in (4),
and $N_{i}$ a positive integer associated with each
$Q_{m,i}\in\mathcal{Q}_{\bf G}$. We say that ${\bf G}$ is _time-quantitatively
nonblocking_ wrt. $\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$ if for every
$i\in\mathcal{I}$ and every reachable state $q\in Q$, $q$ is $N_{i}-tick$
coreachable (wrt. $Q_{m,i}$).

In words, a time-quantitatively nonblocking TDES (it is also an automton)
requires that every state $q$ can reach every subset $Q_{m,i}$ of marker
states within $N_{i}$ $ticks$. Compared with quantitatively nonblockingness in
[18], time-quantitatively nonblockingness only requires the time for reaching
marker states being bounded, rather than in [18] that the total number of
transitions (caused by any events) for reaching marker state are bounded.

Next we define the time-quantitatively nonblocking property of a supervisory
control $V$. For this, we first introduce a new concept called time-
quantitative completability.

Let $K\subseteq L_{m}({\bf G})$ be a sublanguage of $L_{m}({\bf G})$. For each
marker state subset $Q_{m,i}\in\mathcal{Q}_{\bf G}$ define

$L_{m,i}({\bf G}):=\\{s\in L_{m}({\bf G})|\delta(q_{0},s)\in Q_{m,i}\\}$

i.e. $L_{m,i}({\bf G})$ represents the marked behavior of ${\bf G}$ wrt.
$Q_{m,i}$. Then $K_{i}:=K\cap L_{m,i}({\bf G})$, $i\in\mathcal{I}$.

For an arbitrary string $s\in\overline{K}\setminus K_{i}$, define the set of
strings that lead $s$ to $K_{i}$ for the first time:

$\displaystyle M_{K,i}(s):=\\{t\in\Sigma^{*}\mid st\in K_{i}(\forall
t^{\prime}\in\overline{t}\setminus\\{t\\})st^{\prime}\notin K_{i}\\}.$ (5)

If already $s\in K_{i}$, we define $M_{K,i}(s):=\\{\epsilon\\}$.

###### Definition 2

Let ${\bf G}=(Q,\Sigma,\delta,q_{0},Q_{m})$ be a TDES plant, $K\subseteq
L_{m}({\bf G})$ a sublanguage, $\mathcal{Q}_{\bf
G}=\\{Q_{m,i}|i\in\mathcal{I}\\}$ a partition on $Q_{m}$ as defined in (4),
and $N_{i}$ a positive integer associated with each
$Q_{m,i}\in\mathcal{Q}_{\bf G}$. For a fixed $i\in\mathcal{I}$, we say that
$K$ is _time-quantitatively completable_ wrt. $(Q_{m,i},N_{i})$ if for all
$s\in\overline{K}$,

$\displaystyle{\rm(i)}$ $\displaystyle~{}M_{K,i}(s)\neq\emptyset;$
$\displaystyle{\rm(ii)}$ $\displaystyle~{}(\forall t\in
M_{K,i}(s))~{}\\#t(tick)\leq N_{i}.$

Moreover if $K$ is time-quantitatively completable wrt. $(Q_{m,i},N_{i})$ for
all $i\in\mathcal{I}$, we say that $K$ is time-quuantitatively completable
wrt. $\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$.

If $K$ is time-quantitatively completable wrt.
$\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$, then for every $i\in\mathcal{I}$,
every string $s\in\overline{K}$ may be extended to a string in $K_{i}(=K\cap
L_{m,i}({\bf G}))$ by strings including at most $N_{i}$ $ticks$.

The following result characterizes the relation between time-quantitative
completability of a language and time-quantitative nonblockingness of an
automaton.

###### Proposition 1

Let ${\bf G}=(Q,\Sigma,\delta,q_{0},Q_{m})$ be a TDES, $K\subseteq L_{m}({\bf
G})$ a sublanguage, $\mathcal{Q}_{\bf G}=\\{Q_{m,i}|i\in\mathcal{I}\\}$ a
partition on $Q_{m}$, and $N_{i}$ a positive integer associated with each
$Q_{m,i}\in\mathcal{Q}_{\bf G}$.

(i) If $K=L_{m}({\bf G})$ and ${\bf G}$ is time-quantitatively nonblocking
wrt. $\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$, then $K$ is time-quantitatively
completable wrt. $\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$.

(ii) If $K\subseteq L_{m}({\bf G})$ is time-quantitatively completable wrt.
$\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$, then there exists an automaton ${\bf
K}=(X,\Sigma,\xi,x_{0},X_{m})$ such that $L_{m}({\bf K})=K$ and ${\bf K}$ is
time-quantitatively nonblocking wrt. $\\{(X_{m,i},N_{i})|i\in\mathcal{I}\\}$,
where $X_{m,i}=\\{x_{m}\in X_{m}|(\exists s\in\Sigma^{*})\xi(x_{0},s)=x_{m}\
\&\ \delta(q_{0},s)\in Q_{m,i}\\}$.

The proof of Proposition 1 is similar to that of Proposition 4 in [18].
According to Proposition 1, for an arbitrary sublanguage $K\subseteq
L_{m}({\bf G})$ that is time-quantitatively completable wrt.
$\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$, we may construct a time-
quantitatively nonblocking (wrt. $\\{(X_{m,i},N_{i})|i\in\mathcal{I}\\}$)
automaton ${\bf K}$ representing $K$, i.e. $L_{m}({\bf K})=K$.

With the above time-quantitative completability of a language, we introduce
the time-quantitatively nonblocking property of a supervisory control.

###### Definition 3

Let ${\bf G}=(Q,\Sigma,\delta,q_{0},Q_{m})$ be a TDES plant, $K\subseteq
L_{m}({\bf G})$ a sublanguage, $\mathcal{Q}_{\bf
G}=\\{Q_{m,i}|i\in\mathcal{I}\\}$ a partition on $Q_{m}$ as defined in (4),
$N_{i}$ a positive integer associated with each $Q_{m,i}\in\mathcal{Q}_{\bf
G}$, and $V:L({\bf G})\rightarrow\Gamma$ a (marking) supervisory control (for
$(K,{\bf G})$). We say that $V$ is _time-quantitatively nonblocking_ wrt.
$\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$ if

$\displaystyle{\rm(i)}~{}~{}$ $\displaystyle V\text{ is nonblocking};\mbox{
and}$ $\displaystyle{\rm(ii)}~{}~{}$ $\displaystyle L_{m}(V/{\bf
G})~{}\text{is time-quantitatively completable}$ wrt.
$\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$.

In words, quantitative nonblockingness of a supervisory control $V$ requires
not only $V$ being nonblocking (in the standard sense), but also the marked
behavior $L_{m}(V/{\bf G})$ of the closed-loop system $V/{\bf G}$ being time-
quantitatively completable. According to Proposition 1, $L_{m}(V/{\bf G})$ can
be represented by a time-quantitatively nonblocking automaton.

We are ready to formulate the _Time-Quantitatively Nonblocking Supervisory
Control Problem_ of DES (TQNSCP):

Consider a TDES plant modeled by ${\bf
G}=(Q,\Sigma_{c}\dot{\cup}\Sigma_{uc},\delta,q_{0},Q_{m})$, a specification
language $E\subseteq\Sigma^{*}$, and let $K:=E\cap L_{m}({\bf G})$,
$\mathcal{Q}_{\bf G}=$ $\\{Q_{m,i}\subseteq Q_{m}|i\in\mathcal{I}\\}$ a
partition on $Q_{m}$, and $N_{i}$ a positive integer associated with each
$Q_{m,i}\in\mathcal{Q}_{\bf G}$. Construct a (marking) supervisory control
$V:L({\bf G})\rightarrow\Gamma$ (for ($K,{\bf G}$)) satisfying the following
properties:

  * $\bullet$

Safety. Marked behavior of the closed-loop system $V/{\bf G}$ satisfies the
imposed specification $E$ in the sense that $L_{m}(V/{\bf G})\subseteq E\cap
L_{m}({\bf G})$.

  * $\bullet$

Time-Quantitative nonblockingness. Supervisory control $V$ is time-
quantitatively nonblocking wrt. $\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$.

  * $\bullet$

Maximal permissiveness. Supervisory control $V$ does not restrict more
behavior than necessary to satisfy safety and quantitative nonblockingness,
i.e. for all other safe and time-quantitatively nonblocking supervisory
controls $V^{\prime}$ it holds that $L_{m}(V^{\prime}/{\bf G})\subseteq
L_{m}(V/{\bf G})$.

The TQNSCP is a variation of the the traditional nonblocking supervisory
control problem [8, 4] of TDES, in that the second requirement of time-
quantitative nonblockingness is stronger than the traditional nonblockingness.
This problem can neither be solved in general by supervisors synthesized using
the standard method (because the third requirement of maximal permissiveness
is not satisfied; an example is ${\bf SUP}$ in Example 1), nor be solved by
supervisors using the method in [17] (here only the number of occurrences of
$tick$ is bounded). In subsequent sections, we will develop new algorithms to
design supervisors satisfying the new requirement of time-quantitative
nonblockingness and resolving the TQNSCP.

##  IV Supremal Time-Quantitatively Completable Sublanguage and Its
Computation

Towards solving the TQNSCP formulated in the preceding section, we first
present a basic result which is a counterpart to Theorem 1 in [8, 4] and
Theorem 2 in [17].

###### Theorem 2

Consider a TDES plant ${\bf
G}=(Q,\Sigma_{c}\dot{\cup}\Sigma_{uc},\delta,q_{0},Q_{m})$, a partition
$\mathcal{Q}_{\bf G}=$ $\\{Q_{m,i}\subseteq Q_{m}|i\in\mathcal{I}\\}$ on
$Q_{m}$, and a positive integer $N_{i}$ associated with each
$Q_{m,i}\in\mathcal{Q}_{\bf G}$. Let $K\subseteq L_{m}({\bf G})$,
$K\neq\emptyset$. There exists a time-quantitatively nonblocking (marking)
supervisory control $V$ (for $(K,{\bf G})$) such that $L_{m}(V/{\bf G})=K$ if
and only if $K$ is controllable and time-quantitatively completable wrt.
$\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\}$. Moreover, if such a time-
quantitatively nonblocking supervisory control $V$ exists, then it may be
implemented by a time-quantitatively nonblocking automaton ${\bf QSUP}$, i.e.
$L_{m}({\bf QSUP})=L_{m}(V/{\bf G})$. $\diamond$

Theorem 2 asserts that when the $K$-synthesizing supervisory control $V$ is
required to be time-quantitatively nonblocking, it is necessary and sufficient
to require that $K$ be not only controllable but also time-quantitatively
completable. If $K$ is indeed controllable and time-quantitatively
completable, then the supervisory control $V$ in Theorem 2 is the solution to
the TQNSCP. If $K$ is either not controllable or not time-quantitatively
completable, then to achieve the third requirement of maximal permissiveness
of TQNSCP, one hopes that the supremal controllable and time-quantitatively
completable sublanguage of $K$ exists. Again the key is to investigate if for
time-quantitative completability the supremal element also exists. We provide
a positive answer below. Before we proceed, the following is a proof of
Theorem 2.

Proof of Theorem 2. We first prove the first statement. The direction of (only
if) is a direct result from Theorem 1 and Definition 3. For the direction of
(if), according to Theorem 1, since $K$ is controllable, there exists a
supervisory control $V$ such that $V$ is nonblocking and $L_{m}(V/{\bf G})=K$.
Furthermore, according to Definition 3, it is derived from $L_{m}(V/{\bf
G})=K$ being time-quantitatively completable wrt.
$\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$ that $V$ is time-quantitatively
nonblocking wrt. $\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\}$.

For the second statement, let $V$ be a time-quantitatively nonblocking
supervisory control that synthesizes a controllable and time-quantitatively
completable $K$, i.e. $L_{m}(V/{\bf G})=K$. Since $K$ is time-quantitatively
completable, it follows from Proposition 1 that there exists a time-
quantitatively nonblocking automaton ${\bf QSUP}$ such that $L_{m}({\bf
QSUP})=K=L_{m}(V/{\bf G})$. This completes the proof. $\blacksquare$

###  IV-A Supremal Time-Quantitative Completable Sublanguage

Let ${\bf G}$ be a nonblocking TDES. First, we present the following
proposition that time-quantitative language completability is closed under
arbitrary set unions.

###### Proposition 2

Consider a TDES ${\bf G}=$ $(Q,\Sigma,\delta,q_{0},Q_{m})$, a partition
$\mathcal{Q}_{\bf G}=\\{Q_{m,i}\subseteq Q_{m}|i\in\mathcal{I}\\}$ on $Q_{m}$,
and a positive integer $N_{i}$ associated with each
$Q_{m,i}\in\mathcal{Q}_{\bf G}$. Let $K_{1},K_{2}\subseteq L_{m}({\bf G})$. If
both $K_{1}$ and $K_{2}$ are time-quantitatively completable wrt.
$\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\}$, then $K:=K_{1}\cup K_{2}$ is also
time-quantitatively completable wrt.
$\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\}$.

Proof: Let $s\in\overline{K}$ and $i\in\mathcal{I}$. According to Definition
2, to show that $K$ is time-quantitatively completable, we need to show that
(i) $M_{K,i}(s)\neq\emptyset$, i.e. there exists $t\in\Sigma^{*}$ such that
$st\in K_{i}=K\cap L_{m,i}({\bf G})$, and (ii) for all $t\in M_{K,i}(s)$,
$\\#t(tick)\leq N_{i}$. Since $\overline{K}=\overline{K_{1}\cup
K_{2}}=\overline{K_{1}}\cup\overline{K_{2}}$, either $s\in\overline{K}_{1}$ or
$s\in\overline{K}_{2}$. We consider the case $s\in\overline{K}_{1}$; the other
case is similar.

We first show that (i) holds. Since $K_{1}$ is time-quantitatively
completable, $M_{K_{1},i}(s)\neq\emptyset$, i.e. there exists string $t$ such
that $st\in K_{1}\cap L_{m,i}({\bf G})\subseteq K\cap L_{m,i}({\bf G})$. Thus
(i) is established.

For (ii), let $t\in M_{K,i}(s)$; then $st\in K\cap L_{m,i}({\bf G})$ and for
all $t^{\prime}\in\overline{t}\setminus\\{t\\}$, $st^{\prime}\notin K\cap
L_{m,i}({\bf G})$. Since $K=K_{1}\cup K_{2}$, there exist the following two
cases: (a) $st\in K_{1}\cap L_{m,i}({\bf G})$ and for all
$t^{\prime}\in\overline{t}\setminus\\{t\\}$, $st^{\prime}\notin K\cap
L_{m,i}({\bf G})$; (b) $st\in K_{2}\cap L_{m,i}({\bf G})$ and for all
$t^{\prime}\in\overline{t}\setminus\\{t\\}$, $st^{\prime}\notin K\cap
L_{m,i}({\bf G})$. For case (a), it follows from $K\supseteq K_{1}$ that
$st^{\prime}\notin K_{1}\cap L_{m,i}({\bf G})$, so $t\in M_{K_{1},i}(s)$.
Since $K_{1}$ is time-quantitatively completable, it holds that
$\\#t(tick)\leq N_{i}$. The same conclusion holds for case (b) by a similar
argument on $K_{2}$. Hence (ii) is established.

With (i) and (ii) as shown above, we conclude that $K$ is time-quantitatively
completable. $\blacksquare$

Now for a given sublanguage $K\subseteq L_{m}({\bf G})$, whether or not $K$ is
time-quantitatively completable wrt.
$\\{({{Q}_{m,i}},N_{i})|i\in\mathcal{I}\\}$, let

$\displaystyle{\mathcal{TQC}}(K,\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\}):=\\{K^{\prime}\subseteq
K\mid K^{\prime}$ $\displaystyle\text{is time-quantitatively completable
wrt.}\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\}\\}$

represent the set of sublanguages of $K$ that are time-quantitatively
completable wrt. $\\{({{Q}_{m,i}},N_{i})|i\in\mathcal{I}\\}$. Note from
Definition 2 that the empty language $\emptyset$ is trivially time-
quantitatively completable, so $\emptyset\in$
${\mathcal{TQC}}(K,\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\})$ always holds.
Moreover, it follows from Proposition 2 that there exists the supremal time-
quantitatively completable sublanguage of $K$ wrt.
$\\{({{Q}_{m,i}},N_{i})|i\in\mathcal{I}\\}$, given by

$\displaystyle\sup\mathcal{TQC}(K,$
$\displaystyle\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\}):=\bigcup\\{K^{\prime}\mid$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}K^{\prime}\in\mathcal{TQC}(K,\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\})\\}.$

To compute this
$\sup\mathcal{TQC}(K,\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\})$, we proceed as
follows. Fix $i\in\mathcal{I}$ and let

$\displaystyle{\mathcal{TQC}}$
$\displaystyle(K,({Q_{m,i}},N_{i})):=\\{K^{\prime}\subseteq K\mid K^{\prime}$
$\displaystyle~{}~{}~{}~{}~{}~{}\text{is quantitatively completable
wrt.}({Q_{m,i}},N_{i})\\}$

be the set of all quantitatively completable sublanguage of $K$ wrt.
$({Q_{m,i}},N_{i})$ (Definition 2). By the same reasoning as above, we have
that $\sup\mathcal{TQC}(K,({Q_{m,i}},N_{i}))$ exists. The idea of our
algorithm design is to first compute $\sup\mathcal{TQC}(K,({Q_{m,i}},N_{i}))$
for a fixed $i\in\mathcal{I}$, and then iterate over all $i\in\mathcal{I}$
until fixpoint in order to compute
$\sup\mathcal{TQC}(K,\\{({Q_{m,i}},N_{i})|i\in\mathcal{I}\\})$. In the next
subsection, we present an automaton-based algorithm to compute
$\sup\mathcal{TQC}(K,(Q_{m,i},N_{i}))$ for any given language $K\subseteq
L_{m}({\bf G})$.

###  IV-B Automaton-Based Computation of
$\sup\mathcal{QC}(K,({Q_{m,i}},N_{i}))$

Consider a language $K\subseteq L_{m}({\bf G})$ and $({Q_{m,i}},N_{i})$ for a
fixed $i\in\mathcal{I}$. We present an algorithm to compute the supremal time-
quantitative completable sublanguage $\sup\mathcal{TQC}(K,({Q_{m,i}},N_{i}))$.
The intuition is that we find for each prefix of $\overline{K}$ the time-
quantitatively completable strings, and remove other non-time-quantitatively
completable strings from the transition graph. The detailed steps are
described in Algorithm 1. In the algorithm, we employ a last-in-first-out
stack $ST$ to store the states to be processed (a first-in-first-out queue can
also be used instead to perform a different order of search), and for a set
$Z$ a flag $F:Z\rightarrow\\{true,false\\}$ to indicate whether or not an
element of $Z$ has been visited: i.e. $F(z)=true$ iff $z\in Z$ has been
visited.

Algorithm 1 : Algorithm of Computing $\sup\mathcal{TQC}(K,(Q_{m,i},$ $N_{i}))$

Input: TDES ${\bf G}=(Q,\Sigma,\delta,q_{0},Q_{m})$, language $K\subseteq
L_{m}({\bf G})$, subset $Q_{m,i}\subseteq Q_{m}$ of marker states, and
positive integer $N_{i}$.
Output: Language $K_{i}^{\prime}$.

Step 1. Construct an automaton ${\bf K}_{i}=(X_{i},\Sigma,\xi_{i},x_{i,0},$
$X_{i,m})$ to represent $K_{i}=K\cap L_{m,i}({\bf G})$. If $K_{i}=\emptyset$,
output language $K_{i}^{\prime}=\emptyset$; otherwise go to Step 2.

Step 2. Let

$X_{i}^{\prime}:=\\{(x_{i},d)|x_{i}\in X_{i},d\in\\{0,...,N_{i}\\}\\},$

$\xi_{i}^{\prime}=\emptyset$, $x_{i,0}^{\prime}=(x_{i,0},0)$, and
$X_{i,m}^{\prime}:=\\{(x_{i},0)|x_{i}\in X_{i,m}\\}$. Initially set
$F((x_{i},d))=false$ for each state $x_{i}\in X_{i}$ and each
$d\in\\{0,...,N_{i}-1\\}$. Then push the initial state
$x_{i,0}^{\prime}=(x_{i,0},0)$ into stack $ST$, and set $F((x_{i,0},0))=true$.

Step 3. If stack $ST$ is empty, trim333‘Trimmed’ means that all non-reachable
and non-coreachable states (if they exist) are removed [16, 4]. The generator
${\bf K}^{\prime}$ need not be trim, and to get a nonblocking generator, this
step of trimming is required.  the automaton ${\bf
K}_{i}^{\prime}=(X_{i}^{\prime},\Sigma,\xi_{i}^{\prime},x^{\prime}_{i,0},X_{i,m}^{\prime})$,
and go to Step 6. Otherwise, pop out the top element $(x_{i,j},d)$ of stack
$ST$. If $x_{i,j}\in X_{i,m}$, go to Step 4; otherwise, go to Step 5.

Step 4. For each event $\sigma\in\Sigma$ defined at state $x_{i,j}$ (i.e.
$\xi(x_{i,j},\sigma)!$), let $x_{i,k}:=\xi(x_{i,j},\sigma)$ and do the
following two steps 4.1 and 4.2; then go to Step 3 with updated stack $ST$.
Step 4.1 Add transition $((x_{i,j},0),\sigma,(x_{i,k},0))$ to $\xi^{\prime}$,
i.e.

$\xi_{i}^{\prime}:=\xi_{i}^{\prime}\cup\\{((x_{i,j},0),\sigma,(x_{i,k},0))\\}.$

Step 4.2 If $F((x_{i,k},0))=false$, push $(x_{i,k},0)$ into stack $ST$ and set
$F((x_{i,k},0))=true$.

Step 5. For each event $\sigma\in\Sigma$ defined at state $x_{i,j}$ (i.e.
$\xi(x_{i,j},\sigma)!$), do the following three steps 5.1–5.3; then go to Step
3 with updated stack $ST$.
Step 5.1 Let $x_{i,k}:=\xi_{i}(x_{i,j},\sigma)$. If $\sigma=tick$, set
$d^{\prime}=d+1$; If $\sigma\neq tick$ and $x_{i,k}\in X_{i,m}$, set
$d^{\prime}=0$; if $\sigma\neq tick$ and $x_{i,k}\notin X_{i,m}$, set
$d^{\prime}=d$.
Step 5.2 If $d^{\prime}>N_{i}$, go to Step 5.1 with the next event $\sigma$
defined at $x_{i,j}$. Otherwise, add a new transition
$((x_{i,j},d),\sigma,(x_{i,k},d^{\prime}))$ to $\xi^{\prime}$, i.e.

$\xi_{i}^{\prime}:=\xi_{i}^{\prime}\cup\\{((x_{i,j},d),\sigma,(x_{i,k},d^{\prime}))\\}$

Step 5.3 If $F((x_{i,k},d^{\prime}))=false$, push $(x_{i,k},d^{\prime})$ into
stack $ST$ and set $F((x_{i,k},d^{\prime}))=true$.

Step 6. Output the language $K_{i}^{\prime}=K\cap L({\bf K}_{i}^{\prime})$.

In Step 5.2 of Algorithm 1 above, note that the condition $d^{\prime}>N_{i}$
means that the downstream transitions including more than $N_{i}$ $ticks$ that
have never reached a marker state in $Q_{m,i}$ will be removed, therefore
guaranteeing that from an arbitrary state, at most $N_{i}$ $ticks$ are needed
to reach a marker state in $Q_{m,i}$.

Note that there are two differences between the above new Algorithm 1 and the
algorithm in [17] of computing supremal quantitatively completable language.
The first difference is the definition of $X_{i}^{\prime}$. In the new
algorithm, we have $X_{i}^{\prime}:=\\{(x_{i},d)|x_{i}\in
X_{i},d\in\\{0,...,N_{i}\\}\\}$, namely, $d$ is in the range of $[0,N_{i}]$,
rather than $[0,N_{i}-1]$ in the Algorithm 1 in [17]. The reason is
illustrated in Fig. 4.

Figure 4: Illustration on the reason for defining $d\in[0,N_{i}]$ in
$X_{i}^{\prime}$. Assume that the top subfigure represents partial transition
functions of an automaton ${\bf K}_{i}$ and let $N_{i}=2$. In the process of
constructing ${\bf K}_{i}^{\prime}$ (as represented by the bottom subfigure)
by Algorithm 1, from state (2,1) to state (5,2), $d=1$ is advanced to
$d^{\prime}=2$ since $\sigma=tick$. In the algorithm in [17] of computing the
supremal quantitatively completable sublanguage, since state 5 is not a marker
state, this transition will be removed. However, since the downstream string
$\alpha.\beta$ will lead the automaton to marker state 8 (where $d^{\prime}$
will be set to 0) and the total number of occurred $ticks$ is no more than 2
$ticks$, such states and transitions should be reserved. Thus in Algorithm 1,
by Step 5.2 the states with $d^{\prime}=N_{i}$ are included in ${\bf
K}_{i}^{\prime}$. Also by this step, the states with $d^{\prime}$ larger than
2 are removed from ${\bf K}_{i}$; e.g., transition $(6,tick,7)$ is removed by
Step 5.2 because now $d^{\prime}=3>N_{i}$ (as represented by the dashed lines
in the transition graph of ${\bf K}_{i}^{\prime}$).

The second difference is the rules for updating $d$ at Step 5.1: in the new
algorithm, only when $\sigma=tick$ will $d^{\prime}$ be set to $d+1$. The
reason is that only the $tick$ transitions are counted for satisfying time-
quantitative completability; while in Algorithm 1 in [17], all the transitions
not reaching marker states are counted.

Now we present an example to illustrate Algorithm 1.

######  Example 2 (Continuing Example 1)

Inputting TDES ${\bf G}$, language $K=L_{m}({\bf SUP})$, marker state subset
${Q_{m,1}}=\\{1,2\\}\subseteq Q_{m}$ and positive integer $N_{1}=5$, Algorithm
1 generates a trimmed automaton ${\bf TSUP}_{1}$, as displayed in Fig. 5.

From Fig. 5, we observe that the the algorithm will terminate the search
before the sixth $tick$ occurs. Every reachable states are guaranteed to reach
the marker states (4,0) and (11,0) in at most 5 $ticks$. By contrast in ${\bf
SUP}$ (displayed in Fig. 3), the strings $(tick)^{5}.1.tick.2$ will lead state
0 to the marker state (4,0); however, they include more than 5 $ticks$. Thus,
in fact those strings are removed from ${\bf SUP}$ by Algorithm 1. Also, the
states and the transitions that cannot reach marker state are removed by the
trim operation at Step 3. $\diamond$

Figure 5: Transition graph of ${\bf TSUP}_{1}$

The correctness of Algorithm 1 is confirmed by the following theorem.

###### Theorem 3

Given a TDES plant $\bf G$, a sublanguage $K\subseteq L_{m}({\bf G})$, subset
$Q_{m,i}\subseteq Q_{m}$ of marker states, and positive integer $N_{i}$, let
$K_{i}^{\prime}$ be the language returned by Algorithm 1. Then
$K_{i}^{\prime}=\sup\mathcal{QC}(K,({Q_{m,i}},N_{i}))$.

Proof: First, we prove that $K_{i}^{\prime}\in\mathcal{TQC}(K,N)$. We start by
showing that $K_{i}^{\prime}\subseteq K$, which can be directly obtained by
Step 6.

Next we show that $K_{i}^{\prime}$ is time-quantitative completable wrt.
$(Q_{m,i},N_{i})$. For this, let ${\bf
K}_{i}^{\prime}=(X_{i}^{\prime},\Sigma,\xi_{i}^{\prime},x_{i,0}^{\prime},$
$X_{i,m}^{\prime})$ be the generalized TDES generated by Step 3 of Algorithm
1. According to Step 6, it is easily verified that
$\overline{K_{i}^{\prime}}=L({\bf K}_{i}^{\prime})$ and $K_{i}^{\prime}\cap
L_{m,i}({\bf G})=L_{m}({\bf K}_{i}^{\prime})\cap L_{m,i}({\bf G})$ (because
$K_{i}^{\prime}\cap L_{m,i}({\bf G})=K\cap L({\bf K}_{i}^{\prime})\cap
L_{m,i}({\bf G})=L_{m}({\bf K}_{i})\cap L({\bf K}_{i}^{\prime})\cap
L_{m,i}({\bf G})=L_{m}({\bf K}_{i}^{\prime})\cap L_{m,i}({\bf G})$. Let
$s\in\overline{K_{i}}^{\prime}$, then $s\in\overline{K}$ and $s\in L({\bf
K}_{i}^{\prime})$; then there exists $t\in\Sigma^{*}$ such that $st\in
L_{m}({\bf K}_{i}^{\prime})$, i.e. $st\in K_{i}^{\prime}\cap L_{m,i}({\bf
G})$. According to the definition of $M_{K_{i}^{\prime},i}(s)$,
$M_{K_{i}^{\prime},i}(s)\neq\emptyset$; namely, condition (i) of time-
quantitatively completability is satisfied. Furthermore, according to the
definition of $M$ in (5) and $K_{i}^{\prime}\cap L_{m,i}({\bf G})=L_{m}({\bf
K_{i}}^{\prime})\cap L_{m,i}({\bf G})$, for each $t\in
M_{K_{i}^{\prime},i}(s)$, $t\in M_{L_{m}({\bf K}_{i}^{\prime}),i}(s)$. It is
guaranteed by $d^{\prime}>N_{i}$ in Step 5.2 that if a string includes more
than $N_{i}$ $ticks$ and has not reached a marker state in $Q_{m,i}$, it will
not be added to $L({\bf K}_{i}^{\prime})$. In other words, those strings $st$
added to $L({\bf K}_{i}^{\prime})$ must satisfy that for every $t\in
M_{L_{m}({\bf K}_{i}^{\prime}),i}(s)$, there holds $\\#t(tick)\leq N_{i}$.
Namely, condition (ii) of time-quantitatively completability is also
satisfied. Hence, $K_{i}^{\prime}$ is time-quantitative completable wrt.
$(Q_{m,i},N_{i})$. This establishes that
$K_{i}^{\prime}\in\mathcal{TQC}(K,(Q_{m,i},N_{i}))$.

It remains to show that $K_{i}^{\prime}$ is the largest element in
$\mathcal{TQC}(K,(Q_{m,i},N_{i}))$. Let $M$ be another element in
$\mathcal{TQC}(K,(Q_{m,i},N_{i}))$, i.e.
$M\in\mathcal{TQC}(K,(Q_{m,i},N_{i}))$. It will be shown that $M\subseteq
K_{i}^{\prime}$. For this, we first prove that
$\overline{M}\subseteq\overline{K_{i}^{\prime}}=L({\bf K}_{i}^{\prime})$ by
induction on the length of a string $s\in\overline{M}$.

Base case: Let $s=\epsilon\in\overline{M}$. Then $\epsilon\in\overline{K}$ and
the initial state $x_{0}$ exists in ${\bf K}_{i}$. It follows from Step 1 that
$x_{i,0}^{\prime}=(x_{i,0},0)$ is designated to be the initial state of ${\bf
K}_{i}^{\prime}$, and hence $\epsilon\in L({\bf K}_{i}^{\prime})$.

Inductive case: Let $s\in\overline{M}$, $s\in L({\bf K}_{i}^{\prime})$,
$\sigma\in\Sigma$, and suppose that $s\sigma\in\overline{M}$; we will show
that $s\sigma\in L({\bf K}_{i}^{\prime})$ as well. Since
$M\in\mathcal{TQC}(K,(Q_{m,i},N_{i}))$, we have (i) $M\subseteq K$ and (ii)
$M$ is time-quantitative completable wrt $(Q_{m,i},N_{i})$. It follows from
(i) that $s\in K\cap L({\bf G})=L({\bf K}_{i})$, i.e. $\xi_{i}(x_{i,0},s)!$.
By the same reason, $\xi_{i}(x_{i,0},s\sigma)!$. Letting
$x_{i}=\xi_{i}(x_{i,0},s)$, we derive $\xi_{i}(x_{i},\sigma)!$. Since $s\in
L({\bf K}_{i}^{\prime})$, $\xi_{i}^{\prime}((x_{i,0},0),s)!$. According to the
definition of $\xi_{i}^{\prime}$, there must exist $d\in\\{0,...,N_{i}\\}$
such that $(x_{i},d)=\xi_{i}^{\prime}((x_{i,0},0),s)$. We already know that
$\xi_{i}(x_{i},\sigma)!$. If $x_{i}\in X_{i,m}$, according to Step 4,
$\xi_{i}^{\prime}((x_{i},d),\sigma)$ with $d=0$ is defined. If $x_{i}\notin
X_{i,m}$, according to Step 5.1, there may exist the following three cases:
(a) $\sigma=tick$; (b) $\sigma\neq tick$ and $\xi_{i}(x_{i},\sigma)\in
X_{i,m}$; (c) $\sigma\neq tick$ and $\xi_{i}(x_{i},\sigma)\notin X_{i,m}$.
First, in case (a), $d^{\prime}=d+1$. According to Step 5.2,
$d^{\prime}>N_{i}$ or $d^{\prime}\leq N_{i}$. The former is impossible because
in that case $s\notin M$ (since $x_{i}\notin X_{i,m}$, $s\notin K$ or $s\notin
L_{m,i}({\bf G})$; in both cases, $s\notin M$) but $s.tick\in\overline{M}$
will imply that it needs at least $N_{i}+1$ $ticks$ to lead $\overline{M}$ to
$M$, which contradicts to the assumption that $M$ is time-quantitative
completable $(Q_{m,i},N_{i})$. When $d^{\prime}\leq N_{i}$,
$\xi^{\prime}((x,d),\sigma)$ is defined with $d^{\prime}\leq N_{i}$. For case
(b), $d^{\prime}=0$, according to Step 5.2, $\xi^{\prime}((x,d),\sigma)$ is
defined with $d^{\prime}=0$. For case (c), $\xi^{\prime}((x,d),\sigma)$ is
defined with $d\leq N$ and thus $d^{\prime}=d\leq N_{i}$. For case (d),
$\xi^{\prime}((x,d),\sigma)$ is defined with $d^{\prime}=d\leq N$. Hence, we
conclude that $\xi_{i}^{\prime}((x_{i},d),\sigma)$ is defined, i.e.
$s\sigma\in L({\bf K}_{i}^{\prime})$.

Therefore, by the above induction, $\overline{M}\subseteq L({\bf
K}_{i}^{\prime})$ is established. So, we have

$\displaystyle M$ $\displaystyle\subseteq\overline{M}\cap
K~{}~{}~{}(\text{by}~{}M\in\mathcal{TQC}(K,(Q_{m,i},N_{i})))$
$\displaystyle\subseteq L({\bf K}_{i}^{\prime})\cap K~{}~{}~{}(\text{according
to Step 6})$ $\displaystyle\subseteq K_{i}^{\prime}.$

The proof is now complete. $\blacksquare$

The above theorem confirms that Algorithm 1 computes the supremal time-
quantitatively completable sublanguage $\sup\mathcal{QC}(K,(Q_{m,i}))$. The
time complexity of Algorithm 1 is $O(|Q|\cdot|X|\cdot|\Sigma|\cdot N_{i})$
where $|Q|$ and $|X|$ are the states number of TDES ${\bf G}$ and automaton
representing $K$ respectively. This complexity is derived according to Steps 3
to 5, because ${\bf K}_{i}$ has at most $|Q|\cdot|X|\cdot|\Sigma|$ transitions
and each transitions are visited at most $N_{i}$ times.

##  V Maximally Permissive Time-Quantitatively Nonblocking Supervisory Control

In this section, we present our solution to the TQNSCP. Consider a TDES plant
modeled by ${\bf G}=(Q,\Sigma_{c}\dot{\cup}\Sigma_{uc},\delta,q_{0},Q_{m})$,
and a specification language $E\subseteq\Sigma^{*}$. Let $K:=E\cap L_{m}({\bf
G})$, $\mathcal{Q}_{\bf G}=\\{Q_{m,i}|i\in\mathcal{I}\\}$ be a partition on
$Q_{m}$, and a positive integer $N_{i}$ associated with each
$Q_{m,i}\in\mathcal{Q}_{\bf G}$.

Whether or not $K$ is controllable and time-quantitatively completable, let
$\mathcal{CTQC}(K,{\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}})$ be the set of
sublanguages of $K$ that are both controllable and time-quantitatively
completable wrt. $\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$, i.e.

$\displaystyle\mathcal{CTQC}$
$\displaystyle(K,{\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}}):=$
$\displaystyle\\{K^{\prime}\subseteq K\mid K^{\prime}~{}\text{is controllable
and time-quantitatively}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{ completable
wrt. ${\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}}$}\\}.$

Since the empty language $\emptyset$ is trivially controllable and time-
quantitatively completable, the set
$\mathcal{CTQC}(K,\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\})$ is nonempty.
Moreover, since both controllability and time-quantitative completability are
closed under arbitrary set unions,
$\mathcal{CTQC}(K,\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$ contains a unique
supremal element given by

$\displaystyle\sup\mathcal{CTQC}(K,$
$\displaystyle{\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}}):=\bigcup\\{K^{\prime}\subseteq
K\mid$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}K^{\prime}\in\mathcal{CTQC}(K,{\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}})\\}.$

Our main result in this section is the following.

###### Theorem 4

Suppose that
$\sup\mathcal{CTQC}(K,{\\{(Q_{m,i},N_{i})}|i\in\mathcal{I}\\})\neq\emptyset$.
Then the supervisory control $V_{\sup}$ such that $L_{m}(V_{\sup}/{\bf
G})=\sup\mathcal{CTQC}(K,{\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}})$ $\subseteq
K$ is the solution to the TQNSCP.

Proof: Since $\sup\mathcal{CTQC}(K,{\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}})$
is controllable and time-quantitatively completable wrt.
$\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$, according to Theorem 2 there exists a
time-quantitatively nonblocking supervisory control $V_{\sup}$ such that
$L_{m}(V_{\sup}/{\bf G})=\sup\mathcal{CTQC}(K,$
${\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}})\subseteq K$. Hence the first
(safety) and the second (time-quantitative nonblockingness) requirements of
the TQNSCP are satisfied. Further, since
$\sup\mathcal{CTQC}(K,{\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}})$ is the
supremal element in
$\mathcal{CTQC}(K,{\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}})$, the third
(maximal permissiveness) requirement of the TQNSCP is also satisfied.
Therefore, $V_{\sup}$ that synthesizes
$\sup\mathcal{CTQC}(K,\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\})$ is the solution
to the TQNSCP. $\blacksquare$

We proceed to design an algorithm to compute this solution
$\sup\mathcal{CTQC}(K,\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\})$. Since there
exists a well-known algorithm to compute the supremal controllable sublanguage
[4, 8] which will be referred in this paper as Algorithm SC, and in the
preceding section we designed Algorithm 1 to compute the supremal time-
quantitatively completable sublanguage, a natural idea is to iterate these two
algorithms until the fixed point is reached. The details are described in
Algorithm 2 below.

Algorithm 2 : Algorithm of Computing
$\sup\mathcal{CTQC}(K,\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\})$
($\mathcal{I}=\\{1,\ldots,M\\}$)

Input: TDES ${\bf G}=(Q,\Sigma,\delta,q_{0},Q_{m})$, language $K\subseteq
L_{m}({\bf G})$, partition $\mathcal{Q}_{\bf G}=\\{Q_{m,i}|i\in\mathcal{I}\\}$
on marker state set $Q_{m}$, and set of positive integers
$\\{N_{i}|i\in\mathcal{I}\\}$.
Output: Language $CTK$.

Step 1. Let $j=1$ and $K^{j}=K$ (i.e. $K^{1}=K$).

Step 2. Let $i=1$. Let $K_{i}^{j}=K^{j}$.

Step 2.1 Apply Algorithm 1 with inputs ${\bf G}$, $K_{i}^{j}$, $Q_{m,i}$ and
$N_{i}$, and obtain
${NK_{i}^{j}}=\sup\mathcal{QC}(K_{i}^{j},(Q_{m,i},N_{i}))$.

Step 2.2 If $i<M$, let $K_{i+1}^{j}={NK_{i}^{j}}$, advance $i$ to $i+1$ and go
to Step 2.1; otherwise ($i=M$), go to Step 3.

Step 3. Apply Algorithm SC with inputs ${\bf G}$ and ${NK_{M}^{j}}$ to compute
$K^{j+1}$ such that $K^{j+1}=\sup\mathcal{C}({NK_{M}^{j}})$.

Step 4. If $K^{j+1}=K^{j}$, output $CTK=K^{j+1}$. Otherwise, advance $j$ to
$j+1$ and go to Step 2.

The correctness of Algorithm 2 is confirmed by the following theorem.

###### Theorem 5

Given a TDES plant ${\bf G}$, a specification language $E$, let $K:=E\cap
L_{m}({\bf G})$, a partition $\mathcal{Q}_{\bf G}=\\{Q_{m,i}\subseteq
Q_{m}|i\in\mathcal{I}\\}$ on $Q_{m}$, and a set of positive integer $N_{i}$
each associated with a $Q_{m,i}\in\mathcal{Q}_{\bf G}$. Then Algorithm 2
terminates in a finite number of steps and outputs a language $CTK$ such that
$CTK=\sup\mathcal{CTQC}(K,\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\})$.

Proof: Since Algorithm 1 terminates in a finite number of steps, and Algorithm
SC for computing the supremal controllable sublanugaes does not increase the
state/transition number of the generator representing $NK_{M}^{j}$, Algorithm
2 also terminates in a finite number of steps.

It is left to show that the output $CTK$ of Algorithm 2 satisfies
$CTK=\sup\mathcal{CTQC}(K,{\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}})$. Note that
Step 2 in Algorithm 2 performs the computation of supremal time-quantitatively
completable sublanguage, and Step 3 supremal controllable sublanguage, so the
iterations of Steps 2—4 generates the following sequence of languages:

$\displaystyle K$ $\displaystyle=K^{1}=K_{1}^{1}\supseteq
NK_{1}^{1}\supseteq...\supseteq NK_{M-1}^{1}\supseteq NK_{M}^{1}$
$\displaystyle\supseteq K^{2}\supseteq...$

Since Algorithms 2 is finitely convergent, so is the above sequence of
languages. When the sequence converges, i.e. in Step 4 $K^{j+1}=K^{j}$ holds
for some $j$, $K^{j+1}$ is the supremal controllable and time-quantitatively
completable sublanguage of $K$ wrt. $\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\}$.
This proves that
$CTK=K^{j+1}=\sup\mathcal{CTQC}(K,\\{(Q_{m,i},N_{i})|i\in\mathcal{I}\\})$.
$\blacksquare$

The complexity of one complete iteration over all $i\in\mathcal{I}$ in Step 2
of Algorithm 2 is $O(|Q|\cdot|X|\cdot\prod_{i=1}^{|\mathcal{I}|}{N_{i}})$.
Since Algorithm SC does not increase the state/transition number of
${NK_{M}^{j}}$ ($M=|\mathcal{I}|$), the complexity of each iteration including
Steps 2 and 3 is again $O(|Q|\cdot|X|\cdot\prod_{i=1}^{M}{N_{i}})$. Finally
since there can be at most
$|Q|\cdot|X|\cdot|\Sigma|\cdot\prod_{i=1}^{|\mathcal{I}|}{N_{i}}$ iterations,
the overall time complexity of Algorithm 2 is
$O\big{(}(|Q|\cdot|X|\cdot|\Sigma|\cdot\prod_{i=1}^{|\mathcal{I}|}{N_{i}})^{2}\big{)}$.

The following example demonstrates how to synthesize supervisors satisfying
both controllability and time-quantitative completability.

######  Example 3 (Continuing Example 1)

Consider TDES plant ${\bf G}$ and nonblocking supervisor ${\bf SUP}$ displayed
in Fig. 3. First, applying Algorithm1 with inputs ${\bf G}$, $K=L_{m}({\bf
SUP})$, $\mathcal{Q}_{\bf G}=\\{Q_{m,1}=\\{1,2\\},Q_{m,2}=\\{0\\}\\}$ and
$\\{N_{1}=5,$ $N_{2}=9\\}$, we get the supremal time-quantitatively
completable language $NK$ (wrt. $\\{(Q_{m,1}=\\{1,2\\},N_{1}=5)$,
$(Q_{m,2}=\\{0\\},N_{2}=9)\\}$) represented by automaton $\bf NK$ displayed in
Fig. 6. However, it is not controllable, because event $tick$ is disabled at
state 102, but event 22 is not forcible, which cannot preempt the occurrence
of $tick$. Next applying Algorithm SC with inputs $\bf G$ and $NK$ (although
state 83 is a marker state, $tick$ is preempted on it but after event 21 is
disabled, none of the forcible events is eligible at state 83; thus states 83,
94, 95, 98, 99 and corresponding transition arriving them are removed from
$\bf NK$), we get an automaton ${\bf TQCSUP}$ as displayed Fig. 6. It is
verified that $L_{m}({\bf TQCSUP})$ is both controllable and time-
quantitatively completable wrt. $\\{(Q_{m,1}=\\{1,2\\},N_{1}=5)$,
$(Q_{m,2}=\\{0\\},N_{2}=9)\\}$, and thus according to Theorem 2, ${\bf
TQCSUP}$ may be used as a quantitatively nonblocking supervisor.

This supervisor ${\bf TQCSUP}$ is used to make the autonomous vehicle provide
timely services in Example 1. The control logics of ${\bf TQCSUP}$ are as
follows: (1) never move to zone 2 (corresponding to states 81 and 88) and zone
4 (corresponding to state 48, 49, 50, 51 and 52) when in zone 3 (corresponding
to states 89, 90, 91 and 92); (ii) never move to zone 1 (corresponding to
states 33, 34, 35, 35 and 37) when in zone 4; (iii) if the vehicle is in zone
1, it is safe to move to zone 2 and zone 4 if it has just returned from zone 0
(i.e. finished self-charging; corresponding to states 0, 75, 116); and (iv) if
the vehicle has moved to zone 2 and 3, it must return (either by moving
through zone 1, or moving though zone 4) for self-charging before the next
round of service.

These logics guarantee that the two requirements ((i) and (ii) in Example 1 of
Section 2.2) on the vehicle are satisfied. First, every package sent to
customers can be delivered by the vehicle to one of the two service areas
(zone 1 or 2) within 10 minutes; and whenever a customer calls for package
collection, the vehicle can reach either zone 1 or 2 within 10 minutes no
matter where the vehicle is and no matter which paths (permitted by the
supervisor $\bf TQCSUP$) the vehicle follows. Second, no matter where the
vehicle is, it can return to zone 0 for self-charging within 18 minutes no
matter which paths the vehicle follows.

Figure 6: Transition graphs of automaton ${\bf NK}$ (including all the
transition) and ${\bf TQCSUP}$ (not including the states and transitions with
dashed lines.)

##  VI Conclusion and Future Work

In this paper, we have introduced a new concept of time-quantitative
nonblockingness of TDES (or automaton), which requires that every task (each
represented by a subset of marker states) must be completed in prescribed
time. Moreover, we have formulated a new time-quantitatively nonblocking
supervisory control problem, characterized its solution in terms of time-
quantitative language completability, and developed algorithms to compute the
optimal solution.

## References

  * [1] P. Ramadge and W. Wonham, “Supervisory control of a class of discrete event processes,” _SIAM Journal on Control and Optimization_ , vol. 25, no. 1, pp. 206–230, 1987.
  * [2] W. Wonham and P. Ramadge, “On the supremal controllable sublanguage of a given language,” _SIAM Journal on Control and Optimization_ , vol. 25, no. 3, pp. 637–659, 1987.
  * [3] P. Ramadge and W. Wonham, “The control of discrete event systems,” _The Proceedings of IEEE_ , vol. 77, no. 1, pp. 81–98, 1989.
  * [4] W. Wonham and K. Cai, _Supervisory Control of Discrete-Event Systems_. Springer, 2019.
  * [5] K. Cai and W. Wonham, _Supervisory control of discrete-event systems_. Encyclopedia of Systems and Control, 2nd ed., Springer, 2020.
  * [6] W. Wonham, K. Cai, and K. Rudie, “Supervisory control of discrete-event systems: a brief history,” _Annual Reviews in Control_ , vol. 45, pp. 250–256, 2018.
  * [7] C. Cassandras and S. Lafortune, _Introduction to Discrete Event Systems_ , 2nd ed. Springer, 2008.
  * [8] B. Brandin and W. Wonham, “Supervisory control of timed discrete-event systems,” _IEEE Transactions on Automatic Control_ , vol. 39, no. 2, pp. 329–342, 1994.
  * [9] R. Kumar and M. Shayman, “Non-blocking supervisory control of deterministic discrete event systems,” in _Proc. 1994 American Control Conference_ , 1994, pp. 1089–1093.
  * [10] M. Fabian and R. Kumar, “Mutually nonblocking supervisory control of discrete event systems,” in _Proc. 36th IEEE Conference on Decision and Control_ , 1997, pp. 2970–2975.
  * [11] C. Ma and W. Wonham, “Nonblocking supervisory control of state tree structures,” _IEEE Transactions on Automatic Control_ , vol. 51, no. 5, pp. 782–793, 2006.
  * [12] R. Malik and R. Leduc, “Generalised nonblocking,” in _Proc. 9th International Workshop on Discrete Event Systems_ , 2008, pp. 340–345.
  * [13] S. Balemi, G. Hoffmann, P. Gyugyi, H. Wong-Toi, and G. Franklin, “Supervisory control of a rapid thermal multiprocessor,” _IEEE Transactions on Automatic Control_ , vol. 38, no. 7, pp. 1040–1059, 1993.
  * [14] B. Brandin and F. Charbonnier, “The supervisory control of the automated manufacturing system of the aip,” in _Proc. Rensselaer’s 4th Int. Conf. Computer Integrated Manufacturing and Automation Technology_ , 1994, pp. 319–324.
  * [15] P. Malik, “From supervisory control to nonblocking controllers for discrete event systems,” Ph.D. dissertation, University of Kaiserslautern, 2003.
  * [16] S. Eilenberg, _Automata, Languages and Machines Voluma A_. Academic Press, 1974.
  * [17] R. Zhang, Z. Wang, and K. Cai, “N-step nonblocking supervisory control of discrete-event systems,” in _Proc. 2021 60th IEEE Conference on Decision and Control (CDC)_ , Austin, Texas, December 13-15 2021, pp. 339–344.
  * [18] R. Zhang, J. Wang, Z. Wang, and K. Cai, “Quantitatively nonblocking supervisory control of discrete-event systems,” Tech. Rep., 2022, available at https://arxiv.org/abs/2108.00721.
  * [19] B. Berard, M. Bidoit, A. Finkel, F. Laroussinie, A. Petit, L. Petrucci, and P. Schnoebelen, _Systems and Software Verification_. Springer-Verlag Berlin Heidelberg, 2001.
  * [20] B. Bonakdarpour and S. Kulkarni, “Complexity issues in automated addition of time-bounded liveness properties,” Department of Computer Science and Engineering, Michigan State University, Tech. Rep., 2006.
  * [21] C. Daws, A. Olivero, S. Tripakis, and SergioYovine, _Kronos: A verification tool for real-time systems_ , 2002, available at https://www-verimag.imag.fr/DIST-TOOLS/TEMPO/kronos/.