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