Posts classified under: Amacc

In 1964, R. Berger proved the existence of strongly aperiodic subshifts of finite type (SFT) on $\mathbb{Z}^2$, and used them to prove the undecidability of the Domino Problem. With the goal of understanding what aspects of $\mathbb{Z}^2$ account for this result, there has been an effort in recent years to characterize the groups with undecidable … Continue reading Séminaire Algorithmique : Nicolas Bitar (LAMFA, Univ. Picardie), « Subshifts of finite type and quasi-isometries beyond groups »

A graph is chordal if it has no induced cycle of length greater than 3. Alternatively, Dirac proved that a graph is chordal if and only if every minimal separator is a clique. From this characterization it is not hard to prove that a k-connected chordal graph can be uniquely decomposed into (k+1)-connected components by … Continue reading Séminaire Algorithmique : « Enumeration of some families of chordal graphs », Jordi Castellvi (Univ. Barcelone, Espagne)

Current distributed source version-control systems (such as Git and Mercurial), track the history of changes using an append-only directed acyclic graph, sometimes complemented by labels subsequently attached to commits. We present a chain-based and a dichotomy-based framework, both leveraging incremental indices, to answer reachability queries in sub-linear time, and efficiently perform label synchronisation between users. … Continue reading Séminaire Algorithmique : « Commit graphs in Version-Control Systems: incremental reachability and label discovery », Euxane Tran-Girard (LIGM, Univ. Paris-Est G. Eiffel)

La notion de structure transparaît dans de nombreux domaines scientifiques comme une approche pragmatique pour capturer le fait que des objets complexes peuvent être décomposés en éléments plus simples. Nous proposons une formalisation de cette notion et montrons comment s'en servir pour unifier diverses variations des diagrammes de décision binaires (BDD, une représentation simple, pragmatique, … Continue reading Séminaire Algorithmique : « Introduction à la théorie des structures et son application aux fonctions Booléennes », Joan Thibault (IRISA, Rennes)