This note discusses an approach to the model reduction of discrete event systems represented by finite-state machines. A set of good reduced-order approximations of a deterministic finite-state machine M can be efficiently computed by looking at its contractions, i.e., finite-state machines constructed from M by merging two states. In some particular case, it is also possible to prove that the approximations thus constructed are infimal, in the sense that there do not exist better approximations with the same number of states. This note also defines a merit function to choose, among a set of approximations, the best one with respect to a given observed behavior.

Model reduction of finite state machines by contraction

GIUA, ALESSANDRO
2001

Abstract

This note discusses an approach to the model reduction of discrete event systems represented by finite-state machines. A set of good reduced-order approximations of a deterministic finite-state machine M can be efficiently computed by looking at its contractions, i.e., finite-state machines constructed from M by merging two states. In some particular case, it is also possible to prove that the approximations thus constructed are infimal, in the sense that there do not exist better approximations with the same number of states. This note also defines a merit function to choose, among a set of approximations, the best one with respect to a given observed behavior.
discrete-event systems; finite automata; reduced-order systems
File in questo prodotto:
File Dimensione Formato  
01tac_draft.pdf

accesso aperto

Tipologia: versione post-print
Dimensione 218.78 kB
Formato Adobe PDF
218.78 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11584/665
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact