Regular word grammars are context-free grammars having restricted rules, that define all recognizable languages of words. This paper generalizes regular grammars from words to certain classes of graphs, by defining regular grammars for unordered unranked trees and graphs of tree-width 2 at most. The qualifier ``regular'' is justified because these grammars define precisely the recognizable (equivalently, CMSO-definable) sets of the respective graph classes. The proof of equivalence between regular and recognizable sets of graphs relies on the effective construction of a recognizer algebra of size doubly-exponential in the size of the grammar. This sets a 2EXPTIME upper bound on the (EXPTIME-hard) problem of inclusion of a context-free language in a regular language, for graphs of tree-width 2 at most. A further syntactic restriction of regular grammars suffices to capture precisely the MSO-definable sets of graphs of tree-width 2 at most, i.e., the sets defined by CMSO formulae without cardinality constraints. Moreover, we show that MSO-definability coincides with recognizability by algebras having an aperiodic parallel composition semigroup, for each class of graphs defined by a bound on the tree-width.

Les circuits reconfigurables FPGA (Field-Programmable Gate Arrays) constituent une cible de choix pour la mise en œuvre d'architectures matérielles spécialisées : ils exposent du parallélisme à grain très fin et offrent un accès direct au monde physique via des broches d'entrées/sorties.

Dans cet exposé, je présenterai un modèle de programmation pour mélanger calcul et interaction sur FPGA. Ce modèle de programmation permet de composer à la fois des comportements réactifs orientés flot de données et des calculs parallèles en mémoire partagée, avec de la concurrence déterministe et des performances prédictibles. Il s'est avéré suffisamment expressif pour développer des environnements d'exécution sur mesure, comme par exemple, une implémentation matérielle de la machine virtuelle OCaml ainsi qu'une bibliothèque d'exécution simplifiée pour OCaml (incluant un gestionnaire automatique de mémoire) avec appel d'accélérateurs via la FFI.

Je vais présenter la construction de complétions de Rezk “strictes”. En théorie des types homotopique, la complétion de Rezk d'une catégorie C est une catégorie univalente équivalente à C. Dans un cadre plus spécifique (les ensembles cubiques), la complétion de Rezk stricte permet de plus de conserver certaines égalités strictes (lois d'associativité et de neutralité).

Cette construction s'applique non seulement aux catégories, mais aussi aux modèles de la théorie des types. Elle permet alors de prouver la canonicité homotopique pour la théorie des types homotopique. Plus de détails peuvent êtres trouvés dans https://arxiv.org/abs/2311.05849.

We define pathographs, that is a generalization of graphs. Pathographs have vertices and edges, as graphs, but they also have « ur-path », that are special edges (that we will later subdivide). There are also spokes, that are adjacencies between vertices and ur-paths, and rungs, that are adjacencies between ur-paths. A realization of a pathograph G is any graph G' obtained from G be replacing each ur-path by a path of length at least 2. Furthermore, for each spoke v-p there must be at least one edge between v and the path P arising from the ur-path p, and for each rung pq, there must be at least one edge between the paths P, Q arising from p and q respectively. There are no other vertices or edges.

We consider the problem whose instance is a pathgraph G and a finite set of graphs F. The question is whether there exists a realization of G that contains no graph from F as an induced subgraph. We prove that this problem is undecidable (by reducing the Wang tiles problem to it). This result has several motivations. Pathographs are flexible enough to encode several graph containment problems. Some of them seems easy though it not known whether an algorithm exists for them, and our result show that this is not trivial. Also, many proofs in structural graph theory relies on a fact that some pathograph cannot be realized without introducing a forbidden induced subgraphs, so our result show that automatic provers for such lemmas do not exists in general.

This a joint work with Daniel Carter.

We present a complete characterization of two non-integers with the same Rényi-Parry measure. We prove that for two non-integers $\beta_1 ,\beta_2 >1$, the Rényi-Parry measures coincide if and only if $\beta_1$ is the root of equation $x^2-qx-p=0$, where $p,q\in\mathbb{N}$ with $p\leq q$, and $\beta_2 = \beta_1 + 1$, which confirms a conjecture of Bertrand-Mathis in [A. Bertrand-Mathis, Acta Math. Hungar. 78, no. 1-2 (1998):71–78].

We study the minority-opinion dynamics over a fully-connected network of $n$ nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number of neighbors chosen uniformly at random. Each activated node then adopts the opinion that is least common within the received sample. Unlike all other known consensus dynamics, we prove that this elementary protocol behaves in different ways, depending on whether activations occur sequentially or in parallel. Specifically, we show that its expected consensus time is exponential in n under asynchronous models, but, on the other hand, we show that it converges within $O(\log^2 n)$ rounds with high probability under synchronous models.

Our results shed light on the bit-dissemination problem, which was previously introduced to model the spread of information in biological scenarios. Specifically, our analysis implies that the minority-opinion dynamics is the first memoryless solution to this problem, in the parallel passive-communication setting, achieving convergence within a polylogarithmic number of rounds. This, together with a known lower bound for sequential stateless dynamics, implies a parallel-vs-sequential gap for this problem that is nearly quadratic in the number $n$ of nodes. This is in contrast to all known results for problems in this area, which exhibit a linear gap between the parallel and the sequential setting.

Continuation of part I. I intend to cover

1. applications of WQOs in algorithmic graph theory,
2. a focus on classes of graphs that are well-quasi-ordered by the induced subgraph ordering, along with Pouzet’s Conjecture,
3. the generalisation to preservation properties in first-order logic.

Résumé : Dans le cadre d'un projet de recherche sur les langages de programmation pour les systèmes hybrides, autour du langage Zelus (https://zelus.di.ens.fr), nous avons développé la bibliothèque Sundials/ML (https://inria-parkas.github.io/sundialsml/) pour interfacer OCaml avec les structures de données et les algorithmes du logiciel Sundials développé à Lawrence Livermore National Laboratories. Nous nous sommes efforcés de créer une interface complet, efficace et proche de celui proposé aux programmeurs C, tout en voulant exploiter le système de types et les fonctionnalités d'OCaml (types algébriques de données, fonctions d'ordre supérieur, exceptions, gestion automatique de la mémoire). Le partage de données entre OCaml et C s'avère particulièrement délicat dans ce contexte où un fil d'exécution peut se faufiler entre les deux langages. Certaines de nos solutions pour ce problème sont satisfaisantes, d'autres moins. Nous en présenterons quelques-unes.