kth.sePublications
Planned maintenance
A system upgrade is planned for 10/12-2024, at 12:00-13:00. During this time DiVA will be unavailable.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Computation of Natural Observers in Discrete-Event Systems
KTH, School of Industrial Engineering and Management (ITM), Centres, Innovative Centre for Embedded Systems, ICES.ORCID iD: 0000-0001-5703-5923
2010 (English)In: Discrete event dynamic systems, ISSN 0924-6703, E-ISSN 1573-7594, Vol. 20, no 1, p. 63-102Article in journal (Refereed) Published
Abstract [en]

Natural projections with the observer property have proved effective in reducing the computational complexity of nonblocking supervisory control design, and the state sizes of the resulting controllers. In this paper we present an algorithm to verify this property, or if necessary to achieve it. A natural projection is a special type of general causal reporter map; for the latter an algorithm is already known for verification and modification. This algorithm could be used to verify the observer property of a natural projection, but if the natural projection is not an observer the algorithm is not applicable to modify it to an observer. Also, while a general reporter map always admits a unique smallest refinement with the observer property, a natural projection does not. Indeed there may exist several minimal extensions to the original observable event set of a natural projection. We show that the problem of finding a minimal extension is NP-hard, but propose a polynomial-time algorithm that always finds an acceptable extension. While not guaranteed to be minimal, it is in practice often reasonably small.

Place, publisher, year, edition, pages
2010. Vol. 20, no 1, p. 63-102
Keywords [en]
Discrete-event systems, Model abstraction, Observer, Natural projection
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:kth:diva-28846DOI: 10.1007/s10626-008-0054-3ISI: 000274385100005Scopus ID: 2-s2.0-76649129040OAI: oai:DiVA.org:kth-28846DiVA, id: diva2:396825
Note
QC 20110211Available from: 2011-02-11 Created: 2011-01-21 Last updated: 2022-06-25Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Feng, Lei

Search in DiVA

By author/editor
Feng, Lei
By organisation
Innovative Centre for Embedded Systems, ICES
In the same journal
Discrete event dynamic systems
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 373 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf