Actividades

Cargando Eventos
30 octubre | 11:30 am - 1:00 pm

Seminario Doctorado en Ingeniería de Sistemas Complejos: Complejidad algorítmica en el conteo de puntos fijos en redes booleanas

El Doctorado en Ingeniería en Sistemas Complejos (DISC) invita al seminario: Complejidad algorítmica en el conteo de puntos fijos en redes booleanas.

En esta presentación vamos a estudiar las redes de autómatas booleanas (RABs).
Podemos considerar una RAB como una función f: {0,1}^n -> {0,1}^n o como el producto de n funciones f_1, f_2, …, f_n: {0,1}^n ->{0,1}.
Un problema clásico es calcular el número de puntos fijos de una RAB.
Un punto fijo x de una RAB f es una configuración x en {0,1}^n tal que f(x) = x.
Una manera de estudiar las RABs es utilizar los grafos de interacciones.
El grafo de interacción de una RAB f es un grafo con n vértices, donde existe un arco (i,j) si y solamente si el valor de f_j(x) depende de el valor de x_i. Cada RAB tiene un grafo de interacción, pero un grafo de interacción puede corresponderle varias RABs.
En esta exposición, vamos a tratar la siguiente pregunta:
¿Cuantos puntos fijos (máximos o mínimo) puede tener una RAB con un grafo de interacción G dado?
Finalmente, vamos a ver que dependiendo de la pregunta del problema, la respuesta puede estar en distintas clases de complexidad desde P hasta NEXPTIME.


Expone: Florian Bridoux, Laboratoire d’Informatique et des Systèmes. Université d’Aix-Marseille (France)

Lugar: Sala 205 E, Edificio E Talleres. Campus Peñalolén UAI. Avenida Diagonal Las Torres 2700, Peñalolén.

Más información: marco.montalva@uai.cl