BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:7359@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20180313T110000
DTEND;TZID=Europe/Paris:20180313T120000
DTSTAMP:20241120T203926Z
URL:https://www.i2m.univ-amu.fr/evenements/fixing-monotone-boolean-network
 s-asynchronously/
SUMMARY:Adrien Richard (I3S\, University of Nice-Sophia Antipolis): Fixing 
 monotone boolean networks asynchronously
DESCRIPTION:Adrien Richard: A monotone boolean network with n components is
  a directed graph on [n]≔{1\,…\,n} where each vertex is labeled by a b
 inary variable and a local transition function\, which is monotone\, boole
 an and whose inputs are the binary variables of the in-neighbors. An async
 hronous run consists in updating vertices\, one at each step\, by applying
  its local transition function. Thus a run can be described by the sequenc
 e of vertices to update\, that is\, a word on the alphabet [n]. We prove t
 hat there exists a word W on [n] of cubic length such that\, for every mon
 otone network with n components\, and for every initial configuration\, th
 e run described by W leads to a fixed configuration. We also prove that an
 y 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 wor
 d of quadratic length containing\, as subsequences\, all the permutations 
 of [n]. For the lower-bound\, we prove the following: there exists a subex
 ponential set of permutations of [n] such that every word containing all t
 hese permutations as subsequences is of quadratic length.\nThis is a joint
  work with Julio Aracena\, Maximilien Gadouleau and Lilian Salinas. A prep
 rint is available here: https://arxiv.org/abs/1802.02068.\n&nbsp\;
CATEGORIES:Séminaire,Ernest
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20171029T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR