#Number
TR-PDS-1995-010

#Title
Control and Analysis of Real-Time Discrete Event Systems

#Author
Darren D. Cofer

#Abstract
Many man--made systems such as automated factories, traffic control systems, 
communication networks, and computer programs are described in terms of 
discrete--valued variables that may change in highly discontinuous ways.  
These systems are called discrete event systems (DES) and are characterized by 
a discrete state set and a collection of events, such as the completion of a 
job or the arrival of a message.  The system state changes only at time 
instants corresponding to the occurrence of one of these events.  

The class of DES which can be modelled by automata known as timed event graphs 
are structurally related to finite state machines.  Both are governed by 
linear equations over a particular idempotent algebraic structure.  Since 
there exists a well--developed theoretical framework for studying the control 
of untimed DES modelled by finite state machines, we use the structural 
similarity to develop a corresponding control methodology for certain 
real--time DES.

We define events in a system to be controllable if their execution may be 
delayed.  A behavior specification consisting of a range of acceptable 
schedules for all events is controllable if the occurrence of uncontrollable 
events does not cause the system to leave the specification.  If a 
specification is not controllable we consider the existence and computation 
of a supremal (infimal) controllable subset (superset) of the specification.  
We also consider behaviors specified by minimum acceptable separation times 
between events.  Control can be exercised by defining automata representing 
the system and the specification and operating them in synchrony.  In this 
case we examine conditions under which the desired behavior is controllable 
and, if it is not, provide conditions for the existence of an optimal 
controllable behavior.  
	
#Bib
@phdthesis{,
  author = 	 "Darren D. Cofer",
  title = 	 "Control and Analysis of Real-Time Discrete Event Systems",
  school =	 "The University of Texas at Austin",
  month =	 "May",
  year = 	 1995,
  note =	 "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-1995-010"
}