Search

A68SIM is a program system based on ALGOL 68, containing a set of procedures and operator definitions, which are designed to aid the writing of ALGOL-68-programs for discrete event simulation. A language with the power and flexibility of ALGOL 68 provides a variety of means for carrying out simulations, and A68SIM is just one of the possible approaches. A68SIM is a set of basic elements, and proceeding from these elements the user has a lot of opportunities in formulating and solving his simulation problem. This paper describes some features of A68SIM, originally developed by D.C.S. Shearn, Division of Economic Studies, University of Sheffield, U.K. and since some years implemented on our CD CYBER 172 and CYBER 76 at the Regional Computer Center at the University of Hannover, and compares it with SIMULA 67 and GASP IV, two other simulation “languages” at our site.

We examine a modular approach to the synthesis of supervisory controls for discrete-event systems. Discrete-event systems are modelled by automata together with a mechanism for enabling and disabling a subset of state transitions. The basic problem of interest is to ensure by appropriate supervision that the closed loop behavior of the system lies within a given legal behavior. Assuming this behavior can be decomposed into an intersection of component restrictions we determine conditions under which it is possible to synthesize the appropriate control in a modular fashion.

This paper studies the problem of controlling discrete event systems as formulated by [Ramadge and Wonham 1987]. The optimal D-supervisor is introduced, which requires the minimal number of switchings. A complete characterization of such controllers as well as a procedure for its construction is given.

The past few years have seen significant advances in computer technology and its incorporation into engineering and other applications. In these applications, the various signals acting in and on systems occur as data sequences occurring at discrete time instants. Some familiar examples of systems controlled by discrete data sequences are: 1. National Economies 2. Radar-tracking systems 3. Data-transmission links We note that in such systems the information is available only in samples. In this chapter we present methods for the analysis of systems incorporating digital devices, which are called discrete-time systems. As used here, the term discrete system refers to any system whose operation or output is conveniently described on a discrete time scale even though the system characteristics may in general be given in continuous time.

We study the Dynamic Programming Equation arising in the problem of stochastic control in discrete time over an infinite horozon. The data are unbounded, in which case the solution is not unique. Our results deal with the structure of the set of solutions.

An extended model for a class of discrete event systems is proposed. Based on the model formulated by Ramadge and Wonham [1], we introduce the notion of a nondeterministic supervisor and extend the definition of a controllable language [1]. Some results on the existence of deterministic and nondeterministic supervisors to achieve a given closed loop language are presented. We briefly discuss closure properties of controllable languages in the extended model.

The theory and techniques of discrete event modelling and simulation have advanced substantially over the past two decades. An integrative approach, making use of discrete event formalisms, should now be used when developing computer simulations. An important formalism is the DEVS model — a mathematical representation of the class of discrete event systems. Other formalisms, such as modelling strategies, provide a “world view” in which to conceptualize the simulation model.

In a typical modelling situation, we deal with systems, for which only partial data are available to construct a system model. We often restrict our attention to a subclass of all possible models, constrained, for example, by the necessity to cut down the search space to be explored.

It appears to be the rule rather than the exception that usefully detailed stochastic models are sufficiently complex so that it is extremely difficult or impossible to obtain an exact analytic solution. Simulation is essentially a controlled statistical sampling technique that can be used to study complex stochastic systems when analytic techniques do not suffice. This book concentrates ondiscrete event digital simulationin which the behavior of a specified stochastic system is observed by sampling on a digital computer system and stochastic state transitions occur only at a set of increasing (random) time points.

In this paper, we pursue the Analogy between classical linear System Theory and a new "linear" Theory for Discrete-Event Dynamic Systems which has been introduced for the first time in [3] and which is based on the algebra of "dioids". We first define the particular class of timed Petri nets that can be described by "linear" recurrent equations and then develop concepts such as transfer matrix representations of such systems, stability, observability, controllability, feed-back stabilization, realization of transfer matrices etc...

ESM/RTL is a framework for modelling, specifying and verifying real-time discrete event systems. Extended state machines (ESMs) are used to model the processes of the plant and the controller, and real-time temporal logic (RTL) is used as the assertion language for specifying required plant behaviour and verifying that the controller achieves the specification. A review of the framework is presented. The paper concludes with a brief discussion of current research to automate and modularize the framework.

A simulation language provides an organizational structure to build models that simulate the dynamic performance of systems on a digital computer. The organizational structure allows the variables that define system performance to be described by equations and logical conditions. System descriptions written in terms of mathematical equations are referred to as continuous models. System descriptions written in terms of entity flow or the logical conditions that cause state changes are referred to as discrete models. A simulation language supports the building of continuous or discrete models and, in some languages, combined continuous discrete models.The organizational structure of a simulation language specifies where and how system equations are written, the procedures for modeling the flow of entities through a process, and the method for defining the logical conditions that affect system variables. Within the defined organizational structure, the time advancement function required to study the dynamics of systems performance is formalized. Furthermore, specific user-written models to obtain system performance updates and system performance changes are identified.The two main aspects of a simulation language are the method for specifying system status and the procedure for advancing time to update system status. In continuous and discrete simulation models, the system variable description and the time advance procedures are different. In continuous models, a system description is in terms of state variables as modeled by equations. Events occur when state variables cross thresholds. State variable updating is obtained by evaluating the system equations in a step-evaluate-step fashion.In contrast to this, discrete models including networks describe the status of the system in terms of the number of entities residing in the system and the values of attributes associated with entities. Changes to the status of the system variables only occur with the addition or deletion of entities or when attribute values are recomputed. In discrete simulation, such changes can only occur at event times.To combine continuous and discrete models, the concept of time advance, status changes and event processing must be integrated. To do this a conceptual change was required which is reflected in the redefinition of an event “as a point in time beyond which the status of a system cannot be projected with certainty.” (11,12). This definition allows state variables to change continuously without an event occurring as long as the equations defining the state variables do not change. At the same time, it allows events that cause discrete jumps in continuous variables to be included in the model. It also allows events to occur where a decision is made not to change the status of the system.For combined simulation models, it is useful to describe events in terms of the mechanism by which they occur. Those that occur at specified projected points in time are referred to as time-events. They are commonly thought of in conjunction with process or discrete event simulation. As previously discussed, those that occur when a system variable reaches a particular threshold are called state-events. Unlike time-events, they are not scheduled to occur in the future but occur when state variables are found to satisfy prescribed conditions.In a combined simulation model, the behavior is determined by calculating the values of the state variables at the end of steps and making the changes to the values of attributes or to the number of entities in existence at event times. The step size is determined by the executive function so that events can only occur at the end of a step. The executive also considers accuracy requirements, minimum and maximum user prescribed step size values, and output reporting requirements when determining the appropriate size for the next step.At the end of each time step, the state variables are evaluated to determine if the conditions prescribing a state-event have occurred. If a state-event was passed, that is, a state variable crossed a threshold by more than an allowed tolerance, the step size was too large and is reduced. If a state-event occurs, the model status needs to be updated according to the event logic. As stated above, the executive function sets the step size so that no time-event will occur within a step. This is accomplished by adjusting the size of the step so that the end of the step occurs at the time-event instant.Time-events are scheduled happenings and are placed on the event calendar. The event calendar maintains events in chronological order based on the time the event is to occur. Two attributes of a time-event are its time of occurrence and its event type. In addition, if the time-event is for an entity, the attributes of that entity must be associated with the time-event. When a time-event occurs, it can change system status in four ways: (1) by altering the value of state variables, (2) by changing the values of attributes of current entities in the system, (3) by altering relationships that exist among entities or state variables, and (4) by changing the number of entities present. A combined simulation language provides methods for accomplishing each type of change when an event occurs.In this panel, a discussion of the concepts of combined simulation and the trend of research on combined simulation will be discussed. Joining me on the panel are Professor Francois E. Cellier of the University of Arizona and Professor Donald G. Golden of Cleveland State University. The types of questions that will be discussed by the panel are listed below: Should one look at combined modeling as discrete perturbations to continuous processes or as entities of discrete simulations having some attributes that vary continuously?Is the educational background of an individual the main determinant of his modeling approach?What problems are best suited to a combined approach? To a discrete approach? To a continuous approach?Describe some of the applied models that have been developed using a combined approach.How were problems/systems modeled before combined languages were introduced?Should problems be classified according to an appropriate modeling and analysis method?

In this chapter, our goal is to introduce a way in which discrete time processes may be embedded in continuous time systems without altering the phase space. To do this, we adopt a strictly probabilistic point of view, not embedding the deterministic system S: X → X in a continuous time process, but rather embedding its Frobenius-Perron operator P:L 1 (X) →L 1 (X) that acts on L 1 functions. The result of this embedding is an abstract form of the Boltzmann equation. This chapter requires some elementary definitions from probability theory and a knowledge of Poisson processes, which are introduced following the preliminary remarks of the next section.

All of the previous chapters have considered the development and use of state models for dynamic systems described in terms of differential equations. A number of case study examples have been presented which illustrate the general procedures. In this chapter several models are developed which illustrate the fact that, in certain cases, allowances for changes in the state of a system need be made only at discrete instants in time and that the state itself, as well as the input and output variables, may make discrete changes in their values at these times.

This note provides a simple explanation of the ideas behind perturbation analysis. Perturbation Analysis (PA) is a technique for the computation of the gradient of performance measure (PM) of a discrete event dynamic system with respect to its parameters (e) using only one sample path or Monte Carlo experiment of the system. When first presented, one's immediate reaction has often been incredulity stemming from the belief that "one cannot get something for nothing". Later this disbelief may be developed into a more sophisticated and technical objection involving the legitimacy of interchanging differentiation and expectation operators or the probabilistic convergence of the PA estimate to its true value (more about these later). In nontechnical terms, these translate to "How can you squeeze out information about a trajectory / sample-path operating under one value of the system parameter from that of another operating under a different value? Don't the two trajectories behave entirely dissimilarly?" We shall offer below a simple explanation. This explanation covers the essence of PA in the simplest terms stripped of all of its computational trappings, efficiency tricks, etc. Once the basic ideas are made clear, we leave the question of "how efficient" to other papers and potential implementors. For similar tutorial reasons, the example used below is not at all the most general case for which PA can be applied. The purpose here is to convey the fundamental idea behind this approach in terms accessible to the largest audience. Interested readers are referred to other PA papers which at this point total over 40 (see [7],[8]).

Bufferized production lines can be viewed as discrete event dynamical systems, whose states evolve according to the occurrence of distinct expected or random events. This approach allows the definition of a dynamical aggregate model in terms of nonlinear differential equations, which reveals to be a powerful analytic tool to evaluate production line efficiency v.s. a sufficient set of design parameters.

This chapter reviews discrete event simulation models. Discrete event simulation models are used to study performance characteristics of simple waiting line systems and of more complex queuing systems. All discrete event simulation models describe the way by which customers or entities flow through a system over time. A basic premise that applies to such models is that all changes in the state of a system are instantaneous changes at specific points in time. Such changes are discrete as opposed to continuous, and the occasion of such a change can be termed as an event, thereby, explaining the term discrete event simulation. The two main advantages of adopting a discrete event philosophy when a complex system is to be modeled, studied, and analyzed are (1) that all discrete event models can be synthesized from a set of basic building blocks or components and (2) that computer languages are available to allow the analyst to put together simulation models based on these building blocks. Several different special purpose computer simulation languages such as GPSS or SIMSCRIPT are available. Such languages are particularly useful to describe certain classes of simulation problems. However, they lack the versatility of general purpose languages such as FORTRAN.

The simulation of events in discrete systems for conflicting situations (i.e. race conditions, parallel processes, active feedback loops) is discussed. After a brief survey of the origins of such instances the quasideterministic state description method and the concept of the duality of discrete events are introduced as means for solving the above problems. The categorization of undetermined situations into two subclasses, i.e. Indeterminacies of First and Indeterminacies of Second Order, takes care of the state representation in “level type” events, and systems characterized by the movement of entities can be transformed into such because of their duality.

By way of the solution to a long standing problem in production lines, we illustrate how to apply a well known control theoretic technique to discrete event dynamical systems.

In our discussions of Newton’s method we demonstrated how an apparently innocent system of differential equations gives rise to unimaginably rich and complex behaviour after discretization. This is also the Leitmotiv of our last example, the Volterra-Lotka equations for a predator-prey system.

We present a summary of some of the known results on the complexity of supervisory control of discrete event systems in the framework of [RW1]. In addition some recent results on the controllability of sequential behaviors and on the complexity of basic coordination problems are presented.

A finite state automaton is adopted as a model for Discrete Event Dynamic Systems (DEDS). Observations are assumed to be a subset of the event alphabet. Observability is defined as having perfect knowledge of the current state at points in time seperated by bounded numbers of transitions. A polynomial test for observability is given. It is shown that an observer may be constructed and implemented in polynomial time and space. A bound on the cardinality of the observer state space is also presented. A notion of resiliency is defined for observers, and a test for resilient observability and a procedure for the construction of a resilient observer are presented.

The paper deals with the analysis of discrete event dynamic systems (DEDS) using so-called nonhomogeneous elements for the representation of system attributes and their behaviour, Definitions of fundamental notions (nonhomogeneous vector, matrix) are given and algebraic structures are i ntroduced on the seta of nonhomogeneous elements by means of proper binary relations. Also a special concatenation-like "dissociative" operation is defined which allows to establish "superstructures' on the sets of nonhomogeneous elements containing dissociatively binded terms and having the semigroup structural properties. Further a definition of vector transformation as well as that of multitransformation enable to generate new vectors and new binded terms. An example of manufacturing process modelling is included to illustrate that the nonhomogeneous elements are well suited for the description of DEDS, and lend themselves particularly well to monitoring and control in complex man -machine systems.

The general design of discrete-time systems is carried out with the same principles as for continuous systems, by the introduction of compensation to give improved transient response or some other performance characteristic; methods are discussed in Gupta and Hasdorff (1970). The present chapter illustrates the application of state-variable analysis to the investigation and design of the particular case of minimum -time-response and ripple-free systems. The properties of these systems arise essentially because of the discrete nature of the system, and their characteristics are closely related to many state-variable concepts but, in addition, the design provides a close link with z-plane analysis.

In many systems the functional relationship between an adjustable parameter and a resulting performance measure is either unknown or too complex. An example of such a situation is a queuing network with finite queue capacities for which system the functional relationship between the service rate at a node and the resulting throughput is typically unknown.

In this paper, following ideas recently developed for a class of continuous systems, we introduce the notion of zero dynamics and minimum phase for discrete time nonlinear systems. On this basis, sufficient conditions are given for state feedback stabilization and full linearization via dynamic compensation. Relations with other properties of the system are also investigated.

So far, the Calculus of Variations and Maximum Principle have been analysed in forms of differential equation system where changes are continuous or treated as continuous over time. In the real world, however, many observations are made and recorded only at discrete intervals, for example gross national product is measured only once a year, imports and exports figures are reported only quarterly. A discrete counterpart of the continuous Variational problems and Maximum Principle must be developed. This will be done in this chapter.

The interaction of quantal EPSPs and IPSPs at the membrane of the neuron is similar to the birth and death process in probability theory. Thus the membrane potential can occupy only discrete levels increasing by one unit with the arrival of an excitatory impulse and decreasing by one unit with the arrival of an inhibitory impulse. When the potential reaches a level N corresponding to the threshold of firing, the neuron fires and the membrane potential returns to the rest level immediately. The analogy of course is not perfect because the IPSP can take the membrane potential below the rest level. Nevertheless, the theory of birth and death processes can be suitably modified to take this into account. For this reason, in Section 8.1 basic results from the theory of such processes are presented, following Srinivasan and Mehata (1976). Birth and death processes have been studied over many decades and the literature is vast. This section merely introduces the reader to the study of such processes in relation to neuron modelling. It is important to note here that many discrete state models in the literature go far beyond this; in fact it is difficult to identify some of them as birth and death processes. In Sections 8.2 to 8.4 the different types of discrete state models are discussed in detail.

We give a rigorous extension of the perturbation analysis approach to more general Discrete Event Dynamic Systems (DEDS). For a fairly general class of DEDS, and for certain parameters and performance measures of such DEDS, an infinitesimal perturbation analysis algorithm is stated. It is then proved that this algorithm gives exact values for the gradients of performance w.r.t. the parameters, by observing only one sample-path of the DEDS. This enables very efficient calculation of these gradients: a fact that can be used for design/operation of manufacturing systems, communication networks, and many other real-world systems.

In this paper a discrete event system is a dynamical system in which the term event is used to describe the occurrence of a discontinuous change in the elements of the system at a point in time. Events occur at discrete intervals of time, which are not necessarily uniformly separated, and logical relationships govern the discontinuous changes when events occur. The state space is restricted to being discrete and finite.

The purpose of this paper is to give a discrete-time analogue of the notion of controlled invariance under quasi-static state feedback and to show that it is possible to present a geometric solution of the dynamic disturbance decoupling problem in terms of this new notion.

An algorithm is presented to calculate the validity range of deterministic similarity of a sample path of a discrete event dynamic system when a single perturbation is introduced at the operation times. Based on the calculated range, sensitivity analysis concerning both the gradient of the throughput and some special technological feasibility of an operation schedule can be analysed. The algorithm is recommended in a manufacturing environment, when technology intensive products are produced in small lots. The implementation of the algorithm in an automated steel manufacturing process is also presented.

Petri nets provide a compact and graphical way to model large and complex discrete event systems (DES). For such systems, the state-space explosion is problematic. Fluid stochastic event graphs are decision free Petri nets, which can represent systems with failures. This paper presents an estimation algorithm for state space estimation and optimization of failure-prone DES.

The role played by a discrete-time state-feedback controller in assigning a specified discrete-time eigenvalue stnicture is approached exclusively in terms of plant trajectories. The knowledge of the directional behavior of the plant is based on general, qualitative properties (revealed by a physical insight into the operating conditions) and concrete, quantitative aspects (captured, by experimentation, in non-recursive models). Controller design (including the output regulation case) results directly by complementing the qualitative information with the quantitative one, circumventing the need for parameter estimation, as a distinct and indispensable stage, preceding the design procedure in classical scenarios.

We consider discrete event systems (DES) involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. When tasks are processed over a single stage, it has been shown that there are structural properties of the optimal sample path that lead to very efficient solutions of such problems. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, these properties no longer hold and no obvious extensions are known. We consider a two-stage problem with homogeneous cost functions over all tasks at each stage and derive several new optimality properties. These properties lead to the idea of introducing "virtual" deadlines at the first stage, thus partially decoupling the stages so that the known efficient solutions for single-stage problems can be used. We prove that the solution obtained by an iterative virtual deadline algorithm (VDA) converges to the global optimal solution of the two-stage problem and illustrate the efficiency of the VDA through numerical examples.

We consider linear discrete time systems with exogenous unknown disturbances where the available information is that the state and the disturbance are allowed to belong, at each time, to a given convex polyhedral set. The problem addressed is that of checking if it is possible to maintain the state evolution in a prescribed set, despite the disturbances. If it is the case, a robust control law is described.

Control of hybrid systems is an area that is currently attended by world control communities. One of the main stages in control of hybrid systems is the recognition of the operating modes and the discrete events in the system. In this paper a method for identifying the operating modes and events is introduced in threshold event driven hybrid systems. The method is constructed based on fuzzy Petri net and the concepts of fuzzy ordering relation. Then the proposed method is used for control of an illustrative hybrid system example. The simulation results show that the proposed approach satisfies the expected demands.

To model qualitative aspects of discrete event systems, i.e., the order of the events is of sole importance, we use a triple consisting of the set of all possible events (the alphabet), the set of all behavior (possible strings of events), and the set of all tasks (completed behavior). We use this view to model synchronous as well as asynchronous connection of systems. Moreover, it is easy to define notions like deadlock and livelock in this view. We give a method to construct a second system that, in connection with the original system, gets rid of its deadlock and/or liveloek. A state-space representation is introduced. In this representation computations can be done effectively.

International audience; This paper deals with the problem of fault diagnosis of complex discrete event systems in the context of communicating timed automata. Indeed, for the diagnosis, this kind of systems can be represented by timed models whose components communicate through channels. This paper starts with a description of our modelling methodology of discrete event systems as communicating timed automata. The proposed approach for diagnosis (detection and isolation) is based on the methodology known as the diagnoser approach. This paper extends the approach of diagnoser through the taking into account of the various communicating synchronized automata representing the components of the system. It proposes an automatic step of construction of the global model. The application of the proposed algorithm allows to obtain the diagnoser of the studied system. Starting from a model of the complex system, this approach computes a deterministic automaton, called a diagnoser, which uses observable events to detect the occurrence of a failure. The different steps of the proposed method are described by algorithms and illustrated through a batch process.

Models of discrete event systems combine ideas from control theory and computer science to represent the evolution of distributed processes. We formalize a notion of the invalidation of models presumed to describe dynamics on networks, and introduce an algorithm to evaluate a class of event-driven processes that evolve close to an invariant and stable state. The algorithm returns the value true, if according to the proposed notion of invalidation, the evolution of empirical observations is inconsistent with the stability properties of the model. To illustrate the approach, we represent a generic decision-making process in which the marginal utility of allocating agents to particular nodes rests on the well-known concept in economy theory of the law of diminishing returns.

This paper presents a method to identify discrete event systems (DES) using interpreted Petri nets (IPN). The approach herein proposed works online with the system and has two main steps. In the first step, the algorithm advances finding out new places, transitions and arcs, all of them are obtained using input-output information. In the second step, the algorithm goes back over the last output sequence computing constraints and no observable places. The algorithm is an infinity loop and is always reading and processing DES information. Properties like observability and identifiability will be addressed.

Control, fault monitoring, and diagnosis are critical tasks in managing discrete event systems such as real-world factory automation systems. We have applied a model-based technology based on temporal causal networks to the integrated modeling, diagnosis and reconfiguration of discrete event systems. Temporal causal networks use a propositional temporal logic with quantification over discrete time, in which the temporal sentences are constrained by the topology of the system structure that depicts the causal relations between system variables. This paper specifies for temporal causal networks some formal notions of control properties, such as observability and controllability, and the algorithmic approaches for computing these properties.

Timed event graphs are described in dioids by a linear state-space or transfer function model. This paper proposes a state feedback control under complete control and observation of the states. By using a model reference control approach, the closed-loop transfer function matches the control specification expressed as a given transfer function. It is shown that under certain conditions an optimal controller exists, although two sub-optimal controllers can always be obtained.

We have shown that a trace theory based approach leads to an elegant definition of a logical discrete event system and gives a nice algorithm to find a solution for a control problem, where we, temporally, go beyond the scope of a DES. The algorithm can be translated to work on state graphs, leading to an effectively computable solution if the systems itself are regular. Proofs of all properties can be found in Smedinga [Sme92].

This paper deals with regulation control of discrete event systems using estimated state feedback. The system, the observer and the controller are modeled with interpreted Petri nets (IPN). The case in which both the state and the input events are partially observed is addressed. Based on this framework, structural conditions to determine the controllability of the system using an estimated state feedback are derived. Finally a scheme that integrates the controller and the observer is proposed.

This paper deals with the control of a class of perfectly modelled linear hybrid systems which consist of two, in general coupled, subsystems one being continuous -time while the second one is digital. Both subsystems are driven by continuous time and sampled values of a control input. The description of the overall system is given through an extended hybrid system , which is purely discrete at sampling instants, which has two , in general, coupled continuous-time and discrete - time substates. The discrete -time substate is jointly defined by the digital substate and the samples of the continuous substate while being driven by the sampled input. The control objective has a double nature and it consists of the achievement of separate continuous-time and discrete-time model- matching objectives with respect to two predefined stable reference models . It is achieved by synthesizing a dynamic hybrid controller consisting of a continuous subcontroller and a discrete one. Each of those controllers has its own control objective.

We propose a method that combines simulation and numerical techniques and directly integrated using interval arithmetic techniques for the analysis of large discrete event systems. A system is first divided into several layers. Identifying subsystems that can be modeled in isolation solves a system for each layer. In each subsystem, the Markovian assumption allows us to establish a set of linear equality constraints among the expectation of state variables in the Petri nets, such as token numbers in the places. A pseudo random process is responsible for the timing of the model, event times are completely determined by simulation. Thus, linear equality constraints are computed according to the pre-simulated event times, and it is possible to know the probabilities of interactions between subsystems.

The sample path constructability problem for discrete event systems (DES) involves the observation of a sample path under a particular parameter value /spl theta/ of the system with the requirement to concurrently construct multiple sample paths of the DES under different values using only information available along the given sample path. This allows the on-line estimation of performance measures of the form J(/spl theta/), not available in closed form, over a range of values of /spl theta/. We present a sample path coupling approach that solves the problem without imposing any restrictions on the event processes in the system. A specific "time warping" algorithm is described and its performance is analysed in terms of computational cost. We also identify a structural condition on DES, termed regularity: in regular DES the occurrence of any event can never trigger more than one additional event at the next state. We have found that for DES with this property (satisfied by a wide range of systems) concurrent sample path construction techniques are computationally efficient.