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
Compositional properties of random Boolean networks
KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.ORCID iD: 0000-0001-7382-9408
KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
2005 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 71, no 5, 056116- p.Article in journal (Refereed) Published
Abstract [en]

Random Boolean networks (RBNs) are used in a number of applications, including cell differentiation, immune response, evolution, gene regulatory networks, and neural networks. This paper addresses the problem of computing attractors in RBNs. An RBN with n vertices has up to 2(n) states. Therefore, for large n, computing attractors by full enumeration of states is not feasible. The state space can be reduced by removing irrelevant vertices, which have no influence on the network's dynamics. In this paper, we show that attractors of an RBN can be computed compositionally from the attractors of the independent components of the subgraph induced by the relevant vertices of the network. The presented approach reduces the complexity of the problem from O(2(n)) to O(2(l)), where l is the number of relevant vertices in the largest component.

Place, publisher, year, edition, pages
2005. Vol. 71, no 5, 056116- p.
Keyword [en]
kauffman networks, automata
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-15020DOI: 10.1103/PhysRevE.71.056116ISI: 000231688300028Scopus ID: 2-s2.0-26944502278OAI: oai:DiVA.org:kth-15020DiVA: diva2:333061
Note

QC 20120926

Available from: 2010-08-05 Created: 2010-08-05 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Dubrova, Elena

Search in DiVA

By author/editor
Dubrova, ElenaTeslenko, Maxim
By organisation
Microelectronics and Information Technology, IMIT
In the same journal
Physical Review E. Statistical, Nonlinear, and Soft Matter Physics
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 75 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