Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

27 novembre 2017

Searching a tree with permanently noisy advice

Lucas Bockzkowski (IRIF)

In this talk, I will present and analyze a model of search trees with probabilistic memory faults. Specifically, let T be a tree of maximal degree \Delta. One of the leaves \tau is chosen adversarially. The goal is to find it by walking on the edges of T, starting at its root. To guide the algorithm in its search, nodes are decorated with an indication called advice. For a typical node v, this indication is a pointer to the neighbor of v which is closer to \tau. However, each node v is declared faulty with some small probability q, and in this case the advice is chosen uniformly amongst v’s neighbors.
Usual models of noise assume the information can be refreshed by resampling. In our case, the advice at a node is fixed forever (hence the term “memory faults”). This prevents increasing confidence by visiting several times the same node. I will present upper and lower bounds on the noise regime q that can be tolerated for efficient search, with different measures of complexity: we consider the number of steps needed to reach tau, but also the number of node queries.
Joint work with Amos Korman and Yoav Rodeh.

20 novembre 2017

Coinduction and automata algorithms

Damien Pous (ENS Lyon)

We’ll present a simple algorithm for checking language equivalence of
non-deterministic finite automata. This algorithm can be exponentially
faster than the pre-existing ones, and it exploits a technique from
concurrency theory: `bisimulations up to congruence’. We’ll then
present recent developments on the abstract theory underlying such a
technique.

13 novembre 2017

Fonctions de pulvérisation d’hypergraphes (géométriques)

Xavier Goaoc (Université de Marne la Vallée)

En géométrie discrète et algorithmique, la complexité d'une famille d'ensemble est souvent étudiée au travers de sa fonction de pulvérisation. J'introduirai à ces fonctions et discuterai de comment leur vitesse de croissance asymptotique peut être controlée par une seule de leurs valeurs, dans l'esprit de la théorie de la "dimension de Vapnik-Chervonenkis" des hypergraphes. Je décrirai en particulier une construction probabiliste qui réfute une conjecture de Bondy et Hajnal. C'est un travail commun avec Boris Bukh (https://arxiv.org/abs/1701.06632). L'exposé ne supposera pas de connaissance particulière.

6 novembre 2017

On shift-invariant maximal filters and hormonal cellular automata

Julien Cervelle (LACL)

This paper deals with the construction of shift-invariant maximal filters on ℤ and their relation to hormonal cellular automata, a generalization of the cellular automata computation model with some information about the global state shared among all the cells. We first design shift-invariant maximal filters in order to define this new model of computation. Starting from different assumptions, we show how to construct such filters, and analyze the computation power of the induced cellular automata computation model.

16 octobre 2017

Automata in Glued Vector Spaces

Daniela Petrisan (IRIF)

We introduce a new automata model, hybrid set-vector automata, designed to
accept weighted languages over a field in a more efficient way than Schützenberger’s weighted automata. The space of states for these automata is not a vector space, but rather a union of vector spaces “glued” together along subspaces. We call them hybrid automata,
since they naturally embed both deterministic finite state automata and finite automata
weighted over a field.  We prove that these automata can be minimized.  However, proving the existence of minimal automata “by hand” is rather complicated. Instead we adopt a more systematic approach and discuss the properties of the category of “glued” vector spaces that render minimization possible.

This is joint work with Thomas Colcombet. The talk can be either in English or French, depending on the audience’s preference.

2 octobre 2017

A unified formalism for monoprocessor schedulability analysis under uncertainty

Étienne André (LIPN)

The schedulability analysis of real-time systems (even on a single
processor) is a very difficult task, which becomes even more complex (or
undecidable) when periods or deadlines become uncertain.
In this work, we propose a unified formalism to model and formally
verify monoprocessor schedulability problems with several types of tasks
(periodic, sporadic, or more complex), most types of schedulers
(including EDF, FPS, SJF), with or without preemption, in the presence
of uncertain timing constants.
Although the general case is undecidable, we exhibit a large
decidable subclass.
We demonstrate the expressive power of our formalism on several
examples, allowing also for robust schedulability.

2 octobre 2017

A unified formalism for monoprocessor schedulability analysis under uncertainty

Étienne André (LIPN)

The schedulability analysis of real-time systems (even on a single
processor) is a very difficult task, which becomes even more complex (or
undecidable) when periods or deadlines become uncertain.
In this work, we propose a unified formalism to model and formally
verify monoprocessor schedulability problems with several types of tasks
(periodic, sporadic, or more complex), most types of schedulers
(including EDF, FPS, SJF), with or without preemption, in the presence
of uncertain timing constants.
Although the general case is undecidable, we exhibit a large
decidable subclass.
We demonstrate the expressive power of our formalism on several
examples, allowing also for robust schedulability.

25 septembre 2017

Small complexity classes for cellular automata, dealing with diamond and round neighborhood

Anaël Grandjean (LACL)

We are interested in 2-dimensional cellular automata and more precisely in the recognition of langages in small time. The time complexity we consider is called real-time and is rather classic for the study of cellular automata. It consists of the smallest amount of time needed to read the whole imput. It has been shown that this set of langages depend on the neighborhood of the automaton. For example the two most used neighborhoods (Moore and von Neumann ones) are different with respect to this complexity. Our study deals with more generic sets of neighborhoods, round and diamond neighborhoods. We prove that all diamond neighborhoods can recognize the same langages in real time and that the round neighborhoods can recognize stricly less than the diamond ones.