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. Conferences
 2.1  The 26th IASTED International Conference on Modelling, Identification,
     and Control (MIC 2007), Innsbruck, Austria, February 12 - 14,
     2007
 2.2 The Forty-Fourth Annual Allerton Conference on Communication, Control,
     and Computing, Urbana-Champaign, Illinois, USA, September 27 -
     29, 2006

3. Journals
 3.1 Selections from IEEE Transactions on Systems, Man and Cybernetics, Part
     A, Volume: 36, Issue: 3, May 2006
 3.2 Selections from IEEE Transactions on Automatic Control, Volume: 51,
     Issue: 5, May 2006
 3.3 Selections from Automatica, Volume 42, Issue 6, June 2006
 3.4 Selections from IEEE Transactions on Software Engineering, Vol. 32,
     No. 4, April 2006
 3.5 Discrete Event Dynamic Systems, Volume 16, Number 2, April 2006

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:

Welcome to the May 2006 edition of the DESTC newsletter.

Ryan

Contributed by: Ryan Leduc <leduc _at_ mcmaster _dot_ ca>

THE 26TH IASTED INTERNATIONAL CONFERENCE ON MODELLING, IDENTIFICATION,
AND CONTROL (MIC 2007)
Innsbruck, Austria
February 12 - 14, 2007

Sponsors

The International Association of Science and Technology for Development
(IASTED)

    * Technical Committee on Modelling and Simulation
    * Technical Committee on Control

World Modelling and Simulation Forum (WMSF)

Conference Chair

Dr. Luca Bruzzone, University of Genoa, Italy.

Purpose

This conference provides an opportunity for prominent international
specialists, researchers, and engineers to present and observe the
latest research, results, and ideas in the areas of modelling,
identification, and control. MIC 2007 aims to strengthen relations
between industry, research laboratories and universities. All papers
submitted to this conference will be peer evaluated by two reviewers.
Acceptance will be based primarily on originality and contribution.

MIC 2007 will be held in conjunction with the IASTED International
Conference on:
- Artificial Intelligence and Applications (AIA 2007)
- Parallel and Distributed Computing and Networks (PDCN 2007)
- Software Engineering (SE 2007)
- Signal Processing, Pattern Recognition, and Applications (SPPRA 2007)
- Biomedical Engineering (BIOMED 2007)
- Computer Graphics and Imaging (CGIM 2007) 

Scope

The topics of interest include, but are not limited to:
Modelling

    * Model Development
    * Bond Graph Modelling
    * Statistical and Probabilistic Modelling
    * Numerical Methods
    * Mathematical Modelling
    * System Theory
    * Dynamic Modelling
    * 3-Dimensional Modelling
    * Continuous and Discrete Methodology
    * Simulation
    * Times Series Analysis
    * Multi-Paradigm Modelling
    * Environmental Modelling
    * Energy and Power Systems Modelling
    * Biomedical Modelling
    * Performance Modelling

Identification

    * Estimation
    * Filtering
    * Parametric Identification
    * Non-Parametric Identification
    * Structural Identification
    * Validation

Control

    * Control Theory
    * Linear Control
    * Non-Linear Control
    * Optimization
    * Intelligent Control
    * Adaptive Control
    * Predictive Control
    * Fuzzy Control
    * Stochastic Control
    * Process Control
    * PID Control
    * Robust Control
    * Variable Structure Control
    * Discrete Events
    * Stability
    * Control using Neural Networks
    * Computer Control
    * Distributed Parameter Control Systems

IMPORTANT DEADLINES
Submissions due:	      September 15, 2006
Notification of acceptance:   November 1, 2006
Camera-ready manuscripts due: November 15, 2006
Registration Deadline:	      December 1, 2006

web site: click here

Contributed by: Ryan Leduc <leduc _at_ mcmaster _dot_ ca>

THE FORTY-FOURTH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL,
AND COMPUTING
Urbana-Champaign, Illinois, USA
September 27 - 29, 2006

The Forty-Fourth Annual Allerton Conference on Communication, Control,
and Computing will be held from Wednesday, September 27 through Friday,

September 29, 2006, at 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. 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. 

Plenary lecture: Professor Sergio Verd, of Princeton University, will 
deliver this year's plenary lecture.  It is scheduled for Friday,
September 29, 2006.

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 five-page summaries in the Proceedings.

For reviewing purposes of 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 Friday, June 30, 2006, following the 
instructions at the Conference website. 

Authors will be notified of acceptance via e-mail by August 4, 2006, 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-Chairs: Andrew Singer and Christoforos Hadjicostis
Email: allerton@csl.uiuc.edu	
COORDINATED SCIENCE LABORATORY AND THE
DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING
University of Illinois at Urbana-Champaign

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: 36, ISSUE: 3
MAY, 2006

1) Autonomic-Computing Approach to Secure Knowledge Management: A
Game-Theoretic Analysis

Arora, H.; Mishra, B.K.; Raghu, T.S.

Abstract:

The explosion of knowledge management systems (KMS) and the need for
their wide accessibility and availability has created an urgent need
for reassessing the security practices and policies in organizations.
Security of these assets is a day-to-day job placing a tremendous
cognitive load on information-technology (IT) professionals, which can
make it almost impossible to manage the security aspects of KMS.
Autonomic-computing systems are well suited to manage KMS, as they use
high-level system objectives provided by administrators as the basis
for managing the security of KMS. The authors model the self-protection
and self-healing configuration attributes in autonomic systems through
game-theoretic models. The proposed modeling approach progressively
moves from a manual intervention-oriented security setup to an
autonomic security setup. This allows the authors to compare and
contrast the different approaches and provide insights on their
applicability to different security environments. The authors find that
moving to a partial autonomic system with self-healing mechanisms can
provide a stable environment for securing enterprise knowledge assets
and can reduce hacking. It is beneficial to implement an autonomic
system when manual investigation costs are higher and/or when the
volume of malicious traffic is very low. An autonomic approach is
especially attractive when it is difficult to impose penalties on
malicious users. Autonomic systems can be effective in securing
organizational knowledge assets and in reducing the potential damage
from malicious users.

2) Computing Minimal Siphons in Petri Net Models of Resource Allocation
Systems: A Parallel Solution

 Tricas, F.; Ezpeleta, J.

Abstract:

Siphons are related to the liveness properties of Petri net models.
This relation is strong in the case of resource allocation systems
(RASs). Siphons can be used in these systems in order to both
characterize and prevent/avoid deadlock situations. However, the
computation of these structural components can be very time consuming
or, even, impossible. Moreover, if, in general, the complete
enumeration of the set of minimal siphons must be avoided (there can
exist an exponential number of such components), some deadlock
prevention methods rely on its (complete or partial) computation and
enumeration. The special syntactical constraints of some classes of
RASs can help in developing specific algorithms to compute siphons in a
more efficient way. In this work, a known method for siphon computation
is adapted to get advantage of the special (syntactical) structure of a
class of RASs; a parallel implementation is proposed and some
experimental results are presented.

web site: click here

Contributed by: Ryan Leduc <leduc At mcmaster _dot_ ca>

SELECTIONS FROM IEEE TRANSACTIONS ON AUTOMATIC CONTROL
VOLUME: 51, ISSUE: 5
MAY, 2006

1) Control of Nondeterministic Discrete-Event Systems for Bisimulation
Equivalence

Zhou, C.; Kumar, R.; Jiang, S.

Abstract:

Most prior work on supervisory control of discrete event systems is for
achieving deterministic specifications, expressed as formal languages.
In this paper we study supervisory control for achieving
nondeterministic specifications. Such specifications are useful when
designing a system at a higher level of abstraction so that lower level
details of system and its specification are omitted to obtain higher
level models that may be nondeterministic. Nondeterministic
specifications are also meaningful when the system to be controlled has
a nondeterministic model due to the lack of information (caused for
example by partial observation or unmodeled dynamics). Language
equivalence is not an adequate notion of behavioral equivalence for
nondeterministic systems, and instead we use the finest known notion of
equivalence, namely the bisimulation equivalence. Choice of
bisimulation equivalence is also supported by the fact that
bisimulation equivalence specification is equivalent to a specification
in the temporal logic of$mu $-calculus that subsumes the complete
branching-time logic CTL*. Given nondeterministic models of system and
its specification, we study the design of a supervisor (possibly
nondeterministic) such that the controlled system is bisimilar to the
specification. We obtain a small model theorem showing that a
supervisor exists if and only if it exists over a certain finite state
space, namely the power set of Cartesian product of system and
specification state spaces. Also, the notion of state-controllability
is introduced as part of a necessary and sufficient condition for the
existence of a supervisor. In the special case of deterministic
systems, we provide an existence condition that can be verified
polynomially in both system and specification states, when the
existence condition holds.

2) Nonblocking Supervisory Control of State Tree Structures

Ma, C.; Wonham, W.M.

Abstract:

It is well known that the nonblocking supervisory control problem is
NP-hard, subject in particular to state space explosion that is
exponential in the number of system components. In this paper we
propose to manage complexity by organizing the system as a state tree
structure (STS). STS are an adaptation of statecharts to supervisory
control theory. Based on STS we present an efficient recursive symbolic
algorithm that can perform nonblocking supervisory control design (in
reasonable time and memory) for systems of state size$10^24$and higher.
The resulting controllers are tractable and readily comprehensible.

3) On the Supervisory Control of Multiagent Product Systems

Romanovski, I.; Caines, P.E.

Abstract:

In this note, we use the formal framework of multiagent (MA) product
systems (introduced and developed in previous works) for the analysis
of complex systems. The results of this note constitute a natural
extension of the classical supervisory control results for scalar
systems to the more general MA product system case. The notion of MA
controllability is introduced and is shown to essentially constitute a
necessary and sufficient condition for the synthesis of an MA
supervisor.

4) On Minimal Representations of Petri Net Languages

Sreenivas, R.S.

Abstract:

Given a measure of size of a labeled Petri net, we consider the
existence of a procedure that takes as input a description of an
arbitrary, labeled Petri net, and returns a description of a (possibly
different) labeled Petri net with the smallest size that generates the
same language as the input. We refer to such procedures as minimization
procedures. In this note, we investigate the existence of minimization
procedures for a variety of measures. We show that these procedures
cannot exist for Petri net languages for a large class of measures.
However, for families of Petri net languages where controllability (cf.
[15]), and consequently language-containment, is decidable [16], there
can be minimization procedures for a restricted class of measures.
After showing that minimization procedures for a family of measures are
intractable for languages generated by bounded Petri nets, it is argued
that a similar conclusion has to be reached for any family of Petri net
languages that includes the family of regular languages for which there
are minimization procedures.

3) Delay-Robust Supervisory Control of Discrete-Event Systems With
Bounded Communication Delays

Park, S.-J.; Cho, K.-H.

Discrete-event systems (DESs) are often controlled by remote
supervisors through communication networks and thereby the sensor
messages or the control commands can experience nonnegligible
transmission delays depending on the network traffic. A series of
uncontrollable events can then unexpectedly occur before a proper
control action is actually applied to the DES for an observed event
sequence. For such supervised systems with bounded communication
delays, we present in this note a notion of delay-nonconflictingness
for a language specification and based on this notion we further
investigate the existence conditions of a delay-robust nonblocking
supervisor that can achieve the given language specification.

web site: click here

Contributed by: Ryan Leduc <leduc _at_ mcmaster _dot_ ca>

SELECTIONS FROM AUTOMATICA
VOLUME 42, ISSUE 6
JUNE, 2006

1) Suboptimal supervisory control of Petri nets in presence of
uncontrollable transitions via monitor places

Francesco Basile, Pasquale Chiacchio and Alessandro Giua

Abstract:

This paper deals with the problem of enforcing generalized mutual
exclusion constraints (GMEC) on place/transition nets with
uncontrollable transitions. An efficient control synthesis technique,
which has been proposed in the literature, enforces GMEC constraints by
introducing monitor places to create suitable place invariants. The
method has been shown to be maximally permissive and to give a unique
control structure in the case that the set of legal markings is
controllable. This paper investigates on and formally shows that the
class of controllers obtained by this technique may not have a supremal
element for uncontrollable specifications. Moreover, it is shown that
the family of monitor places enforcing an uncontrollable specification
can be parameterized with respect to the solution of a linear system of
equation. An algorithm to obtain such parameterization is presented
here.

web site: click here

Contributed by: Ryan Leduc <leduc _at_ mcmaster _dot_ ca>

SELECTIONS FROM IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
VOL. 32, NO. 4
APRIL, 2006

1) Threat-Driven Modeling and Verification of Secure Software Using
Aspect-Oriented Petri Nets

Dianxiang Xu, Kendall E. Nygard

Abstract:

Design-level vulnerabilities are a major source of security risks in
software. To improve trustworthiness of software design, this paper
presents a formal threat-driven approach, which explores explicit
behaviors of security threats as the mediator between security goals
and applications of security features. Security threats are potential
attacks, i.e., misuses and anomalies that violate the security goals of
systems' intended functions. Security threats suggest what, where, and
how security features for threat mitigation should be applied. To
specify the intended functions, security threats, and threat
mitigations of a security design as a whole, we exploit aspect-oriented
Petri nets as a unified formalism. Intended functions and security
threats are modeled by Petri nets, whereas threat mitigations are
modeled by Petri net-based aspects due to the incremental and
crosscutting nature of security features. The unified formalism
facilitates verifying correctness of security threats against intended
functions and verifying absence of security threats from integrated
functions and threat mitigations. As a result, our approach can make
software design provably secured from anticipated security threats and,
thus, reduce significant design-level vulnerabilities. We demonstrate
our approach through a systematic case study on the threat-driven
modeling and verification of a real-world shopping cart application.

web site: click here

Contributed by: Ryan Leduc <leduc _at_ mcmaster _dot_ ca>

DISCRETE EVENT DYNAMIC SYSTEMS
VOLUME 16, NUMBER 2
APRIL, 2006

1) Model Checking of Time Petri Nets Using the State Class Timed
Automaton

Didier Lime and Olivier H. Roux

Abstract:

 In this paper, we propose a method for building the state class graph
of a bounded time Petri net (TPN) as a timed automaton (TA), which we
call the state class timed automaton. We consider bounded TPN, whose
underlying net is not necessarily bounded. We prove that our
translation preserves the behavioral semantics of the TPN (the initial
TPN and the obtained TA are proved timed-bisimilar). It allows us to
check real-time properties on TPN by using the state class TA. This can
be done efficiently thanks to a reduction of the number of clocks. We
have implemented the method, and give some experimental results
illustrating the efficiency of the translation algorithm in terms of
number of clocks. Using the state class TA, we also give a framework
for expressing and efficiently verifying TCTL properties on the initial
TPN.

2) A Generalized Kalman Filter for Fixed Point Approximation and
Efficient Temporal-Difference Learning

David Choi and Benjamin Van Roy

Abstract:

The traditional Kalman filter can be viewed as a recursive stochastic
algorithm that approximates an unknown function via a linear
combination of prespecified basis functions given a sequence of noisy
samples. In this paper, we generalize the algorithm to one that
approximates the fixed point of an operator that is known to be a
Euclidean norm contraction. Instead of noisy samples of the desired
fixed point, the algorithm updates parameters based on noisy samples of
functions generated by application of the operator, in the spirit of
Robbins-Monro stochastic approximation. The algorithm is motivated by
temporal-difference learning, and our developments lead to a possibly
more efficient variant of temporal-difference learning. We establish
convergence of the algorithm and explore efficiency gains through
computational experiments involving optimal stopping and queueing
problems.

3) Modeling and Control of Hybrid Timed Event Graphs with Multipliers
Using (Min, +) Algebra

S. Hamaci, J.-L. Boimond, S. Lahaye

Abstract:

We study a subclass of Petri nets, called hybrid timed event graphs
with multipliers, or equivalently, hybrid timed weighted marked graphs,
composed of continuous and discrete graphs interconnected among
themselves. Such graphs can be modeled by using a particular algebra,
called dioid, defined on a set of operators and endowed with the
pointwise minimum operation as addition and the composition operation
as multiplication. A just in time control method of these graphs based
on residuation theory is proposed.

4) A New Class of Supervisors for Timed Discrete Event Systems Under
Partial Observation

Shigemasa Takai and Toshimitsu Ushio

Abstract:

Brandin and Wonham have developed a supervisory control framework for
timed discrete event systems (TDESs) in order to deal with not only
logical specifications but also temporal specifications. Lin and Wonham
have extended this framework to the partial observation case, and
presented necessary and sufficient conditions for the existence of a
nonblocking supervisor under partial observation. In this paper, we
define a new class of supervisors for TDESs under partial observation.
We then present necessary and sufficient conditions for the existence
of a nonblocking supervisor defined in this paper. These existence
conditions of our supervisor are weaker than those of Lin and Wonham's
supervisor. Note, however, that the price that must be paid to weaken
the existence conditions is the higher computational cost. Moreover,
given a closed regular language, we study computation of a sublanguage
that satisfies the existence conditions of our supervisor. We present
an algorithm for computing such a sublanguage larger than the supremal
closed, controllable, and normal sublanguage.

5) Constrained Ordinal Optimization: A Feasibility Model Based Approach

Xiaohong Guan, Chen Song, Yu-Chi Ho, Qianchuan Zha

Abstract:

Ordinal Optimization (OO) is a useful simulation-based approach for
stochastic optimization problems such as the problems in Discrete Event
Dynamic Systems (DEDS). However, OO cannot be applied directly for the
problem since many infeasible decisions cannot be excluded from ordinal
comparison without extensive computation involving the expectation
operation. In this paper, a new approach for solving constrained
ordinal optimization (COO) problems is presented. The key idea of our
method for constrained OO problems is to estimate the feasibility of
decisions and to choose selected subset based on the estimated
feasibility. Any crude method such as the one based on rough set theory
developed in our previous work can be applied to determine the decision
feasibility efficiently. The algorithm for subset selection and the
procedure of Blind Picking with Feasibility Model (BPFM) for COO are
derived in the paper. The infeasible decisions are excluded by an
imperfect feasibility model in the procedure of subset selection. The
performance of the new method is evaluated and compared with the
regular OO method. Numerical testing with two examples including the
planning problem of a practical remanufacturing system shows that to
meet the same required alignment probability, BPFM is more efficient
than pure Blind Picking in regular OO.

web site: click here