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 to the newsletter, please go here.

To submit news items and articles to this newsletter, go here.

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 Beta Version of IDES Software Available

3. Conferences
 3.1 13th International ERCIM Workshop on Formal Methods for Industrial
     Critical Systems (FMICS 2008), L'Aquila, Italy, September 15 -
     16, 2008

4. Journals
 4.1 Selections from Automatica, Volume 44, Issue 3, March 2008
 4.2 Selections from IEEE Transactions on Systems, Man, and Cybernetics,
     Part C: Applications and Reviews, Volume 38, Issue 2, March
     2008
 4.3 Selections from IEEE Transactions on Systems, Man and Cybernetics, Part
     A, Volume: 38, Issue: 2, March 2008
 4.4 Selections from IEEE Transactions on Automatic Control, Volume: 53 
     Issue: 2, March 2008

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

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

Personal note from the editor:

Welcome to the March 2008 newsletter,

Ryan

Contributed by: Ryan Leduc <leduc aT mcmaster dOt ca>

BETA VERSION OF IDES SOFTWARE AVAILABLE

The Discrete-Event Systems Control Group Lab of Karen Rudie, Queen's 
University,  has released a beta version of IDES (Integrated 
Discrete-Event Systems software).  The software can be downloaded (at
no cost) from
http://www.ece.queensu.ca/hpages/labs/discrete/software.html, 
where a quick start guide is also available.

 The key features of this software are that it allows you to
---draw and manipulate graphical drawings of finite-state machines 
   (i.e., directed graphs)
---export your drawings to file formats such as EPS and PNG
---do DES operations on the finite-state machines
---do LaTeX rendering

 The interface of IDES allows you to mimic pen and paper drawing of 
finite-state machines by being able to draw in a way that more closely 
resembles the movement of your hand when you are quickly sketching a 
finite-state machine.	Also, even if you don't wish do to any DES 
operations, the software can be used to create directed graphs that can
be exported to LaTeX or other documents.

Contributed by: Ryan Leduc <leduc aT mcmaster DOt ca>

13TH INTERNATIONAL ERCIM WORKSHOP ON FORMAL METHODS FOR INDUSTRIAL
CRITICAL SYSTEMS (FMICS 2008)
L'Aquila, Italy
September 15 - 16, 2008

Preliminary CALL FOR PAPERS - 

FMICS 2008 (Colocated with ASE 2008 conference)

IMPORTANT DATES
---------------
Abstract:			      29 May 2008
Full Paper:			      5 June 2008
Notification of Acceptance:	     14 July 2008
Final version due:		    5 August 2008

SCOPE OF THE WORKSHOP
---------------------
The aim of the ERCIM FMICS workshop series is to provide a forum for
researchers who are interested in the development and application of
formal methods in industry. In particular, these workshops bring
together scientists and engineers that are active in the area of
formal methods and interested in exchanging their experiences in the
industrial usage of these methods. The FMICS workshop series also
aims to promote research and development that will improve formal
methods and related tools, facilitating their industrial application.
Topics include, but are not restricted to:
- Design, specification, code generation and testing based on formal
    methods
- Verification and validation of complex, distributed, real-time
    systems and embedded systems
- Verification and validation methods that address shortcomings
    of existing methods with respect to their industrial applicability
    (e.g., scalability and usability issues)
- Tools for the development of formal design descriptions
- Case studies and experience reports on industrial applications of  
    formal methods, focusing on lessons learned or identification of 
    new research directions
- Impact of the adoption of formal methods on the development process
    and associated costs
- Application of formal methods in standardization and industrial
    forums

INVITED SPEAKERS
----------------
Werner Damm (OFFIS, Germany)
Steven Miller (Rockwell Collins, Advanced Technology Center, USA)

PROGRAM COMMITTEE
-------------------
Maria Alpuente	(U. Politecnica de Valencia, Spain)
Alvaro Arenas (STFC RAL, UK)
Lubos Brim (Masaryk University, Czech Republic)
Darren Cofer (Rockwell Collins, USA)  Co-Chair
Alessandro Fantechi (Univ. di Firenze and ISTI-CNR, Italy)  Co-Chair
Wan Fokkink (Vrije Universiteit Amsterdam, Netherlands)
Patrice Godefroid (Microsoft Research, USA)
Leszek Holenderski (Philips Research, Netherlands)
Roope Kaivola (Intel, USA)
Stefan Kowalewski (RWTH Aachen, Germany)
Stefania Gnesi (ISTI-CNR, Italy)
Mark Lawford  (McMaster University, Canada)
Stefan Leue (University of Konstanz, Germany)
Radu Mateescu (INRIA Rhone-Alpes, France)
Charles Pecheur (Universitè Catholique de Louvain, Belgium)
Francois Pilarski (Airbus, France)
Ralf Pinger (Siemens, Germany)
Murali Rangarajan (Honeywell, USA)
Marco Roveri  (IRST, Italy)
Ina Schieferdecker (Fraunhofer FOKUS, Germany)
Wilfried Steiner (TTTech, Austria)

PAPER SUBMISSIONS
-----------------
Submissions must be made electronically through the FMICS 2008 Web
site at URL:
http://senldogo0039.springer-sbm.com/fmics2008/servlet/Conference
Papers should be up to 16 pages in LNCS format, with the names and
affiliations of the authors and a clear and informative
abstract. Additional details may be included in a clearly marked
appendix, which will be read at the discretion of the program
committee. All submissions must report on original research. Submitted
papers must not have previously appeared in a journal or  conference
with published proceedings and must not be concurrently
submitted to any other peer-reviewed workshop, symposium, conference
or archival journal. Any partial overlap with any such published or
concurrently submitted paper must be clearly indicated.
Case study papers should identify lessons learned, validate theoretical
results (such as scalability of methods), or provide specific
motivation for further research and development.

PUBLICATION
-----------
Participant's proceedings will be available during the workshop. A
post-workshop proceedings volume will be published by Springer Verlag
in the Lectures Notes in Computer Science series.

web site: click here

Contributed by: Ryan Leduc <leduc aT mcmaster DOt ca>

SELECTIONS FROM AUTOMATICA
VOLUME 44, ISSUE 3
MARCH, 2008

1) Robust supervisory control of timed discrete event systems under
partial observation based on eligible time bounds: The existence
conditions

Seong-Jin Park and Kwang-Hyun Cho

Abstract:

This paper addresses a supervisory control problem for uncertain timed
discrete event systems (DESs) under partial observation. An uncertain
timed DES to be controlled is represented by a set of possible timed
models based on the framework of Brandin and Wonham [(1994).
Supervisory control of timed discrete event systems. IEEE Transactions
on Automatic Control, 39(2), 329-342]. To avoid the state space
explosion problem caused by tick events in the timed models, a notion
of eligible time bounds is proposed for a single timed model obtained
from the set of all possible timed models. Based on this notion, we
present the necessary and sufficient conditions for the existence of a
robust supervisor achieving a given language specification for the
single timed model. Moreover, we show that the robust supervisor can
also achieve the specification for any timed model in the set.

web site: click here

Contributed by: Ryan Leduc <leduc aT mcmaster DOt ca>

SELECTIONS FROM IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS,
PART C: APPLICATIONS AND REVIEWS
VOLUME 38, ISSUE 2
MARCH, 2008

1)  A Survey and Comparison of Petri Net-Based Deadlock Prevention
Policies for Flexible Manufacturing Systems

Li , Z.; Zhou, M.; Wu, N.

Abstract:

Over the last two decades, a great deal of research has been focused on
solving deadlock problems in resource allocation systems such as
computer communication systems, workflow systems, and flexible
manufacturing systems, resulting in a wide variety of approaches. As a
well-defined problem in resource allocation systems, deadlock
prevention based on a Petri net formalism has received an enormous
amount of attention in the literature. This paper intends to review and
compare a variety of Petri net-based deadlock prevention policies
reported in the literature. Their comparison is done in terms of
structural complexity, behavior permissiveness, and computational
complexity. This paper should facilitate engineers in choosing a suited
method for their industrial application cases.

web site: click here

Contributed by: Ryan Leduc <leduc aT mcmaster DOt ca>

SELECTIONS FROM IEEE TRANSACTIONS ON SYSTEMS, MAN AND CYBERNETICS, PART
A
VOLUME: 38, ISSUE: 2
MARCH, 2008

1) On Controllability of Dependent Siphons for Deadlock Prevention in
Generalized Petri Nets

Li, Z.; Zhao, M.

Abstract: 

A fair amount of research has shown the importance of siphons in the
analysis and control of deadlocks in a variety of resource allocation
systems by using a Petri net formalism. In this paper, siphons in a
generalized Petri net are classified into elementary and dependent
ones, as done for ordinary nets in our previous work. Conditions are
derived under which a dependent siphon is controlled by properly
supervising its elementary siphons, which indicates that the
controllability of dependent siphons in an ordinary Petri net is a
special case of that in a generalized one. The application of the
controllability of dependent siphons is shown by considering the
deadlock prevention problem for a class of resource allocation systems,
namely, G-system that allows multiple resource acquisitions and
flexible routings in a flexible manufacturing system with machining,
assembly, and disassembly operations. We develop a monitor-based
deadlock prevention policy that first adds monitors for elementary
siphons only to a G-system plant model such that the resultant net
system satisfies the maximal controlled-siphon property (maximal
cs-property). Then, by linear programming, initial tokens in the
additional monitors are decided such that liveness is enforced to the
supervised system. Also, a simplified live marking relationship for a
G-system between the initial tokens of the source places and those of
the resource places is derived. Finally, the proposed deadlock
prevention methods are illustrated by using an example.

2) Multiparadigm Modeling for Hybrid Dynamic Systems Using a Petri Net
Framework

Lee, J.-S.; Zhou, M. C.; Hsu, P.-L.

Abstract:

Recently, modeling and simulation of hybrid dynamic systems (HDSs) have
attracted much attention. However, since simultaneously dealing with
the discrete and continuous variables is very difficult, most of the
models result in a unified but more complicated and unnatural format.
Moreover, design engineers cannot be allowed to use their preferred
domain models. Based on the multiparadigm modeling concept, this
correspondence proposes a Petri net framework with associated state
equations to model the HDSs. In the presented approach, modeling
schemes of the hybrid systems are separated but combined in a
hierarchical way through specified interfaces. Designers can still work
in their familiar domain-specific modeling paradigms, and the
heterogeneity is hidden when composing large systems. An application to
a rapid thermal process in semiconductor manufacturing is provided to
demonstrate the practicability of the developed approach.

web site: click here

Contributed by: Ryan Leduc <leduc aT mcmaster DOt ca>

SELECTIONS FROM IEEE TRANSACTIONS ON AUTOMATIC CONTROL
VOLUME: 53 ISSUE: 2
MARCH, 2008

1) Modular Control of Discrete-Event Systems With Coalgebra

Komenda, J.; van Schuppen, H.

Abstract:

Modular supervisory control of discrete-event systems, where the
overall system is a synchronous (parallel) product of subsystems, is
considered. The main results of this paper are formulations of
sufficient conditions for the compatibility between the synchronous
product and various operations stemming from supervisory control as
supervised product and supremal controllable sublanguages. These
results are generalized to the case of modules with partial
observations: e.g., modular computation of supremal normal sublanguages
is studied. Coalgebraic techniques based on the coinduction proof
principle are used in our main results. Sufficient conditions are
derived for modular to equal global control synthesis. An algorithmic
procedure for checking the new conditions is proposed and the
computational benefit of the modular approach is discussed and
illustrated by comparing the time complexity of modular and monolithic
computation.

2) Synthesis of Inference-Based Decentralized Control for Discrete
Event Systems

Takai, S.; Kumar , R.

Abstract:

In our past work, we presented a framework for the decentralized
control of discrete event systems involving inferencing over
ambiguities, about the system state, of various local decision makers.
Using the knowledge of the self-ambiguity and those of the others, each
local control decision is tagged with a certain ambiguity level (level
zero being the minimum and representing no ambiguity). A global control
decision is taken to be a "winning'' local control decision, i.e., one
with a minimum ambiguity level. For the existence of a decentralized
supervisor, so that for each controllable event the ambiguity levels of
all winning disablement or enablement decisions are bounded by some
number $N$ (such a supervisor is termed $N$-inferring), the notion of
$N$-inference-observability was introduced. When the given
specification fails to satisfy the $N$-inference-observability
property, an $N$-inferring supervisor achieving the entire
specification does not exist. We first show that the class of
$N$-inference-observable sublanguages is not closed under union
implying that the supremal $N$-inference-observable sublanguage need
not exist. We next provide a technique for synthesizing an
$N$-inferring decentralized supervisor that achieves an
$N$-inference-observable sublanguage  of the specification. The
sublanguage achieved equals the specification language when the
specification itself is $N$-inference-observable.- A formula for the
synthesized sublanguage is also presented. For the special cases of
$N=0$ and $N=1$ , the proposed supervisor achieves the same language as
those reported in  (for $N=0$) and  (for $N=1$ ). The synthesized
supervisor is parameterized by $N$ (the parameter bounding the
ambiguity level), and as $N$ is increased, the supervisor becomes
strictly more permissive in general. Thus, a user can choose $N$ based
on the degree of permissiveness and the degree of computational
complexity desired.

3) Decentralized Diagnosis of Stochastic Discrete Event Systems

Liu, F.; Qiu, D.; Xing, H.; Fan, Z.

Abstract:

We investigate the decentralized diagnosis of stochastic discrete event
systems (SDESs) by using multiple local stochastic diagnosers, each
possessing its own sensors to deal with different information. We
formalize the notions of decentralized diagnosis for SDESs by defining
the concept of codiagnosability for stochastic automata, in which any
communication among the local stochastic diagnosers or to any
coordinators is not involved. These notions are weaker than the
corresponding notions of decentralized diagnosis of classical DESs. A
stochastic system being codiagnosable means that a fault can be
detected by at least one local stochastic diagnoser within a finite
delay. We construct a codiagnoser from a given stochastic system with a
finite number of projections whose each diagnosis component uses the
complete model of the system. We also deal with a number of basic
properties of the codiagnoser. In particular, a necessary and
sufficient condition of the codiagnosability for SDESs is presented,
which generalizes the corresponding results of centralized diagnosis
for SDESs. Also, we give a computing method in detail to check the
codiagnosability of SDESs. As an application of our results, some
examples are described.

4) Decentralized Supervisory Control of Discrete-Event Systems Over
Communication Networks

Mannani , A.; Gohari, P.

Abstract: 

In this paper, we investigate the problem of designing embedded
decentralized discrete-event controllers over communication networks.
It is assumed that there is a path between every pair of processes in
the network. The control objective is specified by a prefix-closed
language that is controllable and observable, but not coobservable. The
paper is focused on communication among processes necessary to meet the
control objective. As such, process models are left unspecified; it is
only required that disabling any of the controllable events do not
block communication among processes. Our findings support the idea that
in the presence of ideal communication channels, the protocol design
for noncoobservable specifications can be reduced to the synthesis of
communicating decentralized supervisors, and we propose solutions for a
restricted class of problems. The paper is concluded with a positive
result for the case where channels are unreliable.

web site: click here