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

DOI10.1109/TAC.2018.2882154zbMATH Open1482.93085arXiv1706.04072MaRDI QIDQ5223786FDOQ5223786

Eyal Weiss, Michael Margaliot

Publication date: 18 July 2019

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

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.

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)

Cited In (13)

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

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)