2010/2011 T. Kaced (tarik.kaced[at]lif.univ-mrs.fr)
Exposés passés
12 mai 2011 ~ Tarik Kaced. (Un)constrained Linear Information Inequalities.Date de publication : 12 mai 2011 par Tarik Kaced
For each collection of n discrete random variables, we can define a vector of 2^n-1 entropies, one for each singleton, pair, triple etc. We study the subset of the Euclidian space R^2^n-1 consisting of all such vectors, and few other related (...)
En savoir plus...5 mai 2011 ~ Thomas Hugel. Mesurer la satisfaisabilité par des poids..
Date de publication : 5 mai 2011 par Tarik Kaced
Nous présenterons le phénomène de transition de phase dans les problèmes de satisfaction de contraintes (CSP). Le calcul de la valeur du seuil (dans 3-SAT notamment) résiste depuis une vingtaine d'années. En particulier, nous montrerons (...)
7 avril 2011 ~ Pascal Vanier. Ensembles $\pi^0_1$ et pavages. .
Date de publication : 7 avril 2011 par Tarik Kaced
Les pavages et la récursivité sont intimement liés : en 1964, Berger prouvait l'indécidabilité de la pavabilité du plan, par la suite, Hanf et Myers prouvèrent qu'il existe des jeux de tuiles n'admettant aucun pavage récursif. Puis Simpson (...)
24 mars 2011 ~ Kevin Perrot. Kadanoff sandpile model : in pursuit of a wave pattern.
Date de publication : 24 mars 2011 par Tarik Kaced
Sand pile models are dynamical systems describing the evolution from N stacked grains to a stable configuration. It uses local rules to depict grain moves and iterate it until reaching a stable configuration from which no rule can be applied. (...)
22 février 2011 ~ Antoine Taveneaux. Vers une axiomatisation de la complexité de Kolmogorov.
Date de publication : 22 février 2011 par Tarik Kaced
Nous commencerons par présenter un résultat de A. Shen montrant que quatre propriétés élémentaires de la complexité de Kolmogorov (la complexité pleine) suffisent à la caractériser. Après avoir présenté cette caractérisation, nous allons prouver (...)
10 février 2011 ~ Luidnel Maignan. Points, Distances and Cellular Automata : Geometric and Spatial Algorithmics.
Date de publication : 10 février 2011 par Tarik Kaced
Spatial computing aims at providing a scalable framework where computation is distributed on a uniform computing medium and communication happen locally between nearest neighbors. We study the particular framework of cellular automata, using a (...)
3 février 2011 ~ Benjamin Hellouin De Menibus. Particules et automates cellulaires..
Date de publication : 3 février 2011 par Tarik Kaced
Un système dynamique auto-organisant peut être décrit de la manière suivante : avec des conditions initiales aléatoires, l'évolution du système laisse apparaître des structures régulières, qui sont toujours les mêmes. On s'intéresse ici à (...)
27 janvier 2011 ~ Youssouf Oualhadj. Probabilistic Automata on Finite Words : Decidable and Undecidable Problems.
Date de publication : 27 janvier 2011 par Tarik Kaced
In this talk we present three algorithmic problems for probabilistic automata on finite words : the Emptiness Problem, the Isolation Problem and the Value 1 Problem. The Emptiness Problem asks, given some probability 0\leq\lambda\leq 1, whether (...)
20 janvier 2011 ~ Mathilde Noual. Etude combinatoire de la dynamique des circuits d’automates booléens.
Date de publication : 20 janvier 2011 par Tarik Kaced
Les réseaux d'automates booléens sont des systèmes dynamiques discrets largement utilisés dans la modélisation de phénomènes réels (régulations biologiques, en particulier, génétiques, circuits logiques, propagation d'épidémies...). Pour (...)
25 novembre 2010 ~ Martin Delacourt. Théorème de Rice pour les ensembles mulimites d’automates cellulaires.
Date de publication : 25 novembre 2010 par Tarik Kaced
à venir
4 novembre 2010 ~ Andrei Romashchenko. On information inequalities.
Date de publication : 4 novembre 2010 par Tarik Kaced
We will talk about linear inequalities that are true for Shannon's entropies of any random variables. This class of inequalities surprisingly coincides with several other classes of inequalities : the inequalities that are valid for Kolmogorov (...)
28 octobre 2010 ~ Alexander Shen. K-reducibility and ML-reducibility are equivalent (following Joe Miller).
Date de publication : 28 octobre 2010 par Tarik Kaced
There are many difficult results where computability theory meets randomness. In this talk (following the explanations of Joe Miller) we will consider a very small and (relatively) very simple result. If oracle $A$ is Turing-reducible to $B$, (...)
21 octobre 2010 ~ Alex Borello. A speed-up of oblivious multi-head finite automata by cellular automata.
Date de publication : 21 octobre 2010 par Tarik Kaced
We present a parallel speed-up of a simple, yet significantly powerful, sequential model by cellular automata. The simulated model is called oblivious multi-head finite automata and is characterized by the fact that the trajectory of the heads (...)
13 octobre 2010 ~ Valentin Shehtman. Some directions in contemporary modal logic.
Date de publication : 13 octobre 2010 par Tarik Kaced
In recent 20 years modal logic became more oriented to different applications in Computer Science (knowledge representation, spatial reasoning, program verification etc.) On the other hand, theoretical modal logic is now connected to different (...)
30 septembre 2010 ~ Pierre Guillon. Des machines qui zigzaguent.
Date de publication : 30 septembre 2010 par Tarik Kaced
On étudie les machines de Turing via la dynamique topologique et symbolique. On peut leur associer un sous-décalage qui représente la succession des états pris par la tête et des caractères qu'elle lit lors d'un calcul ; on s'intéresse alors à (...)
30 septembre 2010 ~ Julien Cassaigne. Le shift impair bidimensionnel est sofique.
Date de publication : 30 septembre 2010 par Tarik Kaced
On appelle "shift impair" l'ensemble des parties de Z^d dont les composantes connexes finies sont toutes de cardinal impair, vu comme un sous-shift de 0,1^(Z^d). Mike Hochman a posé la question de savoir si ce système était sofique, voir (...)
16 septembre 2010 ~ Alexis Ballier. Exemple d’automates cellulaires stables et instables ayant le même ensemble limite.
Date de publication : 16 septembre 2010 par Tarik Kaced
On peut définir la notion d'ensemble limite pour un automate cellulaire (AC). Certains AC l'atteignent en temps fini et sont dits stables, les autres sont dits instables. Depuis les travaux de A. Maass sur le sujet, une question était restée en (...)
8 juillet 2010 ~ Eric Goles. Dynamique et complexité du modele de segregation de Schelling .
Date de publication : 8 juillet 2010 par Martin Delacourt
A venir.
8 juillet 2010 ~ Guillaume Escamocher. A Refinement of the Notion of Temperature in Combinatorial Games.
Date de publication : 8 juillet 2010 par Fabien Givors
We present here a study of combinatorial games, introduced by John Horton Conway. These games are complete information ones, and to each of them is associated a value, which represents its winning strategy. One of the main goals in this area of (...)
1er juillet 2010 ~ Petr Kůrka. Arithmetical algorithms in Moebius number systems.
Date de publication : 1er juillet 2010 par Fabien Givors
Moebius number systems generalize positional systems and continued fractions and represent real numbers by infinte compositions of a finite number of Moebius transformations of the form F(x)=(ax+b)/(cx+d). If the system is redundant, i.e., if (...)
10 juin 2010 ~ Laurent Boyer. On factor universality in cellular automata.
Date de publication : 10 juin 2010 par Fabien Givors
3 juin 2010 ~ Chaim Goodman-Strauss (salle 003). Regular Productions and Strongly Aperiodic Tilings of the Hyperbolic Plane.
Date de publication : 3 juin 2010 par Fabien Givors
“Regular production systems”, non-deterministic production rules restricted to a regular language, model tilings in a wide range of settings. We discuss applications to “strongly aperiodic” sets of tiles in the hyperbolic (...)
27 mai 2010 ~ Michael Weiss. Computability and Tilings.
Date de publication : 27 mai 2010 par Fabien Givors
Pavages et théorème de récursion à la Kleene.
20 mai 2010 ~ Victor Poupet. Robinson revisited (yes... again).
Date de publication : 20 mai 2010 par Fabien Givors
20 mai 2010 ~ Alex Borello, Martin Delacourt, Tarik Kaced, Pascal Vanier. Divers exposés des divers doctorants.
Date de publication : 20 mai 2010 par Fabien Givors
Présentation de leurs divers travaux.
4 mai 2010 ~ Thomas Fernique. Sur la formation des quasicristaux.
Date de publication : 4 mai 2010 par Fabien Givors
On proposera un modèle de formation des quasicristaux à base de pavages de type fini sur lesquels agissent des chaînes de Markov aléatoires dont les distributions stationnaires plaisent aux physiciens (Boltzmann). On montrera des résultats (...)
8 avril 2010 ~ Pascal Vanier. Présentation du papier Tilings robust to errors.
Date de publication : 8 avril 2010 par Fabien Givors
We study the error robustness of tilings of the plane. The fundamental question is the following : given a tileset, what happens if we allow a small probability of errors ? Are the objects we obtain close to an error-free tiling of the plane ? (...)
25 mars 2010 ~ Laurent Braud. Ordres dans la hiérarchie à pile.
Date de publication : 25 mars 2010 par Fabien Givors
La « hiérarchie à pile » est une famille de classes de graphes au croisement de domaines tels que les automates à piles d'ordre supérieur, les grammaires de termes et les transformations logiques. Les graphes que l'on y trouve ont une théorie (...)
18 mars 2010 ~ Towards new interactions between mathematics and computer science . Tiling and Automata (Joerg Thuswaldner & Jacques Sakarovitch).
Date de publication : 18 mars 2010 par Fabien Givors
Lien
Application of automata to topology of tilings. Keywords : Relation of contact graph and adding machine. Boundary of tiles. Cancellation problem of free group endomorphsim
L'heure et le lieu (frumam / cirm / ailleurs) ne sont pas encore (...)
1er mars 2010 ~ Semaine Math-Info au CIRM. Topological Methods For The Study Of Discrete Structures.
Date de publication : 1er mars 2010 par Fabien Givors
* Ron Aharoni : Connectivity, colorability and matchability.
Abstract : « Hypergraphs (namely sets of sets, the latter being called "edges") can be realized geometrically : every vertex is represented by a point in R^n and every edge is (...)
15 février 2010 ~ Semaine Math-Info au CIRM. Multi-dimensional Subshifts And Tilings.
Date de publication : 15 février 2010 par Fabien Givors
Link : http://www.lirmm.fr/arith/wiki/MathInfo2010/Multi-dimensionalSubshiftsAndTilings
Courses
* Mike Boyle : Multidimensional Shifts of Finite Type and Sofic Shifts
Abstract : « A Z^d shift of finite type (SFT) is a topological dynamical (...)
8 février 2010 ~ Semaine Math-Info au CIRM. Dynamics And Computation.
Date de publication : 8 février 2010 par Fabien Givors
Courses
* Olivier Bournez : Analog Models of Computations
Abstract : « We will provide an overview of theories of computation for analog models of computation, focusing mainly on continuous time models of computation. These theories allow us (...)
1er février 2010 ~ Semaine Math-Info au CIRM. Lattice Algorithmics.
Date de publication : 1er février 2010 par Fabien Givors
Courses
* Ali Akhavi : o Introduction to lattice reduction and to the LLL algorithm. o Analysis of the LLL algorithm in the uniform model of the unit ball.
* Nicolas Chevallier o Best simultaneous diophantine approximations.
* Damien Stehlé : (...)
21 janvier 2010 ~ Alexis Ballier (14h, salle 103). Caractérisation des sous-shifts indénombrables.
Date de publication : 21 janvier 2010 par Fabien Givors
Dans cet exposé nous nous intéresserons aux ensembles indénombrables de pavages. Les ensembles de pavages sont des cas particuliers d'une notion plus générale : les sous-shifts. Nous savons qu'un sous-shift est indénombrable si et seulement s'il (...)
10 décembre 2009 ~ Vincent Delecroix. Classification des billards. Comptages..
Date de publication : 10 décembre 2009 par Fabien Givors
Les échanges d'intervalles sont des systèmes dynamiques que l'on obtient comme application de premier retour d'un flot de surface sur un intervalle. Cette technique générale (mise en place par Poincaré) permet de passer d'une dynamique en temps (...)
12 novembre 2009 ~ Gregory Lafitte. Countable ordinals galore ℵ.
Date de publication : 12 novembre 2009 par Fabien Givors
(suite)
5 novembre 2009 ~ Gregory Lafitte. Countable ordinals galore.
Date de publication : 5 novembre 2009 par Fabien Givors
TBA (ou pas)
29 octobre 2009 ~ Olivier Bournez. Caractérisations algébriques de classes de complexité.
Date de publication : 29 octobre 2009 par Fabien Givors
Nous nous intéresserons à différentes caractérisations algébriques indépendantes des machines de classes de complexité, et à leurs applications.
On peut définir la notion de fonction calculable algébriquement, c'est-à-dire à partir de fonctions (...)
8 octobre 2009 ~ Alex Borello. Language Recognition on One-Way Cellular Automata.
Date de publication : 8 octobre 2009 par Fabien Givors
We review some properties of language recognition on cellular automata using a one-way neighbourhood ; in particular, the languages included in a*b*, among which a^nb^(kn) : k, n integers > 0 cannot be (...)
1er octobre 2009 ~ Alexis Ballier. Lohrey, pavages et conséquences.
Date de publication : 1er octobre 2009 par Fabien Givors
Résumé à venir
24 septembre 2009 ~ Martin Delacourt. From consequences to directional dynamics along arbitrary curves on cellular automata of dimension 1.
Date de publication : 24 septembre 2009 par Fabien Givors
The classical dynamical properties of cellular automata (expansivity, sensivity, equicontinuity) are most of the time considered along the line (x=0). Mathieu Sablik extended these properties first to all lines, and here we want to deal with (...)
17 septembre 2009 ~ Pascal Vanier. Bornes pour automates cellulaires non surjectifs.
Date de publication : 17 septembre 2009 par Fabien Givors
Les automates cellulaires sont des systèmes dynamiques homogènes discrets. Les automates cellulaires de dimension 1 ont :
des configurations finies (ou mots) sans préimage, appelés orphelins
des paires de mots différents, mais de suffixe et (...)
23 juin 2009 ~ Joseph Miller. A venir.
Date de publication : 23 juin 2009 par Martin Delacourt
A venir.
17 juin 2009 ~ Pascal Vanier. Périodicités dans les pavages..
Date de publication : 17 juin 2009 par Martin Delacourt
On étudie ici les ensembles de périodes dans les pavages, introduisant une notion de reconnaissabilité par pavage liée aux périodes. On établit des analogies avec certaines classes de complexité nous permettant de déduire des résultats sur la (...)
2 juin 2009 ~ Francesca Fiorenzi. Automates cellulaires et groupes finiment engendres.
Date de publication : 2 juin 2009 par Martin Delacourt
On considère des automates cellulaires dont l'univers est le graphe de Cayley d'un groupe finiment engendré. En ce contexte plus général, on introduit la notion de système dynamique symbolique (ou shift) et on étudie certaines propriétés (...)
26 mai 2009 ~ Benoît Masson. Simulation de pavages en voisinage quelconque par des polyominos .
Date de publication : 26 mai 2009 par Martin Delacourt
Dans certaines applications pratiques de la modélisation par pavages, il peut arriver que l'on ait besoin d'utiliser des tuiles plus générales que les tuiles de Wang, avec des voisinages complexes et arbitrairement grands. Ces nouvelles (...)
19 mai 2009 ~ Charles Radin. Structure in dense systems of many particles..
Date de publication : 19 mai 2009 par Martin Delacourt
http://www.ma.utexas.edu/users/radin/
14 mai 2009 ~ Siamak Taati. What conservation laws may tell us about the dynamics of a cellular automaton ?.
Date de publication : 14 mai 2009 par Martin Delacourt
I will talk about some restrictions that the existence of conservation laws imposes on the dynamical properties of a CA. A trivial example is that a CA with a non-trivial conservation law cannot be nilpotent. A less trivial result is that (...)
5 mai 2009 ~ Thomas Fink. Dynamics of network motifs / self-assembly and physical complexity.
Date de publication : 5 mai 2009 par Martin Delacourt
I will give a talk in two parts :
1. We study the dynamics of network motifs by treating them as small Boolean networks and comprehensively evaluating all possible binary (Boolean) update rules. We introduce a formalism for classifying (...)
28 avril 2009 ~ Olivier Finkel. Sur les langages de figures infinies acceptés par systèmes de pavages.
Date de publication : 28 avril 2009 par Martin Delacourt
On rappellera les notions d'acceptation de langages de mots bi-dimensionnels infinis, ou figures infinies, par systèmes de pavages, en considérant diverses conditions d'acceptation. On présentera des résultats sur la complexité topologique de (...)
21 avril 2009 ~ Nicolas Ollinger. Periodicity and Immortality in Reversible Computing .
Date de publication : 21 avril 2009 par Martin Delacourt
Cellular automata are compact and very uniform discrete dynamical systems with complex dynamics. Some complexity is due to computational phenomena, the model being discrete with local interactions. In this talk, in order to investigate the (...)
14 avril 2009 ~ David Renault. The uniform locally finite tilings of the plane.
Date de publication : 14 avril 2009 par Martin Delacourt
This talk presents a family of tilings of the plane called the uniform locally finite tilings of the plane. A uniform tiling is a tiling whose group of automorphisms is transitive on its set of vertices. The locally finite property means that (...)
24 mars 2009 ~ Vincent Nesme. Automates cellulaires et fractales.
Date de publication : 24 mars 2009 par Martin Delacourt
En étudiant une certaine classe d'automates cellulaires, dits "de Clifford", on s'aperçoit que des structures fractales aparaissent dans leurs diagrammes espace-temps. Je vais expliquer pourquoi ces structures aparaissent et comment les prévoir, (...)
18 mars 2009 ~ Lucas Gérin. Automates cellulaires aléatoires : quelques problèmes en dimension 2.
Date de publication : 18 mars 2009 par Martin Delacourt
Je parlerai d'automates cellulaires aléatoires "totalement asynchrones" : une cellule est tirée au hasard à chaque étape, et mise à jour. Je me concentrerai sur quelques exemples caractéristiques de la dimension 2, liés à des questions de (...)
3 mars 2009 ~ Emmanuel Jeandel. A forgotten proof of the domino problem.
Date de publication : 3 mars 2009 par Martin Delacourt
Lewis and Aanderaa gave in 1974 a new proof of the undecidability of the domino problem. This proof is not widely known and entirely different from the usual proofs (Berger, Robinson, Kari...). I will present the ideas of this result without the (...)
26 février 2009 ~ Andrés Moreira. Old results and some open questions on number-conserving cellular automata.
Date de publication : 26 février 2009 par Martin Delacourt
Number-conserving cellular automata are cellular automata in which the states are numbers, and the sum of those numbers remains unchanged under the system's dynamics ; they appear naturally in several modeling fields, and have been the topic of (...)
19 février 2009 ~ Laurent Bienvenu. Des suites pas si triviales.
Date de publication : 19 février 2009 par Martin Delacourt
Dans les années 1960-1970, les travaux de Kolmogorov, Martin-Löf, Chaitin ,Levin, Schnorr, etc, ont permis de donner une définition mathématique rigoureuse de suite binaire infinie aléatoire. En fait, plusieurs définitions ont été à ce jour (...)
17 février 2009 ~ Jérémie Chalopin. Playing with Population Protocols.
Date de publication : 17 février 2009 par Martin Delacourt
Population protocols have been introduced by Angluin et al. as a model of sensor networks consisting of very limited mobile agents with no control over their own movement : A collection of anonymous agents, modeled by finite automata, interact (...)
10 février 2009 ~ Damien Régnault. Minorité stochastique sur les graphes..
Date de publication : 10 février 2009 par Martin Delacourt
Nous considérons un graphe où les cellules sont caractérisées par un état qui est soit noir, soit blanc. À chaque pas de temps, une cellule, choisie aléatoirement, se met à jour et passe dans l'état minoritaire dans son voisinage. L'évolution (...)
3 février 2009 ~ Florent Becker. Self-assembly fo the whole plane..
Date de publication : 3 février 2009 par Martin Delacourt
A venir.
27 janvier 2009 ~ Pierre Guillon. Asymptotic sets of dynamical systems..
Date de publication : 27 janvier 2009 par Martin Delacourt
The asymptotic (or ultimate) set of some dynamical system is a notion which represents its (very-)long-time behavior, in the sense that each point, during its evolution, will "look more and more like" points of the asymptotic set. Formally, a (...)
15 janvier 2009 ~ Xavier Provençal. A sub-quadratic algorithm to determine if a polyomino tiles the plane by translation .
Date de publication : 15 janvier 2009 par Martin Delacourt
Given a polyomino code by its contour word, the Beauquier-Nivat characterization gives necessary and sufficient criteria for that polyomino to tile the plane by translation. The computation of the longest common extension of two words in (...)
13 janvier 2009 ~ Vladimir Podolskii. Bounds on Weights of Perceptrons.
Date de publication : 13 janvier 2009 par Martin Delacourt
A threshold gate is a Boolean computational element defined by a linear combination of its input variables with integer coefficients (weights). It outputs 1 if this combination is positive and 0 otherwise. The sum of absolute values of (...)
11 décembre 2008 ~ Sylvain Sené. Influence of boundary conditions in threshold Boolean automata networks.
Date de publication : 11 décembre 2008 par Martin Delacourt
We will focus on the influence of boundary conditions in threshold Boolean automata networks, which are discrete mathematical objects classicaly used to model biological regulations systems. The objective is to emphasise that boundaries (which (...)
25 novembre 2008 ~ Adrien Richard. Circuits positifs et négatifs dans les systèmes dynamiques discrets.
Date de publication : 25 novembre 2008 par Martin Delacourt
On présente un modèle discret général pour la dynamique des réseaux de gènes basé sur la méthode logique de René Thomas : la dynamique d'un réseau de n gènes est décrite par les itérations asynchrones d'une application F qui envoie le produit de (...)
13 novembre 2008 ~ Edmund Harriss. Rauzy Fractals from PV (Pisot) to Non-PV .
Date de publication : 13 novembre 2008 par Martin Delacourt
It is well known that Hyperbolic automorphisms of the 2-torus admit a markov partition. This markov partition is closely related to 1 dimensional tilings of the line called Sturmian tilings. In the general case any hyperbolic toral automorphism (...)
12 novembre 2008 ~ Bruno Grenet. Acceptable Complexity Measure of Theorems.
Date de publication : 12 novembre 2008 par Martin Delacourt
In 1930, Gödel presented in Königsberg his famous Incompleteness Theorem, stating that some true mathematical statements are unprovable. Yet, this result gives us no idea about those independent (that is, true and unprovable) statements, about (...)
6 novembre 2008 ~ Nathalie Aubrun. Un ordre sur les sous-shifts et son équivalent sur les langages.
Date de publication : 6 novembre 2008 par Martin Delacourt
Traditionally a tiling is defined with a finite number of finite forbidden patterns. We can generalize this notion considering any set of patterns. Generalized tilings defined in this way can be studied with a dynamical point of view, leading to (...)
6 novembre 2008 ~ Thierry Monteil. Mesures ergodiques en dynamique symbolique.
Date de publication : 6 novembre 2008 par Martin Delacourt
Lorsqu'on essaye de montrer l'existence de fréquences d'apparition de motifs dans un mot infini, on est amené à étudier l'ensemble des mesures invariantes du sous-shift associé. J'essaierai d'introduire ces notions puis donnerai une majoration (...)
16 octobre 2008 ~ Victor Poupet. Ultimate cellular complexity.
Date de publication : 16 octobre 2008 par Martin Delacourt
In a previous adventure, super-scientists Bruno Durand, Leonid A. Levin and Alexander Shen have won a heroic battle against the forces of Order and Regularity by producing a set of Wang tiles that can only generate tilings of maximal complexity, (...)
9 octobre 2008 ~ Alexis Ballier. Automates cellulaires à états continus.
Date de publication : 9 octobre 2008 par Martin Delacourt
Pour le résumé : Cet exposé présentera les travaux de P. Flocchini et H. Betel sur les automates cellulaires à états dans [0 ;1], quelques fois en tentant de les généraliser sans grand succès. La méthode utilisée pour obtenir des AC à états (...)
2 octobre 2008 ~ Andrei Romashchenko. Kolmogorov complexity and basic information quantities..
Date de publication : 2 octobre 2008 par Martin Delacourt
Theory of Kolmogorov complexity defines some measure of information contained in each tuple of individual words (i.e., complexity of each word, complexity of each pair of words, etc). These information quantities being calculated for different (...)
18 septembre 2008 ~ Thomas Fernique. Pavages, règles locales, substitutions et fractions continues : quelques résultats et quelques questions..
Date de publication : 18 septembre 2008 par Martin Delacourt
Dans cet exposé, je présenterai le contexte de mes travaux de thèse, quelques résultats (brièvement), et quelques questions ouvertes, notamment celles que j'aimerais examiner avec les (éventuelles) personnes intéressées de (...)
4 septembre 2008 ~ Philippe MOSER. Logical depth..
Date de publication : 4 septembre 2008 par Martin Delacourt
A venir.
7 juillet 2008 ~ Katsunobu IMAI . On the influence of symmetries to two-dimensional number-conserving cellular automata rules.
Date de publication : 7 juillet 2008 par Gaétan Richard
A number-conserving cellular automaton (NCCA) is a cellular automaton such that all states of cells are represented by integers and the total number of the state of each cell of its configuration is conserved throughout its computing process. It (...)
3 juillet 2008 ~ Francis OGER. Interprétation des pavages par des structures relationnelles.
Date de publication : 3 juillet 2008 par Alexis Ballier
Salle 005.
Nous mettrons en évidence les relations entre les propriétés géométriques des pavages et les propriétés algébriques et logiques de leurs structures relationnelles associées. Nous avons étudié tout d'abord les pavages d'espaces (...)
2 juillet 2008 ~ Francis OGER. Étude des pavages quasi-périodiques associés à des courbes de pliage du plan.
Date de publication : 2 juillet 2008 par Alexis Ballier
Salle 005.
L'objet du présent travail est de montrer que les suites et les courbes de pliage satisfont des propriétés de quasi-périodicité analogues à celles qui ont été mises en évidence pour certaines classes de pavages. Pour cela, on est (...)
10 avril 2008 ~ Jean-Baptiste Rouquier. Automate minorité sur les arbres.
Date de publication : 10 avril 2008 par Alexis Ballier
Le domaine des automates cellulaires voit depuis quelques années un intérêt pour l'étude de l'asynchronisme. En particulier, une classe d'automates 1D et et l'automate "minorité" ont été étudiés par Fatès, Regnault, Schabanel, Thierry. La règle (...)
27 mars 2008 ~ Marion Le Gonidec. Ensembles d’entiers reconnus par des automates dénombrables.
Date de publication : 27 mars 2008 par Alexis Ballier
Les ensembles d'entiers p-reconnaissables (reconnus par automates finis) ont été largement étudiés depuis le début des années 1970. Dans l'optique de généraliser les résultats classiques concernant ces ensembles d'entiers, on s'interesse à des (...)
20 mars 2008 ~ Christiane Bercoff. Génération de mots de contour de tuiles pavant le réseau carré.
Date de publication : 20 mars 2008 par Alexis Ballier
Beauquier-Nivat caractérisent les tuiles, homéomorphes à un disque, qui pavent le plan par translation d'une unique tuile q, par une propriété du mot de contour (mot circulaire défini sur Σ, un alphabet à 4 lettres) ω_q de q : il (...)
6 mars 2008 ~ Florent Becker. Signaux et auto-assemblage.
Date de publication : 6 mars 2008 par Alexis Ballier
Les pavages auto-assemblants constituent un modèle de construction de figures planes qui permet d'utiliser la chimie et en particulier les propriétés de l'ADN pour calculer. Les mécanismes chimiques qui permettent de l'implémenter commencent à (...)
14 février 2008 ~ Stephane Le Roux. Abstraction et formalisation en théorie des jeux.
Date de publication : 14 février 2008 par Alexis Ballier
Les notions de jeu et d'équilibre de Nash sont fondamentales en théorie des jeux. On voudrait que tous les jeux aient des équilibres de Nash, mais ce n'est pas le cas, alors Nash a montré que tous les jeux d'une certaine classe avaient un (...)
10 janvier 2008 ~ Damien REGNAULT. Apparition de la percolation dirigée dans l’analyse des automates cellulaires stochastiques.
Date de publication : 10 janvier 2008 par Alexis Ballier
Historiquement les automates cellulaires ont été étudiés évoluant sous une dynamique synchrone. Néanmoins des dynamiques asynchrones sont apparues pour d'un côté modéliser des systèmes réels (modèle d'Ising) ou créer des automates cellulaires (...)
11 décembre 2007 ~ Sylvain Périfel. Interpolation en théorie de Valiant.
Date de publication : 11 décembre 2007 par Alexis Ballier
Nous nous intéresserons à la question suivante : si un polynôme peut être évalué par un algorithme (booléen) en temps polynomial, est-il alors calculable par un circuit arithmétique de taille polynomiale ? En d'autres termes, peut-on tout faire (...)
6 décembre 2007 ~ Vincent Bernardi. Lois de conservation sur automates cellulaires.
Date de publication : 6 décembre 2007 par Alexis Ballier
Pré-soutenance de thèse
29 novembre 2007 ~ Thomas Fernique. Reconnaissance de plan et fractions continues.
Date de publication : 29 novembre 2007 par Alexis Ballier
Une manière de stocker de manière économe un gros objet géométrique discret (images 3D acquises expérimentalement etc.) est de le vectoriser. Une façon de procéder est de le décomposer en plans discrets (approximations de plans euclidiens). Pour (...)
22 novembre 2007 ~ Jérémie Chalopin. Election and Rendez-vous in a Babel world.
Date de publication : 22 novembre 2007 par Alexis Ballier
Consider an intercontinental highway network linking different cities in different countries. In each city, the directions to the other cities are written in the language that is locally spoken. Consider now a set of different drivers coming (...)
15 novembre 2007 ~ . Pas de séminaire.
Date de publication : 15 novembre 2007 par Alexis Ballier
FRAC
8 novembre 2007 ~ Gaétan Richard. Collisions and their Catenations : Ultimately Periodic Tilings of the Plane.
Date de publication : 8 novembre 2007 par Alexis Ballier
Motivated by the study of cellular automata algorithmics and dynamics, we investigate an extension of ultimately periodic words to two-dimensional infinite words : collisions. A natural composition operation on tilings leads to a catenation (...)
1er novembre 2007 ~ . Pas de séminaire.
Date de publication : 1er novembre 2007 par Alexis Ballier
Férié
26 octobre 2007 ~ Victor Poupet. Des réels calculables sur des courbes co-récursivement énumérables.
Date de publication : 26 octobre 2007 par Alexis Ballier
On dit d'un nombre réel qu'il est calculable s'il est possible d'en calculer des approximations aussi fines que l'on veut. Un point du plan est calculable si ses deux coordonnées le sont.
On cherche alors à caractériser des familles d'ensembles (...)
25 octobre 2007 ~ . Pas de séminaire.
Date de publication : 25 octobre 2007 par Alexis Ballier
Journée de rentrée de l'école doctorale.
19 octobre 2007 ~ Alexey Chernov. Useless cryptography.
Date de publication : 19 octobre 2007 par Alexis Ballier
Attention : Exceptionnellement ce séminaire a lieu en salle 004
Un programme qui produit B à partir de A mais inutilisable sans A
Cet exposé est basé sur un travail non publié de Andrej Muchnik, annoncé en 2003.
Andrej A. Muchnik Cryptography (...)
18 octobre 2007 ~ Peter Gacs, Boston university. The angel game.
Date de publication : 18 octobre 2007 par Alexis Ballier
A problem concerning a combinatorial game, called the angel-devil game,has been circulating among mathematicians for at least 30 years. Then last summer, at least four independent solutions appeared, one of them (the most complex and weakest) by (...)
12 octobre 2007 ~ Benoit Masson. Nilpotence des automates de sable .
Date de publication : 12 octobre 2007 par Alexis Ballier
Dans cet exposé nous étudierons la nilpotence des automates de sable. Après avoir vu que la définition classique n'avait pas de sens, nous définirons une nouvelle notion plus souple : un automate est nilpotent s'il rapproche chaque configuration (...)
24 septembre 2007 ~ Yuri Pritykin. Finite transductions of almost periodic sequences.
Date de publication : 24 septembre 2007 par Alexis Ballier
We prove that finite transduction of an almost periodic sequence is almost periodic up to a prefix, and then deal with an effective version of this result. We also discuss connections of finite automata and monadic logics on infinite (...)
11 septembre 2007 ~ . Réunion d’équipe.
Date de publication : 11 septembre 2007 par Alexis Ballier
Ordre du jour :
accueil des nouveaux
organisation
demandes de moyens
divers (faire un mail à Bruno Durand)