Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Efficient observability verification for large-scale boolean control networks
KTH, School of Electrical Engineering and Computer Science (EECS), Automatic Control. KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre.
KTH, School of Electrical Engineering and Computer Science (EECS), Automatic Control. KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-9940-5929
2018 (English)In: 2018 37th Chinese Control Conference (CCC), IEEE Computer Society, 2018, p. 560-567Conference paper, Published paper (Refereed)
Abstract [en]

It is known that verifying observability of Boolean control networks (BCNs) is NP-hard in the number of nodes. In this paper, we use a node aggregation approach to overcome the computational complexity in verifying observability for networks with special structures. First, we define a class of network node aggregations with compatible observability. It is proven for this class of aggregations, the whole BCN being observable does not imply that all corresponding subnetworks are observable, and vice versa. Second, when the aggregations are acyclic, we prove that all corresponding subnetworks being observable implies that the overall BCN is observable, although the converse is not true. Third, we show that finding acyclic aggregations with small subnetworks can tremendously reduce the computational complexity in verifying observability. Finally, we use a BCN T-cell receptor kinetics model from the literature with 37 state nodes and 3 input nodes to illustrate the efficiency of these results. For this model, we derive the unique minimal set of 16 state nodes needed to be observed to make the overall BCN observable.

Place, publisher, year, edition, pages
IEEE Computer Society, 2018. p. 560-567
Series
Chinese Control Conference, ISSN 2161-2927
Keywords [en]
Boolean control network, Graph theory, Node aggregation, Observability, Cell membranes, Computational complexity, T-cells, Boolean control networks, Input node, Network node, NP-hard, Special structure, State nodes, Subnetworks, T cell receptor, Complex networks
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-247146DOI: 10.23919/ChiCC.2018.8482737ISI: 000468622100100Scopus ID: 2-s2.0-85056095636ISBN: 9789881563941 (print)OAI: oai:DiVA.org:kth-247146DiVA, id: diva2:1314027
Conference
37th Chinese Control Conference, CCC 2018; Wuhan; China; 25 July 2018 through 27 July 2018
Funder
Swedish Foundation for Strategic Research Swedish Research CouncilKnut and Alice Wallenberg Foundation
Note

QC 20190507

Available from: 2019-05-07 Created: 2019-05-07 Last updated: 2019-06-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Zhang, KuizeJohansson, Karl H.

Search in DiVA

By author/editor
Zhang, KuizeJohansson, Karl H.
By organisation
Automatic ControlACCESS Linnaeus Centre
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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