Evènement pour le groupe Séminaire Méthodes Formelles


Date 2019-07-09  11:00-12:00
Titre Most permissive semantics of Boolean networks 
Résumé Dynamics of Boolean networks (BNs) are usually computed according to a fixed update mode (synchronous, asynchronous, etc.). However, update modes can miss important behaviours actually realisable in more concrete multilevel or quantitative models. We introduce the most permissive semantics of BNs which guarantees a correct over-approximation of behaviours of any multilevel refinement. Moreover, it turns out that analysing the most permissive dynamics of BNs is much simpler than with update modes: reachability is PTIME (instead of PSPACE-complete), and identifying attractors is NP-complete (instead of PSPACE-complete). Therefore, computing reachable attractors become tractable to very large networks, without any assumption on their structure. We conclude on the impact for the synthesis of BNs from reachability and stability constraints. https://arxiv.org/abs/1808.10240  
Lieu178 
OrateurLoïc Paulevé  
UrlCNRS, LaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index