Full-state perturbation analysis of discrete event dynamic systems

Discrete event dynamic systems are studied within the framework of perturbation analysis in this paper. Perturbation is extended from the event times only to both event times and queue lengths. An approximate technique, full-state perturbation analysis (PA), is developed as an extension of the PA approach. Full-state PA is able to deal with problems involving queue length perturbations which often defy existing PA methods, while it still retains all the advantages of existing PA. Full-state PA is used to calculate the throughput sensitivity to the number of customers in closed queueing networks and the throughput sensitivity to routing change. Numerical examples are given. Experimental results verify the validity and accuracy.This work is supported in part by the National High Technology Project and by Southeast University Research Funds for Young Teachers.     

Performance evaluation and perturbation analysis of discrete event dynamic systems

This is a conceptual and speculative paper concerning the future development of system and control theory in operational and discrete event systems with particular emphasis to the techniques of perturbation analysis.     

An event domain formalism for sample path perturbation analysis of discrete event dynamic systems

We present a state-space representation of a general discrete event dynamic system (DEDS) model on the basis of a natural event domain, which replaces time. Perturbation analysis of a sample path Of a DEDS is then formalized using some fundamental concepts introduced to establish conditions for its validity. A set of simple perturbation equations is then derived under these conditions, so that performance gradients with respect to parameters are estimated from observation of real or simulated data on a single sample path.     

Using infinitesimal perturbation analysis of stochastic flow models to recover performance sensitivity estimates of discrete event systems

Stochastic Flow Models (SFMs) form a class of hybrid systems used as abstractions of complex Discrete Event Systems (DES) for the purpose of deriving performance sensitivity estimates through Infinitesimal Perturbation Analysis (IPA) techniques when these cannot be applied to the original DES. In this paper, we establish explicit connections between gradient estimators obtained through a SFM and those obtained in the underlying DES, thus providing analytical evidence for the effectiveness of these estimators which has so far been limited to empirical observations. We consider DES for which analytical expressions of IPA (or finite difference) estimators are available, specifically G/G/1 and G/G/1/K queueing systems. In the case of the G/G/1 system, we show that, when evaluated on the same sample path of the underlying DES, the IPA gradient estimators of states, event times, and various performance metrics derived through SFMs are, under certain conditions, the same as those of the associated DES or their expected values are asymptotically the same under large traffic rates. For G/G/1/K systems without and with feedback, we show that SFM-based derivative estimates capture basic properties of finite difference estimates evaluated on a sample path of the underlying DES.     

判定非确定离散事件系统稳定性的梯度搜索算法

讨论基于非确定自动机/形式语言模型的非确定离散事件系统(NDES)稳定性问题.引入非确定离散事件系统稳定性的定义,并得到了稳定性的判据定理.给出了基于梯度的搜索算法,该算法可有效消除观测器的冗余,从而降低了计算复杂度.     

离散事件系统N步稳定性分析

讨论基于自动机/形式语言模型的离散事件系统(DES)稳定性问题,引入了确定性离散事件系统N步稳定性定义,并得到了稳定性的判据定理,推导了具体的算法实现。该算法具有多项式复杂度。     

Smoothed perturbation analysis for a class of discrete-eventsystems

A gradient-estimation procedure for a general class of stochastic discrete-event systems is developed. In contrast to most previous work, the authors focus on performance measures whose realizations are inherently discontinuous (in fact, piecewise constant) functions of the parameter of differentiation. Two broad classes of finite-horizon discontinuous performance measures arising naturally in applications are considered. Because of their discontinuity, these important classes of performance measures are not susceptible to infinitesimal perturbation analysis (IPA). Instead, the authors apply smoothed perturbation analysis, formalizing it and generalizing it in the process. Smoothed perturbation analysis uses conditional expectations to smooth jumps. The resulting gradient estimator involves two factors: the conditional rate at which jumps occur, and the expected effect of a jump. Among the types of performance measures to which the methods can be applied are transient state probabilities, finite-horizon throughputs, distributions on arrival, and expected terminal cost     

Numeration and discrete dynamical systems

This survey aims at giving both a dynamical and computer arithmetic-oriented presentation of several classical numeration systems, by focusing on the discrete dynamical systems that underly them: this provides simple algorithmic generation processes, information on the statistics of digits, on the mean behavior, and also on periodic expansions (whose study is motivated, among other things, by finite machine simulations). We consider numeration systems in a broad sense, that is, representation systems of numbers that also include continued fraction expansions. These numeration systems might be positional or not, provide unique expansions or be redundant. Special attention will be payed to β-numeration (one expands a positive real number with respect to the base β > 1), to continued fractions, and to their Lyapounov exponents. In particular, we will compare both representation systems with respect to the number of significant digits required to go from one type of expansion to the other one, through the discussion of extensions of Lochs’ theorem.     

On fuzzifications of discrete dynamical systems

Let X denote a locally compact metric space and φ : X → X be a continuous map. In the 1970s Zadeh presented an extension principle helping us to fuzzify the dynamical system (X, φ), i.e., to obtain a map Φ for the space of fuzzy sets on X. We extend an idea mentioned in [P. Diamond, A. Pokrovskii, Chaos, entropy and a generalized extension principle, Fuzzy Sets Syst. 61 (1994) 277-283] to generalize Zadeh’s original extension principle.In this paper we study basic properties of so-called g-fuzzifications, such as their continuity properties. We also show that, for any g-fuzzification: (i) a uniformly convergent sequence of uniformly continuous maps on X induces a uniformly convergent sequence of fuzzifications on the space of fuzzy sets and (ii) a conjugacy (resp., a semi-conjugacy) between two discrete dynamical systems can be extended to a conjugacy (resp., a semi-conjugacy) between fuzzified dynamical systems.Throughout this paper we consider different topological structures in the space of fuzzy sets, namely, the sendograph, endograph and levelwise topologies.     

Detectability of networked discrete event systems

Detectability of discrete event systems, defined as the ability to determine the current and subsequent states, is very important in diagnosis, control, and many other applications. So far only detectability of non-networked discrete event systems has been defined and investigated. Non-networked discrete event systems assume that all the communications are reliable and instantaneous without any delays or losses. This assumption is often violated in networked systems. In this paper, we study detectability for networked discrete event systems. We investigate the impact of communication delays and losses on detectability. We define two classes of detectabilities: network detectability for determining the state of a networked discrete event systems and network D-detectability for distinguishing certain pairs of states of the systems. Necessary and sufficient conditions for network detectability and network D-detectability are derived. Methods to check network detectability and network D-detectability are also developed. Examples are given to illustrate the results.     

Diagnosability of fair discrete event systems

Failure diagnosability has been widely studied using discrete event system (DES) models. It is, however, shown in this work by means of a counterexample that the diagnosability condition, which has been shown to be necessary and sufficient in the DES context, fails to hold for many real‐world hybrid systems. This is because the abstraction employed in formulating the DES models obliterates the continuous dynamics. In the present work, a new failure diagnosability mechanism has been developed for discrete time hybrid system (DTHS) models to alleviate this problem. A new diagnosability condition is proposed and its necessity and sufficiency with respect to the diagnosability definition are established formally. Finally, the method of A‐diagnosability, which can also be used to circumvent this problem and which needs additional probabilistic information for diagnosability analysis, has been shown to have a higher computational complexity than the DTHS model based method proposed in this paper. Further, it is also highlighted that the DTHS model based diagnosability analysis technique is capable of diagnosing faults that degrade the temporal performance of the system, which cannot be handled by the A‐diagnosability analysis mechanism. Copyright © 2008 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

The predictability of discrete event systems

Perturbation analysis and the automaton and language model are approaches developed recently for the study of discrete-event systems (DESs). The prediction of a trajectory of a new system is the essential idea of perturbation analysis. The automaton theory models a trajectory of a DES by a string in a particular language. The author formulates the trajectory prediction as a projection of a string onto a language. A sufficient condition is found for one language to be predictable from another language. Examples are given to show the application of this concept     

Diagnosability of fuzzy discrete event systems

In this paper, discrete event systems (DESs) are reformulated as fuzzy discrete event systems (FDESs) and fuzzy discrete event dynamical systems (FDEDSs). These frameworks include fuzzy states, events and IF-THEN rules. In these frameworks, all events occur at the same time with different membership degrees. Fuzzy states and events have been introduced to describe uncertainties that occur often in practical problems, such as fault diagnosis applications. To measure a diagnoser’s fault discrimination ability, a fuzzy diagnosability degree is proposed. If the diagnosability of the degree of the system yields one a diagnoser can be implemented to identify all possible fault types related to a system. For any degree less than one, researchers should not devote their time to distinguish all possible fault types correctly. Thus, two different diagnosability definitions FDEDS and FDES are introduced. Due to the specialized fuzzy rule-base embedded in the FDEDS, it is capable of representing a class of non-linear dynamic system. Computationally speaking, the framework of diagnosability of the FDEDS is structurally similar to the framework of diagnosability of a non-linear system. The crisp DES diagnosability has been turned into the term fuzzy diagnosability for the FDES. The newly proposed diagnosability definition allows us to define a degree of diagnosability in a class of non-linear systems. In addition, a simple fuzzy diagnosability checking method is introduced and some numerical examples are provided to illustrate this theoretical development. Finally, the potential applications of the proposed method are discussed.     

集值离散动力系统的扩张性*

设(X,d)为紧致度量空间,f∶X→X连续,(k(X),dH)是X所有非空紧致子集构成的紧致度量空间,f∶k(X)→k(X),f(A)={f(a)|a∈A}。运用分析的方法初步给出了集值离散动力系统中的扩张性理论。提出集值映射的全扩张、强全扩张的概念,并研究了f的扩张性与f的扩张性之间的关系。所得结果扩展了集值离散动力系统的研究范围,并提出了该领域未来可研究的方向。     

Observability of discrete event dynamic systems

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 separated 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     

Periodic orbits on discrete dynamical systems

In this paper, we discuss the discrete dynamical system x_n+1 = βx_n − g(x_n), n = 0, 1, …, arising as a discrete-time network of single neuron, where β is the internal decay rate, g, is a signal function. First, we consider the case where g is of McCulloch-Pitts nonlinearity. Periodic orbits are discussed according to different range of β. Moreover, we can construct periodic orbits. Then, we consider the case where g is a sigmoid function. Sufficient conditions are obtained for (1) has periodic orbits of arbitrary periods and an example is also given to illustrate the theorem.     

Modeling discrete event scalable network systems

Scalability in simulation tools is one of the most important traits to measure performance of software. The reason is that today’s Internet is the main instance of a large-scale and highly complex system. Simulation of Internet-scale network systems has to be supported by any simulation tool. Despite this fact, many network simulators lacks support for building large models. In this work, in order to propose a new approach for scalability issue in network simulation tools, a network simulator is developed based on behavior of honeybees and high performance DEVS, modular and hierarchical system theoretic approach. A biologically-inspired discrete event modeling approach is described for studying networks’ scalability and performance traits. Since natural systems can offer important concepts for modeling network systems, key adaptive and emergent attributes of honeybees and their societal properties are incorporated into a set of simulation models that are developed using the discrete event system specification approach. Large-scale network models are simulated and evaluated to show the benefits of nature-inspired network models.     

Detectability in stochastic discrete event systems

A discrete event system possesses the property of detectability if it allows an observer to perfectly estimate the current state of the system after a finite number of observed symbols, i.e., detectability captures the ability of an observer to eventually perfectly estimate the system state. In this paper we analyze detectability in stochastic discrete event systems (SDES) that can be modeled as probabilistic finite automata. More specifically, we define the notion of A-detectability, which characterizes our ability to estimate the current state of a given SDES with increasing certainty as we observe more output symbols. The notion of A-detectability is differentiated from previous notions for detectability in SDES because it takes into account the probability of problematic observation sequences (that do not allow us to perfectly deduce the system state), whereas previous notions for detectability in SDES considered each observation sequence that can be generated by the underlying system. We discuss observer-based techniques that can be used to verify A-detectability, and provide associated necessary and sufficient conditions. We also prove that A-detectability is a PSPACE-hard problem.     

A non-trivial relation between some many-dimensional chaotic discrete dynamical systems and some one-dimensional chaotic discrete dynamical systems

Chaotic maps are very useful in practical applications. In this paper, we present a method for constructing the many-dimensional chaotic discrete dynamical systems using semiconjugacy property. The chaotic property in one dimension may be influenced the chaotic property in higher-dimensions. In fact, using the one-dimensional chaotic maps and semiconjugacy property, we construct some many-dimensional chaotic discrete dynamical systems. These systems may be used as random number generators in Monte Carlo simulations. Also, these systems may be used in practical applications such as chaotic cryptography and evolutionary algorithms.     

A new approach to the analysis of discrete event dynamic systems

We present a new, time domain approach to the study of discrete event dynamical systems (DEDS), typified by queueing networks and production systems. A general state-space representation is developed and perturbation analysis is carried out. Observation of a single sample realization of such a system can be used to predict behavior over other sample realizations, when some parameter is perturbed, without having to make additional observations. Conditions under which this is always possible are investigated and explicit results for some special cases are included.