IEEE CONTROL SYSTEMS SOCIETY TECHNICAL COMMITTEE
ON DISCRETE EVENT SYSTEMS

    Ryan J. Leduc
    Chair, IEEE CSS Technical Committee on DES
    Dept. of Computing and Software
    McMaster University
    1280 Main Street West
    Hamilton, Ontario
    Canada L8S 4K1

    Phone: (905) 525-9140 Ext. 27962
    Fax: (905) 524-0340
    e-mail: leduc@mcmaster.ca
    WWW: http://www.cas.mcmaster.ca/~leduc/

DESTC Web Page: http://www.cas.mcmaster.ca/destc/

To subscribe/unsubscribe or submit news items and articles to this newsletter, send e-mail to: destcsubm@cas.mcmaster.ca

It is the responsibility of the contributor to ensure that they have the necessary permissions/clearance required for the transmittal of their news item.

Contents:

1. Editorial

2. Announcements
 2.1 Volunteers needed to submit table of contents for journals.
 2.2 List of Discrete-Event System Researchers goes Live.
 2.3 Suggestions needed for DES related web sites.

3. Conferences
 3.1 16th IFAC World Congress, Prague, Czech Republic, July 4 - 8, 2005.
 3.2 The Forty-Third Annual Allerton Conference on Communication,   
     Control, and Computing, Urbana-Champaign,  Illinois, USA, 
     September 28 - 30, 2005.

4. Journals
 4.1 Table of Contents, Discrete Event Dynamic Systems: Theory and
     Applications, VOL. 15, NUMBER 2, June 2005.
 4.2 Selections from IEEE Transactions on Automatic Control,
     VOLUME 50, ISSUE 4, April 2005.

Welcome to the newsletter of the IEEE Control Systems Technical Committee Group on Discrete Event Systems!

See http://www.cas.mcmaster.ca/destc/ for information on the DESTC.

Personal note from the editor:

Normally I don't send out newsletters this frequently, but I
received two conference notices with rapidly approaching dates, so I
decided to send out a quick update.

Contributed by: Ryan Leduc <leduc@mcmaster.ca>

VOLUNTEERS NEEDED TO SUBMIT TABLE OF CONTENTS FOR JOURNALS

As the full table of contents of many control systems journals already
appear in the IEEE Control Systems Society's eletter (see:
http://www.ieeecss.org/PAB/eletter/ ) which I assume many  of the
readers of this newsletter also receive, I wish to avoid duplication. 
For this reason, only articles that appear relevant to DES in a
journal's table of contents will be listed.  If only a few articles,
the abstract may be included, if available and space permits.  What is
"relevant" to DES will be liberally interpreted, but I'm sure some
articles will accidentally get overlooked. If you see such an
oversight, please send a correction to destcsubm@cas.mcmaster.ca with
subject: CORR. 

I need volunteers who regularly read the indicated journals to provide
the newsletter with a table of contents announcement for the journal,
 only including articles relevant to DES.  I can provide you with the
announcement of the new edition, as well as the table of contents and
access to the abstracts. I need volunteers for the journals listed
below. I have already made arrangements for the IEEE Transactions on
Automatic Control and the  Discrete Event Dynamic Systems Journal. 
If interested, please send e-mail to: destc@cas.mcmaster.ca indicating
which journal you would like to handle. 

1) IEEE Transactions on Control Systems Technology.
2) IEEE Transactions Systems, Man and Cybernetics, Part A, Part B, and
   Part C.
3) Automatica, an IFAC Journal.
4) Control Engineering Practice, an IFAC Journal.  

If you regularly read other journals in which DES articles sometimes
appear and you would like to provide announcements for this, please
send e-mail to: destc@cas.mcmaster.ca  to let me know.

Contributed by: Ryan Leduc <leduc@mcmaster.ca>

LIST OF DISCRETE-EVENT SYSTEM RESEARCHERS GOES LIVE

The section on the DESTC website labelled "Links to relevant sites" is
very out of date. If you know of any good DES related websites, please
send e-mail to destcsubm@cas.mcmaster.ca with subject: WWW.  In
particular, I'd like links to DES related software tools, but any
useful, relevant website is welcome.

Please do not submit links to personal websites of DES
researchers. These should go in the list of DES researchers website

Contributed by: Ryan Leduc <leduc@mcmaster.ca>

SUGGESTIONS NEEDED FOR DES RELATED WEB SITES

The section on the DESTC website labelled "Links to relevant sites" is
very out of date. If you know of any good DES related websites, please
send e-mail to destcsubm@cas.mcmaster.ca with subject: WWW.  In
particular, I'd like links to DES related software tools, but any
useful, relevant website is welcome.

Please do not submit links to personal websites of DES
researchers. These should go in the list of DES researchers website. 

Contributed by: Xiren Cao <eecao@ust.edu.hk>

TABLE OF CONTENTS, DISCRETE EVENT DYNAMIC SYSTEMS: THEORY AND
APPLICATIONS
VOL. 15, NUMBER 2
JUNE, 2005

1)  Min-Max Inequalities and the Timing Verification Problem with a
    Max and Linear Constraints (Yiping Cheng and Da-Zhong Zheng) 

    ABSTRACT:

    "In this paper the timing verification problem with max and linear
    constraints is formulated in min-max inequalities.  An algorithm
    MMIsolve, based on the UBCsolve algorithm of Walkup, is proposed for
    solving min-max inequalities and for efficiently finding the maximum
    time separations between events.  A concept of structural finite
    separation is introduced, and it is found that structural finite
    separation is a sufficient, but not necessary condition for finite
    separation.  The two conditions are equivalent when the parameters are
    only allowed to take nonnegative values."

    Keywords: discrete event systems, min-max inequalities, min-max
              functions, timing analysis and verification. 

2)  PACE-Completeness of Modular Supervisory Control Problems (Kurt
    Rohloff and Sephane Lafortune) 

    ABSTRACT:

    "In this paper we investigate computational issues associated with
    the supervision of concurrent processes modeled as modular
    discrete-event systems.  Here, modular discrete-event systems are
    sets of deterministic finite-state automata whose interaction is
    modeled by the parallel composition operation.  Even with such a
    simple model process model, we show that in general many problems
    related to the supervision of these systems are PSPACE-complete.
    This shows that although there may be space-efficient methods for
    avoiding the state-explosion problem inherent to concurrent
    processes, there are most likely no time-efficient solutions that
    would aid in the study of such "large-scale" systems.  We show our
    results using a reduction from a special class of automata
    intersection problem introduced here where behavior is assumed to
    be prefix-closed.  We find that deciding if there exits a
    supervisor for a modular system to achieve a global specification
    is PSPACE-complete.  We also show many verification problems for
    system supervision are PSPACE-complete, even for prefix-closed
    cases.  Supervisor admissibility and online supervision operations
    are also discussed." 

    Keywords: modular systems, supervisory control, verification,
              computational complexity 


3)  Basic Ideas for Event-Based Optimization of Markov Systems (Xi-Ren
    Cao http://www.ee.ust.hk/~eecao) 

    ABSTRACT:

    "The goal of this paper is two-fold: First, we present a
    sensitivity point of view on the optimization of Markov systems.
    We show that Markov decision processes (MDPs) and the
    policy-gradient approach, or perturbation analysis (PA), can be
    derived easily from two fundamental sensitivity formulas, and such
    formulas can be flexibly constructed, by first principles, with
    performance potentials as building blocks. Second, with this
    sensitivity view we propose an event-based optimization approach,
    including the event-based sensitivity analysis and event-based
    policy iteration. This approach utilizes the special feature of a
    system characterized by events and illustrates how the potentials
    can be aggregated using the special feature and how the aggregated
    potential can be used in policy iteration. Compared with the
    traditional MDP approach, the event-based approach has its
    advantages: the number of aggregated potentials may scale to the
    system size despite that the number of states grows exponentially
    in the system size, this reduces the policy space and saves
    computation; the approach does not require actions at different
    states to be independent; and it utilizes the special feature of a
    system and does not need to know the exact transition probability
    matrix. The main ideas of the approach are illustrated by an
    admission control problem." 

    Keywords: Perturbation analysis, Markov decision processes (MDPs),
              POMDPs, Performance potentials, Policy iteration, Policy
              gradients, Aggregation.

Web site:

Click Here.

Contributed by: Ryan Leduc <leduc@mcmaster.ca>

SELECTIONS FROM IEEE TRANSACTIONS ON AUTOMATIC CONTROL
VOLUME 50, ISSUE 4
APRIL, 2005

1) Characterization of Co-Observable Languages and Formulas for Their
   Super/Sublanguages
   Takai, S.; Kumar, R.; Ushio, T.
   Page(s):  434-447

   ABSTRACT:

   "We present fixed-point based characterization of several classes
   of co-observable languages that are of interest in the context of
   decentralized supervisory control of discrete-event systems,
   including C&P$vee $D&A co-observable languages, C&P co-observable
   languages, and D&A co-observable languages. We also provide
   formulas for computing super/sublanguages for each of these
   classes. In cases where the class of co-observable languages is not
   closed under intersection/union, we provide upper/lower bound of
   the super/sublanguage formula we present. The computation of
   super/sublanguages and also computation of their upper/lower bounds
   has lead to the introduction of other classes of co-observable
   languages, namely, strongly C&P co-observable languages, strongly
   D&A co-observable languages, locally observable languages, and
   strongly locally observable languages. Fixed-point based
   characterization of all the above language classes is also given,
   and their closure under intersection/union is investigated. We also
   study whether the fixed-point operator preserves prefix closure,
   relative closure (also called$L_m(G)$-closure), and
   controllability." 

2) Polynomial Synthesis of Supervisor for Partially Observed
   Discrete-Event Systems by Allowing Nondeterminism in Control 
   Kumar, R.; Jiang, S.; Zhou, C.; Qiu, W.
   Page(s):  463- 475

   ABSTRACT:

   "We study the supervisory control of discrete-event systems (DESs)
   under partial observation using nondeterministic supervisors. We
   formally define a nondeterministic control policy and also a
   control & observation compatible nondeterministic state machine and
   prove their equivalence. The control action of a nondeterministic
   supervisor is chosen online, nondeterministically from among a set
   of choices determined offline. Also, the control action can be
   changed online nondeterministically (prior to any new observation)
   in accordance with choices determined offline. The online choices,
   once made, can be used to affect the set of control action choices
   in future. We show that when control is exercised using a
   nondeterministic supervisor, the specification language is required
   to satisfy a weaker notion of observability, which we define in
   terms of recognizability and achievability. Achievability serves as
   necessary and sufficient condition for the existence of a
   nondeterministic supervisor, and it is weaker than controllability
   and observability combined. When all events are controllable,
   achievability reduces to recognizability. We show that both
   existence, and synthesis of nondeterministic supervisors can be
   determined polynomially. (For deterministic supervisors, only
   existence can be determined polynomially.) Both achievability and
   recognizability are preserved under union, and also under
   intersection (when restricted over prefix-closed languages). Using
   the intersection closure property we derive a necessary and
   sufficient condition for the range control problem for the
   prefix-closed case. Unlike the deterministic supervisory setting
   where the complexity of existence is exponential, our existence
   condition is polynomially verifiable, and also a supervisor can be
   polynomially synthesized." 

3) Diagnosability of Stochastic Discrete-Event Systems
   Thorsley, D.; Teneketzis, D.
   Page(s):  476- 492

   ABSTRACT:

   "We investigate diagnosability of stochastic discrete-event
   systems. We define the notions of A- and AA-diagnosability for
   stochastic automata; these notions are weaker than the
   corresponding notion of diagnosability for logical automata
   introduced by Sampath Through the construction of a stochastic
   diagnoser, we determine offline conditions necessary and sufficient
   to guarantee A-diagnosability and sufficient to guarantee
   AA-diagnosability. We also show how the stochastic diagnoser can be
   used for on-line diagnosis of failure events. We illustrate the
   results through two examples from HVAC systems."

Web site:

http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=30592&isYear=2005

Contributed by: Ryan Leduc <leduc@mcmaster.ca>

16TH IFAC WORLD CONGRESS
Prague, Czech Republic
July 4 - 8, 2005

It is our great pleasure to invite you to participate in the 16th IFAC
World Congress to be held in Prague, Czech Republic, from July 4 to
July 8, 2005. The Congress will be a good opportunity for presenting
new results and directions of Automatic Control theory, technology and
applications. As such, it mainly will concentrate on the following key
points: 

    * Emphasis on invited lectures including plenaries, surveys and
      tutorials 
    * Industry participation promotion
    * Attract young people to study and work in the field

The participants of the 16th IFAC World Congress will have the
opportunity to take part in the wide spectrum of categories for
technical presentations, including plenary lectures, survey papers,
regular papers of both lecture and poster session types, panel
discussions and case studies. Immediately preceding the formal opening
of the Congress, tutorials and workshops are being offered to give
participants an opportunity to learn new principles, methodologies,
technologies and applications that have been developed and/or are
developing in recent years. 

For program information, go here: http://ifacplaza.certicon.cz/program.php 

    * Vladimir Kucera- IFAC President
    * Michael Sebek - NOC Chairman
    * Petr Horacek - IPC Co-Chairman
    * Miroslav Simandl - IPC Co-Chairman
    * Pavel Zitek - Editor

Web site:

http://ifacplaza.certicon.cz/index.php

Contributed by: Ryan Leduc <leduc@mcmaster.ca>

THE FORTY-THIRD ANNUAL ALLERTON CONFERENCE ON COMMUNICATION,
CONTROL, AND COMPUTING
Urbana-Champaign, Illinois, USA
September 28 - 30, 2005

The Forty-Third Annual Allerton Conference on Communication, Control,
and Computing will be held from Wednesday, September 28 through
Friday, September 28, 2005, at the Allerton House, the conference
center of the University of Illinois. Allerton House is located
twenty-six miles southwest of the Urbana-Champaign campus of the
University, in a wooded area on the Sangamon River. It is part of the
fifteen-hundred acre Robert Allerton Park, a complex of natural and
man-made beauty designated as a National natural landmark. The
Allerton Park has twenty miles of well-maintained trails and a living
gallery of formal gardens, studded with sculptures collected from
around the world. 

Papers presenting original research are solicited in the areas of
communication systems, communication and computer networks, detection
and estimation theory, information theory, error control coding,
source coding and data compression, queueing networks, control
systems, robust and nonlinear control, adaptive control, optimization,
dynamic games, large scale systems, robotics and automation,
manufacturing systems, discrete event systems, intelligent control,
multivariable control, computer vision based control, learning theory,
neural networks, VLSI architectures for communications and signal
processing, and automated highway systems. Also solicited are
organized sessions for the Conference; prospective organizers should
discuss their plans with the Conference co-chairs before sending a
formal proposal. 

Plenary lecture: Professor Jacob Ziv of the Technion -- Israel
Institute of Technology will deliver this year's plenary
lecture. It is entitled "What is Hidden in an Individual
Sequence" and is scheduled for Friday, September 30, 2005. 

Information for authors: Regular papers, suitable for presentation in
twenty minutes, as well as short papers, suitable for presentation in
ten minutes, are solicited. The purpose of the short paper category is
to encourage authors to present preliminary results of their
work. Regular papers will be published in full (subject to a maximum
length of ten 8.5" x 11" pages) in the Conference
Proceedings, while short papers will be limited to two-page summaries
in the Proceedings. 

For reviewing purposes regular papers, a title and a five-to-ten page
extended abstract, including references and sufficient detail to
permit careful reviewing, are required. For short papers, a title and
a three-to-five page summary are required. Manuscripts that are
submitted as regular papers but cannot be accommodated in that
category will be considered in the short paper category, unless the
authors indicate otherwise. 

Manuscripts must be submitted by Tuesday, July 5, 2005 following the
instructions at the Conference website:
http://www.comm.csl.uiuc.edu/allerton. 

Authors will be notified of acceptance via e-mail by August 5, 2005,
at which time they will also be sent detailed instructions for the
preparation of their papers for the Proceedings. 

A final version of presented papers must be submitted electronically
prior to the end of the Conference. 

Conference Co-Chairmen: Geir Dullerud and Andrew Singer

Email: allerton@csl.uiuc.edu

Web site:

http://www.csl.uiuc.edu/allerton/