IEEE CONTROL SYSTEMS SOCIETY WORKING GROUP
ON DISCRETE EVENT SYSTEMS
Newsletter......................................................September, 1996
Editor: Edwin K. P. Chong
Chair, IEEE CSS Working Group on DES
School of Electrical and Computer Engineering
Purdue University
1285 Electrical Engineering Bldg.
West Lafayette, IN 47907-1285
Phone: (317) 494-9143
Fax: (317) 494-3371
e-mail: echong@ecn.purdue.edu
WWW: http://yara.ecn.purdue.edu/~echong/
Back issues: http://yara.ecn.purdue.edu/~echong/des_wg/
_._________________________________________________________________________._
Contents:
1. Editorial
2. Announcements
2.1 Ph.D. thesis on "Theory of Hybrid Systems and Discrete Event Systems".
2.2 Columbia's Center for Applied Probability (CAP) awarded NSF
Group Infrastructure Grant
3. Conferences
3.1 Second IEEE International Conference on
Engineering of Complex Computer Systems
_._________________________________________________________________________._
Editorial
_._________________________________________________________________________._
Welcome to the newsletter of the IEEE Control Systems Society Working
Group on Discrete Event Systems!
It's been a quiet couple of months for the DES WG; as you can see, there
were only three contributions to this month's newsletter. Must be the
end-of-summer blues, a phenomenon that besets researchers from the
northern hemisphere around this time every year.
The DES WG aims to promote communication between
DES researchers, scholars, students, and practitioners.
I wish to encourage participation by submitting contributions
(announcements, articles, etc.) to the newsletter. Just send
them to me by e-mail. Examples of contributions include
announcements on:
- Conferences
- Workshops
- Special sessions
- Publications
- Courses
- Personals
- Job opportunities and positions
- FTP and WWW Sites
Notice the delimiter between articles/contributions in this newsletter.
If you are using an editor to read this article, you can go directly
to the delimiter by searching for the string "_.__"
(underscore,period,underscore,underscore).
This feature is useful for quickly skipping to the next item.
_._________________________________________________________________________._
Announcements
_._________________________________________________________________________._
Contributed by: Anuj Puri
I have recently finished my PhD thesis in the area of hybrid systems
and discrete event systems. My thesis and my papers are available
on my homepage at:
http://www-path.eecs.berkeley.edu/~anuj/anuj.html
Attached below is the abstract for my thesis which is titled
"Theory of Hybrid Systems and Discrete Event Systems".
Abstract:
A continuous system has a continuous state space and an evolution law given by
a differential or a difference equation. A discrete event system is modeled by
an automaton which changes state in response to events. A hybrid system
contains both continuous and discrete event sub-systems. In this thesis we
study some theoretical problems in the design and analysis of hybrid systems
and discrete event systems.
We first consider the reachability question for a hybrid system --- is a target
state reachable from an initial state? We show that for hybrid automata with
rectangular inclusions, the reachability question can be answered in a finite
number of steps. Hybrid systems with more general dynamics can be reduced to
hybrid systems with rectangular inclusions using abstractions.
We next consider an Automated Vehicle Highway System (AVHS) design. We
consider the safety question: can there be a collision between two vehicles on
the AVHS ? We show that the AVHS is safe provided the controllers in the
vehicles satisfy a set of constraints. The constraints require the reach set
$Reach_{f}(X_{0},t)$ --- the set of states reached after time $t$ starting from
an initial set $X_{0}$ for a differential inclusion $\dot{x} \in f(x)$ --- to
satisfy a simple criterion. We show that this problem is equivalent to solving
an optimal control problem.
We then consider some computational questions for differential inclusions. For
a Lipschitz differential inclusion $\dot{x} \in f(x)$, we give a method to
compute an arbitrary close approximation of $Reach_{f}(X_{0},t)$. For a
differential inclusion $\dot{x} \in f(x)$, and any $\epsilon > 0$, we define a
finite {\em sample graph} $A^{\epsilon}$. Using graph $A^{\epsilon}$, we can
compute the $\epsilon$-invariant sets of the differential inclusion --- the
sets that remain invariant under $\epsilon$-perturbations in $f$.
We also consider some dynamical games played on graphs. The synthesis and the
control problem for $\omega$-automata can be formulated as a game between two
players. We discuss games on $\omega$-automata and the payoff games. We show
that $\omega$-automata games do not necessarily have a value when restricted to
positional strategies. We exhibit a bound on the amount of memory required to
play these games. We then consider the discounted and mean payoff games. We
present the successive approximation and the policy iteration algorithm for
solving payoff games. We then show that an $\omega$-automata game with the
chain acceptance condition can be solved as a mean payoff game. Solving a
chain game is equivalent to solving the model checking problem for propositional
$\mu$-calculus. Hence, the policy iteration method can be used to model check
$\mu$-calculus formulae. This is at present the most efficient algorithm for
model checking propositional $\mu$-calculus.
_._________________________________________________________________________._
Contributed by: David Yao
Columbia University's Center for Applied Probability (CAP)
has been recently awarded by the National Science Foundation
a Group Infrastructure Grant of $1,000,000 for five years,
effective September 1, 1996.
The winning proposal, "CAP: Infrastructural Support for an Interdisciplinary
Research Center," outlined four application areas (mathematical and
computational finance, stochastic networks, logistics and distribution,
and population dynamics), and four methodological areas (control and
optimization, stochastic analysis, numerical methods, and statistical
inference), with extensive cross linkage, as CAP's focal areas for
building research and educational programs.
The proposing team is led by Chris Heyde and David Yao, and includes
Sid Browne, Joel Cohen, Awi Federgruen, Paul Glasserman, Ioannis Karatzas,
Perwez Shahabuddin, Larry Shepp, and Karl Sigman. Their many honors and
awards include: Membership in the U.S. National Academy of Science and the
Australian Academy of Science, MacArthur Fellowship, Guggenheim Fellowship,
George B. Pegram Distinguished Fellowship, Pitman Medal, Hannan Medal,
Lyle Medal, Paul Levy Prize, IEEE Distinguished Scientist Award,
Distinguished Statistical Ecologist Award, Mindel C. Sheps Award,
Mercer Award, Presidential/NSF Young Investigator Awards, NSF Faculty
Career Award, and George E. Nicholson Awards. Jointly, the team holds
over 30 positions on the editorial board of more than a dozen leading
journals in applied probability and related fields, including
Advances in Applied Probability, Annals of Applied Probability,
Journal of Applied Probability, Management Science, Mathematical Finance,
Operations Research, Queueing Systems, and SIAM Journal of Control and
Optimization.
______________________________________________
David D. Yao
Thomas Alva Edison Professor
IEOR Dept, 302 Mudd Bldg, Columbia University
New York, NY 10027-6699
Phone: 212-854-2934
Fax: 212-854-8103
E-mail: yao@ieor.columbia.edu
_._________________________________________________________________________._
Conferences
_._________________________________________________________________________._
Contributed by: Edwin Chong (echong@ecn.purdue.edu)
Second IEEE International Conference on
Engineering of Complex Computer Systems
Held jointly with 6th CSESAW, 4th IEEE RTAW and SES'96
Montreal Bonaventure Hilton, Montreal, Quebec, Canada
October 21-25, 1996
Sponsored by IEEE Computer Society and IEEE Technical Committee on
Complexity in Computing
Description: IEEE Computer Society's Second International Conference on the
Engineering of Complex Computer Systems (ICECCS'96) is to be held in
Montreal, Quebec, Canada, in October 1996, jointly with the 6th Complex
Systems Engineering Synthesis and Assessment Technology Workshop
(CSESAW'96), the 4th IEEE Workshop on Real-Time Applications (RTAW'96), and
the IEEE Forum on Software Engineering Standards Issues (SES'96).
Scope: Complex computer systems are becoming common in many sectors, such as
manufacturing, communications, defense, transportation, aerospace, hazardous
environments, energy, and health care. These systems frequently include
distributed, heterogeneous networks, and are driven by requirements on
performance, real-time behavior, fault tolerance, security, adaptability,
development time and cost, long life concerns, and other areas. Such
requirements frequently conflict, and satisfaction of these requirements
requires managing the tradeoffs among them during system development and
throughout the entire system life. The goal of this conference is to bring
together industrial, academic, and government experts from these various
disciplines, to determine how the disciplines' problems and solution
techniques interact within the whole system. Researchers, practitioners,
tool developers and users, and technology transition experts are all
welcome. Long-term research, near-term complex system requirements and
promising tools, and existing complex systems and commercially available
tools will be examined on a level playing field.
Keynote Speakers:
- Bertram Neville Brockhouse, McMaster University, Canada
(Nobel Prize in Physics 1994)
- David Gries, Cornell University, USA
- Ric Holt, University of Toronto
Technical Program includes 76 papers from academia, industry and government
sectors, and two panels of high current interest:
- New Paradigms
- Building Safety into Systems Applications
Exhibits: State-of-the-art ECCS tools will be exhibited.
Tutorials are planned as follows:
- Improved Software Testing with the Use of Metrics by Al Sorkowitz
- Software Design for Client/Server and Distributed Applications
by Hassan Gomaa
- JAVA
- Part I: The Java Programming Language by Guy L. Steele Jr.
- Part II: Java for Embedded Real-Time Development by Kelvin Nilsen
- Concepts and Use of the Common Object Request Broker Architecture
by Bernd Kraemer
- Software Reliability Engineering for Client-Server Systems
by Norman F. Schneidewind
Registration form and detailed information are available via
WWW: http://www.rtl.njit.edu/iceccs96.html
e-mail requests: iceccs96@rtlab12.njit.edu
_._________________________________________________________________________._
The End
_._________________________________________________________________________._
Fri Sep 13 10:22:24 EST 1996