DEVS

DEVS abbreviating Discrete Event System Specification is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems which might be described by state transition tables, and continuous state systems which might be described by differential equations, and hybrid continuous state and discrete event systems. DEVS is a timed event system.
Contents
History
DEVS is a formalism for modeling and analysis of discrete event systems (DESs). The DEVS formalism was invented by Dr. Bernard P. Zeigler, who is a professor at the University of Arizona. DEVS was introduced to the public in Zeigler's first book, Theory of Modeling and Simulation, in 1976, while Zeigler was an associate professor at University of Michigan. DEVS can be seen as an extension of the Moore machine formalism ^{[1]}, which is a finite state automaton where the outputs are determined by the current state alone (and do not depend directly on the input). The extension was done by
 associating a lifespan with each state [Zeigler76],
 providing a hierarchical concept with an operation, called coupling [Zeigler84].
Since the lifespan of each state is a real number (more precisely, nonnegative real) or infinity, it is distinguished from discrete time systems, sequential machines, and Moore machines, in which time is determined by a tick time multiplied by nonnegative integers. Moreover, the lifespan can be a random variable; for example the lifespan of a given state can be distributed exponentially or uniformly. The state transition and output functions of DEVS can also be stochastic.
Zeigler proposed a hierarchical algorithm for DEVS model simulation in 1984 [Zeigler84] which was published in Simulation journal in 1987. Since then, many extended formalism from DEVS have been introduced with their own purposes: DESS/DEVS for combined continuous and discrete event systems, PDEVS for parallel DESs, GDEVS for piecewise continuous state trajectory modeling of DESs, RTDEVS for realtime DESs, CellDEVS for cellular DESs, FuzzyDEVS for fuzzy DESs, Dynamic Structuring DEVS for DESs changing their coupling structures dynamically, and so on. In addition to its extensions, there are some subclasses such as SPDEVS and FDDEVS have been researched for achieving decidability of system properties.
Due to the modular and hierarchical modeling views, as well as its simulationbased analysis capability, the DEVS formalism and its variations have been used in many application of engineering (such as hardware design, hardware/software codesign, communications systems, manufacturing systems) and science (such as biology, and sociology)
Formalism
 Intuitive Example
DEVS defines system behavior as well as system structure. System behavior in DEVS formalism is described using input and output events as well as states. For example, for the pingpong player of Fig. 1, the input event is ?receive, and the output event is !send. Each player, A, B, has its states: Send and Wait. Send state takes 0.1 seconds to send back the ball that is the output event !send, while Wait lasts the state until the player receives the ball that is the input event ?receive.
The structure of pingpong game is to connect two players: Player A 's output event !send is transmitted to Player B 's input event ?receive, and vice versa.
In the classic DEVS formalism, Atomic DEVS captures the system behavior, while Coupled DEVS describes the structure of system.
The following formal definition is for Classic DEVS [ZKP00]. In this article, we will use the time base, that is the set of nonnegative real numbers; the extended time base, that is the set of nonnegative real numbers plus infinity.
Atomic DEVS
An atomic DEVS model is defined as a 7tuple
M = < X,Y,S,ta,δ_{ext},δ_{int},λ > where
 X is the set of input events;
 Y is the set of output events;
 S is the set of sequential states (or also called the set of partial states);
 is the time advance function which is used to determine the lifespan of a state;
 is the external transition function which defines how an input event changes a state of the system, where is the set of total states, and t_{e} is the elapsed time since the last event;
 is the internal transition function which defines how a state of the system changes internally (when the elapsed time reaches to the lifetime of the state);
 is the output function where and is a silent event or an unobserved event. This function defines how a state of the system generates an output event (when the elapsed time reaches to the lifetime of the state);
Deterministic DEVS and Nondeterministic DEVS
Let A and B be two arbitrary sets. Then function is called deterministic if for , f(a) is identical any time. Otherwise, f is called nondeterministic.
A DEVS M = < X,Y,S,ta,δ_{ext},δ_{int},λ > is called deterministic if ta, δ_{ext}, δ_{int} and λ are deterministic. Otherwise, M is called nondeterministic.
 The atomic DEVS Model for PingPong Players
The atomic DEVS model for player A of Fig. 1 is given Player= < X,Y,S,s_{0},ta,δ_{ext},δ_{int},λ > such that
and
Both Player A and Player B are deterministic DEVS models.
Behavior of Atomic DEVS
Simply speaking, there are two cases that an atomic DEVS model M can change its state : (1) when an external input comes into the system M; (2) when the elapsed time t_{e} reaches the lifespan of s which is defined by ta(s). (At the same time of (2), M generates an output which is defined by λ(s).) .
For formal behavior description of given an Atomic DEVS model, refer to the page Behavior of DEVS. Computer algorithms to implement the behavior of a given Atomic DEVS model are available at Simulation Algorithms for Atomic DEVS.
Coupled DEVS
The coupled DEVS defines which subcomponents belong to it and how they are connected with each other. A coupled DEVS model is defined as a 8tuple
N = < X,Y,D,{M_{i}},C_{xx},C_{yx},C_{yy},Select > where
 X is the set of input events;
 Y is the set of output events;
 D is the name set of subcomponents;
 {M_{i}} is the set of subcomponents where for each can be either an atomic DEVS model or a coupled DEVS model.
 is the set of external input couplings;
 is the set of internal couplings;
 is the external output coupling function;
 is the tiebreaking function which defines how to select the event from the set of simultaneous events;
 The coupled DEVS model for PingPong Game
The pingpong game of Fig. 1 can be modeled as an coupled DEVS model N = < X,Y,D,{M_{i}},C_{xx},C_{yx},C_{yy},Select > where X = {};Y = {};D = {A,B}; M_{A} and M_{B} is described as above; C_{xx} = {}; C_{yx} = {(A.!send,B.?receive),(B.!send,A.?receive)}; and C_{yy}(A.!send) = ϕ,C_{yy}(B.!send) = ϕ.
Behavior of Coupled DEVS
Simply speaking, like the behavior of the atomic DEVS class, a coupled DEVS model N changes its components' states (1) when an external event comes into N; (2) when one of components M_{i} where executes its internal state transition and generates its output . In both cases (1) and (2), a triggering event is transmitted to all influencees which are defined by coupling sets C_{xx},C_{yx}, and C_{yy}.
For formal definition of behavior of the coupled DEVS, you can refer to Behavior of Coupled DEVS. Computer algorithms to implement the behavior of a given coupled DEVS mode are available at Simulation Algorithms for Coupled DEVS.
Analysis Methods
Simulation for Discrete Event Systems
The simulation algorithm of DEVS models considers two issues: time synchronization and message propagation. Time synchronization of DEVS is to control all models to have the identical current time. However, for an efficient execution, the algorithm makes the current time jump to the most urgent time when an event is scheduled to execute its internal state transition as well as its output generation. Message propagation is to transmit a triggering message which can be either an input or output event along the associated couplings which are defined in a coupled DEVS model. For more detailed information, the reader can refer to Simulation Algorithms for Atomic DEVS and Simulation Algorithms for Coupled DEVS.
Simulation for Continuous State Systems
By introducing a quantization method which abstracts a continuous segment as a piecewise const segment, DEVS can simulate behaviors of continuous state systems which are described by networks of differential algebraic equations. This research has been initiated by Zeigler in 90's^{[3]} and many properties have been clarified by Prof. Kofman in 2000's and Dr. Nutaro. In 2006, Prof. Cellier who is the author of Continuous System Modeling[Cellier91], and Prof. Kofman wrote a text book, Continuous System Simulation[CK06] in which Chapters 11 and 12 cover how DEVS simulates continuous state systems. Dr. Nutaro's book [Nutaro10], covers the discrete event simulation of continuous state systems too.
Verification for Discrete Event Systems
As an alternative analysis method against the samplingbased simulation method, an exhaustive generating behavior approach, generally called verification has been applied for analysis of DEVS models. It is proven that infinite states of a given DEVS model (especially a coupled DEVS model ) can be abstracted by behaviorally isomorphic finite structre, called a reachability graph when the given DEVS model is a subclass of DEVS such as SchedulePreserving DEVS (SPDEVS) and Finite & Deterministic DEVS (FDDEVS) [HZ09]. As a result, based on the rechability graph, (1) deadlock and livelock freeness as qualitative properties are decidable with SPDEVS [Hwang05] and FDDEVS [HZ06], and (2) min/max processing time bounds as a quantitative property are decidable with SPDEVS so far by 2009.
Variations of DEVS
Extensions (Superclassing)
Numerous extensions of the classic DEVS formalism have been developed in the last decades. Among them formalisms which allow to have changing model structures while the simulation time evolves.
GDEVS, Parallel DEVS, Dynamic Structuring DEVS, CellDEVS [Wainer09], dynDEVS, FuzzyDEVS, GKDEVS, mlDEVS, Symbolic DEVS, RealTime DEVS, rhoDEVS
Restrictions (Subclassing)
There are some subclasses known as SchedulePreserving DEVS (SPDEVS) and Finite and Deterministic DEVS (FDDEVS) which were designated to support verification analysis. SPDEVS and FDDEVS whose expressiveness are E(SPDEVS) E(FDDEVS) E(DEVS) where E(formalism) denotes the expressiveness of formalism.
See also
DEVS Related Articles
 Event Segment
 Timed Event System
 Verifiable subclasses of DEVS: SPDEVS, FDDEVS
 Behavior of Atomic DEVS
 Behavior of Coupled DEVS
 Simulation Algorithms for Atomic DEVS
 Simulation Algorithms for Coupled DEVS
Other Formalisms
 Automata Theory: a formal method for state transition systems
 Finite State Machine: a state transition machine with finite sets of events and states
 Petri Nets: a graphical representation of state and transition relations
 Markov Chain: a stochastic process in which the future will be determined by the current
External links to DEVS Research Groups
Alphabetical Order
 DEVS Standardization Group: http://celldevs.sce.carleton.ca/devsgroup/
 DEVS Study Group: http://tech.groups.yahoo.com/group/DEVSTD/
 DEVS Tools: http://celldevs.sce.carleton.ca/devsgroup/?q=node/8
 Dr. Barros' Lab at Universidade de Coimbra: http://eden.dei.uc.pt/~barros/
 Dr. Giambiasi's Lab at Laboratoire des Sciences de I'Information et des Systemes (LSIS): http://www.lsis.org/fiche.php?id=72&page=&afficher=&presentation_publis=&processus=ok
 Dr. Hu's Lab at Georgia State University: http://www.cs.gsu.edu/~cscxlh/
 Dr. Hwang's Homepage: http://moonho.hwang.googlepages.com/
 Dr. Jamshidi's Virtual Laboratory for Autonomous Agents at University of New Mexico: http://vlab.unm.edu/
 Dr. Kim's Systems Modeling Simulation Lab at KAIST: http://smslab.kaist.ac.kr/
 Dr. Kofman's Laboratory for System Dynamics and Signal Processing at Universidad Nacional de Rosario: http://www.fceia.unr.edu.ar/lsd/
 Dr. Mittal's startup Dunip Technologies: http://www.duniptechnologies.com
 Dr. Tolk's Interoperability and Composability Research Group at the Virginia Modeling, Analysis and Simulation Center
 Dr. Uhrmacher's Modeling and Simulation Group at University of Rostock: http://wwwmosi.informatik.unirostock.de/mosi
 Dr. Vangheluwe's Modeling, Simulation & Design Lab at McGill University: http://msdl.cs.mcgill.ca/
 Dr. Wainer's Lab at Carleton University: http://www.sce.carleton.ca/faculty/wainer/ (Lab).
 Dr. Zeigler and Dr. Sarjoughian's Arizona Center for Integrative Modeling and Simulation (ACIMS): http://www.acims.arizona.edu
 Dr. Zhang's Homepage: http://www.ece.arizona.edu/~mingz/
DEVS Tools
 adevs: A C++ library for constructing discrete event simulations based on the Parallel DEVS and Dynamic DEVS (dynDEVS) formalisms
 CD++ An environment for development of DEVS and Cellular DEVS formalisms.
 CD++Modeler A graphical interface for modeling DEVS and CellDEVS applications (with source code).
 CD++Builder An Eclipse Plugin for developing DEVS and CellDEVS models (with source code).
 CoSMoSim: A unified logical, visual, and persistence environment for specifying families of DEVS, Cellular Automata, and XML models. It supports simulation of parallel DEVS models [open source at SourceForge].
 DEVS++: C++ Open Source Library of DEVS Formalism for simulation analysis
 DEVS#: C# Open Source Library of DEVS Formalism for simulation and verification analysis
 DEVS/C++ Implementation of Parallel DEVS in C++.
 DEVS/HLA/CORBA Extends DEVSJAVA and DEVSC++ with HLA and CORBA.
 DEVSJAVA It supports Parallel DEVS models with software realtime, variable structure, 2D/3D cellular automata, and animation.
 DEVSim++
 DEVSSuite Next generation of DEVSJAVA supporting integrated automated design of experiments, runtime data trajectory plotting, and animation with multiple degrees of control for simulation execution, plotting, and animation speeds [open source at SourceForge]
 GALATEA
 JAMES II M&S Framework for many different formalisms including PDEVS and mlDEVS.
 JDEVS
 LSIS DME
 Mimosa
 PF3S
 PowerDEVS A general purpose software tool for DEVS modeling and simulation oriented to the simulation of hybrid systems
 Python DEVS
 SimBeans
 SmallDEVS
 VLE An environment and C++ libraries for development of DEVS, Cellular DEVS, DESS, QSS, Celluar QSS, Petri net and UML Statechart formalisms.
Footnotes
 ^ automata were the mathematical models of Dr. Zeigler's Ph.D. thesis [Zeigler68]
 ^ We can also define the external transition function as where such that for a total state , is a partial state, is the lifespan of s, and is the elapsed time since last update of t_{s}. For more how to understand this function, refer to the article, Behavior of DEVS.
 ^ the use of quantized values in order to simulate continuous systems by means of a discrete event method was empirically tried out a few years sooner  in the early 90's  by a French engineer <We need any reference for this argument>. He was then working for a company spun off from University of Valenciennes and HainautCambresis, and now part of the Schneider Electric. This quantization^{[disambiguation needed ]} is a feature of a simulation software of which this engineer is the conceptor and main developer, that is used for PLC programs checking and operator training.
References
 [Cellier91] Francois E. Cellier (1991). Continuous System Modeling (first ed.). Springer. ISBN 9780387975023.
 [CK06] Francois E. Cellier and Ernesto Kofman (2006). Continuous System Simulation (first ed.). Springer. ISBN 9780387261027.
 [Hwang05] M.H. Hwang, "Tutorial: Verification of Realtime System Based on SchedulePreserved DEVS", Proceedings of 2005 DEVS Symposium, San Diego, Apr. 28, 2005, ISBN 1565552908,
 [HZ06] M.H. Hwang and B. P. Zeigler, "A Modular Verification Framework using Finite and Deterministic DEVS", Proceedings of 2006 DEVS Symposium, pp57–65, Huntsville, Alabama, USA,
 [HZ09] M.H. Hwang and B.P. Zeigler, "Reachability Graph of Finite and Deterministic DEVS Networks", IEEE Transactions on Automation Science and Engineering, Volume 6, Issue 3, 2009, pp. 454–467,
 [Nutaro10] James Nutaro (2010). Building Software for Simulation: Theory, Algorithms, and Applications in C++ (first ed.). Wiley. ISBN 0470414693.
 [Sarjoughian09] Hessam S. Sarjoughian and Vignesh Elamvazhuthi (2009). CoSMoS: A Visual Environment for ComponentBased Modeling, Experimental Design, and Simulation. Proceedings of the International Conference on Simulation Tools and Techniques.
 [Wainer09] Gabriel A. Wainer (2009). DiscreteEvent Modeling and Simulation: A Practitioner's Approach (first ed.). CRC Press. ISBN 9781420053364.
 [Wainer10] Gabriel A. Wainer and Pieter Mosterman Eds. (2010). DiscreteEvent Modeling and Simulation: Theory and Applications (first ed.). CRC Press. ISBN 9781420072334.
 [Zeiger68] Bernard Zeigler (1968). On the Feedback Complexity of Automata (Ph.D. Thesis ed.). University of Michigan.
 [Zeigler76] Bernard Zeigler (1976). Theory of Modeling and Simulation (first ed.). Wiley Interscience, New York. ISBN 0127784551.
 [Zeigler84] Bernard Zeigler (1984). Multifacetted Modeling and Discrete Event Simulation. Academic Press, London; Orlando. ISBN 9780127784502.
 [Zeigler87] Bernard Zeigler (1987). "Hierarchical, modular discreteevent modelling in an objectoriented environment". Simulation 49 (5): 219–230. doi:10.1177/003754978704900506.
 [ZKP00] Bernard Zeigler, Tag Gon Kim, Herbert Praehofer (2000). Theory of Modeling and Simulation (second ed.). Academic Press, New York. ISBN 9780127784557.
Categories: Automata theory
 Formal specification languages
Wikimedia Foundation. 2010.
Look at other dictionaries:
DEVS — Saltar a navegación, búsqueda DEVS es un acrónimo del inglés para referirse a Discrete Event System Specification (Especificación de Sistemas de Eventos Discretos). El término es ahora estándar en el campo de la Simulación para referirse a un… … Wikipedia Español
DEVS — Discrete Event System Specification DEVS (de l anglais Discrete Event System Specification) est un formalisme modulaire et hiérarchique pour la modélisation, la simulation et l analyse de systèmes complexes qui peuvent être des systèmes à… … Wikipédia en Français
Devs — Div Pour les articles homonymes, voir DIV. Un div est un esprit maléfique de la mythologie iranienne qui aime causer la douleur et la destruction. Le terme signifie littéralement démon . Leur chef est Ahriman. Leurs opposants sont les Izeds ou… … Wikipédia en Français
DEVS — Ziynet etmek, süslemek. * Bir şeyi ayağı ile basıp çiğnemek … Yeni Lügat Türkçe Sözlük
DEVŞ — Fâsid olmak … Yeni Lügat Türkçe Sözlük
Devs Fidivs — DEVS FIDIVS, sieh Fidius … Gründliches mythologisches Lexikon
Devs Iratvs — Infobox Album  Name = Devs Iratvs Type = Album Artist = Arthemesia Released = 2001 Recorded = Genre = Melodic black metal Length = 46:56 Label = Native North Records Producer = Reviews = Last album = The Archaic Dreamer (1999) This album = Devs… … Wikipedia
SPDEVS — abbreviating Schedule Preserving Discrete Event System Specification is a formalism for modeling and analyzing discrete event systems in both simulation and verification ways. SP DEVS also provides modular and hierarchical modeling features which … Wikipedia
Behavior of DEVS — Behaviors of a given DEVS model is a set of sequences of timed events including null events, called event segments which make the model move one state to another within a set of legal states. To define this way, the concept of a set of illegal… … Wikipedia
Bonvs Devs — BONVS DEVS, Gr. Ἀγαθὸς δεὸς, ου, war ein Gott der Arkadier, dessen Tempel am Wege nach dem Berge Mänalus zu stund. Pausan. Arcad. 26 … Gründliches mythologisches Lexikon