Adrien Richard
I3S, University of Nice-Sophia Antipolis
https://www.i3s.unice.fr/~richard/
Date(s) : 13/03/2018 iCal
11 h 00 min - 12 h 00 min
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.
Catégories