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.date.accessioned2019-04-08T07:48:12Z
dc.date.available2019-04-08T07:48:12Z
dc.date.issued2009
dc.identifier.urihttp://gnosis.library.ucy.ac.cy/handle/7/44815
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.source.urihttps://www.scopus.com/inward/record.uri?eid=2-s2.0-64049111568&doi=10.1109%2fTASE.2008.2009095&partnerID=40&md5=08e85228e5c0164450ea1498608ab3ac
dc.subjectEstimationen
dc.subjectUpper boundsen
dc.subjectComputer networksen
dc.subjectSensorsen
dc.subjectPetri netsen
dc.subjectGraph theoryen
dc.subjectMarine biologyen
dc.subjectUnobservableen
dc.subjectState estimationen
dc.subjectInitial stateen
dc.subjectFault diagnosisen
dc.subjectPolynomial approximationen
dc.subjectLabelsen
dc.subjectPetri-neten
dc.subjectController designsen
dc.subjectManufacturing systemsen
dc.subjectSub-netsen
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.typeinfo:eu-repo/semantics/article
dc.identifier.doi10.1109/TASE.2008.2009095
dc.description.volume6
dc.description.issue2
dc.description.startingpage334
dc.description.endingpage344
dc.author.facultyΠολυτεχνική Σχολή / Faculty of Engineering
dc.author.departmentΤμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών / Department of Electrical and Computer Engineering
dc.type.uhtypeArticleen
dc.source.abbreviationIEEE Trans.Autom.Sci.Eng.en
dc.contributor.orcidHadjicostis, Christoforos N. [0000-0002-1706-708X]
dc.gnosis.orcid0000-0002-1706-708X


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record