|
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
|
Lieu | 178 |
Orateur | Loïc Paulevé |
Url | CNRS, LaBRI |
Aucun document lié à cet événement. RetourRetour à l'index
| |