Institut de Mathématiques de Marseille, UMR 7373


Accueil >

Fixing monotone boolean networks asynchronously

Mardi 13 mars 2018 11:00-12:00 - Adrien RICHARD - I3S, Université de Sophia-Antipolis

Fixing monotone boolean networks asynchronously

Résumé : 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 :

Lieu : Salle des séminaires 304-306 (3ème étage) - Institut de Mathématiques de Marseille (UMR 7373)
Site Sud - Bâtiment TPR2
Campus de Luminy, Case 907
13288 MARSEILLE Cedex 9

Exporter cet événement

Pour en savoir plus sur cet événement, consultez l'article Séminaire Dynamique, Arithmétique, Combinatoire (Ernest)