Show simple item record

dc.contributor.authorRu, Y.en
dc.contributor.authorHadjicostis, Christoforos N.en
dc.creatorRu, Y.en
dc.creatorHadjicostis, Christoforos N.en
dc.description.abstractIn this paper, we consider state estimation in discrete-event systems (DESs) modeled by labeled Petri nets and present upper bounds on the number of system states (or markings) that are consistent with an observed sequence of labels. Our analysis is applicable to Petri nets that may have nondeterministic transitions (i.e., transitions that share the same label) and/or unobservable transitions (i.e., transitions that are associated with the null label). More specifically, given knowledge of a labeled Petri net structure and its initial state, we show that the number of consistent markings in a Petri net with nondeterministic transitions is at most polynomial in the length of the observation sequence (i.e., polynomial in the number of labels observed). This polynomial dependency of the number of consistent markings on the length of the observation sequence also applies to Petri nets with unobservable transitions under the assumption that their unobservable subnets are structurally bounded. The bounds on the number of markings established in this paper imply that the state estimation problem in labeled Petri nets can be solved with complexity that is polynomial in the length of the observation sequence. Note to Practitioners-A variety of systems, such as manufacturing systems, computer networks, traffic systems, and others, can be modeled as DESs at a higher level of abstraction. These models can then be used for the purpose of state estimation, supervisory control, and fault diagnosis. Knowledge of the system state is always critical for controller design and fault diagnosis. In this paper, we study state estimation in DESs modeled by labeled Petri nets. This is a challenging problem because two different types of uncertainty can arise due to sensor limitations: a) occurrences of different activity (different transitions) may generate the same observation; b) occurrences of unobservable activity (silent transitions) go unrecorded.We show that, under some reasonable assumptions on the nature of the given Petri net's unobservable transition structure, the number of possible system states that are consistent with an observed sequence of events is upper bounded by a function polynomial in the length of the observation sequence. The implications are twofold: a) the state estimation problem can be solved in a very general setting with complexity that is polynomial in the length of the observation sequence and b) the polynomial bound can guide the design of systems, especially when configuring the state transition sensors, to reduce the uncertainty introduced in the state estimation stage. © 2006 IEEE.en
dc.sourceIEEE Transactions on Automation Science and Engineeringen
dc.subjectUpper boundsen
dc.subjectComputer networksen
dc.subjectPetri netsen
dc.subjectGraph theoryen
dc.subjectMarine biologyen
dc.subjectState estimationen
dc.subjectInitial stateen
dc.subjectFault diagnosisen
dc.subjectPolynomial approximationen
dc.subjectController designsen
dc.subjectManufacturing systemsen
dc.subjectDiscrete-event systems (dess)en
dc.subjectEstimation problemsen
dc.subjectLevel of abstractionsen
dc.subjectPolynomial boundsen
dc.subjectSensor limitationsen
dc.subjectSequence of eventsen
dc.subjectState transitionsen
dc.subjectStructural designen
dc.subjectSupervisory controlsen
dc.subjectSystem stateen
dc.subjectTraffic systemsen
dc.subjectTransition structuresen
dc.titleBounds on the number of markings consistent with label observations in petri netsen
dc.description.endingpage344Πολυτεχνική Σχολή / Faculty of EngineeringΤμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών / Department of Electrical and Computer Engineering
dc.source.abbreviationIEEE Trans.Autom.Sci.Eng.en
dc.contributor.orcidHadjicostis, Christoforos N. [0000-0002-1706-708X]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record