A Polynomial-Time Algorithm for Solving the Minimal Observability Problem in Conjunctive Boolean Networks

DOI10.1109/TAC.2018.2882154MaRDI QIDQ5223786zbMATH OpenFDO

Authors Eyal Weiss, Michael Margaliot

Publication date 18 July 2019

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.04072

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Controllability (93B05) Decentralized systems (93A14) Discrete-time control/observation systems (93C55)

Abstract: Many complex systems in biology, physics, and engineering include a large number of state-variables, and measuring the full state of the system is often impossible. Typically, a set of sensors is used to measure part of the state-variables. A system is called observable if these measurements allow to reconstruct the entire state of the system. When the system is not observable, an important and practical problem is how to add a emph{minimal} number of sensors so that the system becomes observable. This minimal observability problem is practically useful and theoretically interesting, as it pinpoints the most informative nodes in the system. We consider the minimal observability problem for an important special class of Boolean networks, called conjunctive Boolean networks (CBNs). Using a graph-theoretic approach, we provide a necessary and sufficient condition for observability of a CBN with $n$ state-variables, and an efficient~$O(n^2)$-time algorithm for solving the minimal observability problem. We demonstrate the usefulness of these results by studying the properties of a class of random CBNs.

Cited in

(13)

• Complex systems with impulsive effects and logical dynamics: a brief overview
• A survey on observability of Boolean control networks
• On quotients of Boolean control networks
• Finite-time observability of probabilistic Boolean control networks
• Minimal observability of Boolean control networks
• Bisimulations of probabilistic Boolean networks
• A polynomial-time criterion for stability of large-scale switched conjunctive Boolean networks
• Data informativity for analysis and control design of Boolean control networks
• Minimum observability of probabilistic Boolean networks
• Fault detection and pinning control of Boolean networks
• Finite-time pinning stabilization of Markovian jump Boolean networks
• Distributional observability of probabilistic Boolean networks
• Reduction and analysis of Boolean control networks by bisimulation

This page was built for publication: A Polynomial-Time Algorithm for Solving the Minimal Observability Problem in Conjunctive Boolean Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5223786)