### 27 novembre 2017

*Searching a tree with permanently noisy advice*

**Lucas Bockzkowski**

Skip to content
# Séminaires 2017-18

Contact : seminar@lacl.fr
# Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

### 27 novembre 2017

*Searching a tree with permanently noisy advice*

**Lucas Bockzkowski**
(IRIF)

### 20 novembre 2017

*Coinduction and automata algorithms*

**Damien Pous**
(ENS Lyon)

### 13 novembre 2017

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

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

### 6 novembre 2017

*On shift-invariant maximal filters and hormonal cellular automata*

**Julien Cervelle**
(LACL)

### 16 octobre 2017

*Automata in Glued Vector Spaces*

**Daniela Petrisan**
(IRIF)

### 2 octobre 2017

*A unified formalism for monoprocessor schedulability analysis under uncertainty*

**Étienne André**
(LIPN)

### 2 octobre 2017

*A unified formalism for monoprocessor schedulability analysis under uncertainty*

**Étienne André**
(LIPN)

### 25 septembre 2017

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

**Anaël Grandjean**
(LACL)

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.

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.

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.

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.

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.

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.

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.

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.

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.