Fixing monotone boolean networks asynchronously

Carte non disponible

Date/heure
Date(s) - 13/03/2018
11 h 00 min - 12 h 00 min

Catégories


A monotone boolean network with n components is a directed graph on [n]≔{1,…,n} where each vertex is labeled by a binary variable and a local transition function, which is monotone, boolean and whose inputs are the binary variables of the in-neighbors. An asynchronous run consists in updating vertices, one at each step, by applying its local transition function. Thus a run can be described by the sequence of vertices to update, that is, a word on the alphabet [n]. We prove that there exists a word W on [n] of cubic length such that, for every monotone network with n components, and for every initial configuration, the run described by W leads to a fixed configuration. We also prove that any word with this property is at least of quadratic length. To construct W, we use the following basic result about n-complete words: there is a word of quadratic length containing, as subsequences, all the permutations of [n]. For the lower-bound, we prove the following: there exists a subexponential set of permutations of [n] such that every word containing all these permutations as subsequences is of quadratic length.
This is a joint work with Julio Aracena, Maximilien Gadouleau and Lilian Salinas. A preprint is available here: https://arxiv.org/abs/1802.02068.

http://www.i3s.unice.fr/~richard/

Olivier CHABROL
Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange