DROPS

Document

DOI: 10.4230/OASIcs.AUTOMATA.2021.10

Non-Deterministic Updates of Boolean Networks

Authors: Loïc Paulevé and Sylvain Sené

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract

Boolean networks are discrete dynamical systems where each automaton has its own Boolean function for computing its state according to the configuration of the network. The updating mode then determines how the configuration of the network evolves over time. Many of updating modes from the literature, including synchronous and asynchronous modes, can be defined as the composition of elementary deterministic configuration updates, i.e., by functions mapping configurations of the network. Nevertheless, alternative dynamics have been introduced using ad-hoc auxiliary objects, such as that resulting from binary projections of Memory Boolean networks, or that resulting from additional pseudo-states for Most Permissive Boolean networks. One may wonder whether these latter dynamics can still be classified as updating modes of finite Boolean networks, or belong to a different class of dynamical systems. In this paper, we study the extension of updating modes to the composition of non-deterministic updates, i.e., mapping sets of finite configurations. We show that the above dynamics can be expressed in this framework, enabling a better understanding of them as updating modes of Boolean networks. More generally, we argue that non-deterministic updates pave the way to a unifying framework for expressing complex updating modes, some of them enabling transitions that cannot be computed with elementary and non-elementary deterministic updates.

Cite as

Loïc Paulevé and Sylvain Sené. Non-Deterministic Updates of Boolean Networks. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{pauleve_et_al:OASIcs.AUTOMATA.2021.10,
  author =	{Paulev\'{e}, Lo\"{i}c and Sen\'{e}, Sylvain},
  title =	{{Non-Deterministic Updates of Boolean Networks}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{10:1--10:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.10},
  URN =		{urn:nbn:de:0030-drops-140196},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.10},
  annote =	{Keywords: Natural computing, discrete dynamical systems, semantics}
}

Document

DOI: 10.4230/LIPIcs.CONCUR.2017.18

Goal-Driven Unfolding of Petri Nets

Authors: Thomas Chatain and Loïc Paulevé

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract

Unfoldings provide an efficient way to avoid the state-space explosion due to interleavings of concurrent transitions when exploring the runs of a Petri net. The theory of adequate orders allows one to define finite prefixes of unfoldings which contain all the reachable markings. In this paper we are interested in reachability of a single given marking, called the goal. We propose an algorithm for computing a finite prefix of the unfolding of a 1-safe Petri net that preserves all minimal configurations reaching this goal. Our algorithm combines the unfolding technique with on-the-fly model reduction by static analysis aiming at avoiding the exploration of branches which are not needed for reaching the goal. We present some experimental results.

Cite as

Thomas Chatain and Loïc Paulevé. Goal-Driven Unfolding of Petri Nets. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chatain_et_al:LIPIcs.CONCUR.2017.18,
  author =	{Chatain, Thomas and Paulev\'{e}, Lo\"{i}c},
  title =	{{Goal-Driven Unfolding of Petri Nets}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.18},
  URN =		{urn:nbn:de:0030-drops-77730},
  doi =		{10.4230/LIPIcs.CONCUR.2017.18},
  annote =	{Keywords: model reduction; reachability; concurrency; unfoldings; Petri nets; automata networks}
}

Search Results

Documents authored by Paulevé, Loïc

Non-Deterministic Updates of Boolean Networks

Abstract

Cite as

Goal-Driven Unfolding of Petri Nets

Abstract

Cite as

Thanks for your feedback!

Could not send message