Proceedings

[1]

Emmanuel Jeandel and Pascal Vanier. Π₁⁰ sets and tilings. In Theory and Applications of Models of Computation (TAMC), volume 6648 of Lecture Notes in Computer Science, pages 230-239, 2011.
[ bib | DOI | Preprint ]

In this paper, we prove that given any Π₁⁰ subset P of {0,1}^ℕ there is a tileset τ with a set of configurations C such that P ×ℤ² is recursively homeomorphic to C-U where U is a computable set of configurations. As a consequence, if P is countable, this tileset has the exact same set of Turing degrees.

[2]

Alexis Ballier, Bruno Durand, and Emmanuel Jeandel. Tilings robust to errors. In Latin American Theoretical Informatics Symposium (LATIN), volume 6034 of Lecture Notes in Computer Science, pages 480-491. Springer, 2010.
[ bib | DOI | Preprint ]

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? We prove that tilesets that produce only periodic tilings are robust to errors; for this proof, we use a hierarchical construction of islands of errors. We also show that another class of tilesets, those that admit countably many tilings is not robust and that there is no computable way to distinguish between these two classes.

[3]

Emmanuel Jeandel and Pascal Vanier. Periodicity in Tilings. In Developments in Language Theory (DLT), volume 6224 of Lecture Notes in Computer Science, pages 243-254. Springer, 2010.
[ bib | DOI | Preprint ]

Tilings and tiling systems are an abstract concept that arise both as a computational model and as a dynamical system. In this paper, we prove an analog of the theorems of Fagin [9] and Selman and Jones [14] by characterizing sets of periods of tiling systems by complexity classes.

[4]

Alexis Ballier and Emmanuel Jeandel. Computing (or not) quasi-periodicity functions of tilings. In Symposium on Cellular Automata (JAC), pages 54-64, 2010.
[ bib | Download ]

We know that tilesets that can tile the plane always admit a quasi-periodic tiling, yet they hold many uncomputable properties. The quasi-periodicity function is one way to measure the regularity of a quasi-periodic tiling. We prove that the tilings by a tileset that admits only quasi-periodic tilings have a recursively (and uniformly) bounded quasi-periodicity function. This corrects an error from [CervelleDurand2004] which stated the contrary. Instead we construct a tileset for which any quasi-periodic tiling has a quasi-periodicity function that cannot be recursively bounded. We provide such a construction for 1-dimensional effective subshifts and obtain as a corollary the result for tilings of the plane via recent links between these objects.

[5]

Emmanuel Jeandel and Pascal Vanier. Slopes of tilings. In Symposium on Cellular Automata (JAC), pages 145-155, 2010.
[ bib | Download ]

We study here slopes of periodicity of tilings. A tiling is of slope θ if it is periodic along direction θ but has no other direction of periodicity.
We characterize in this paper the set of slopes we can achieve with tilings, and prove they coincide with recursively enumerable sets of rationals.

[6]

Emmanuel Jeandel and Guillaume Theyssier. Subshifts, Languages and Logic. In Developments in Language Theory (DLT), volume 5583 of Lecture Notes in Computer Science, pages 288-299. Springer, 2009.
[ bib | DOI | Preprint ]

We study the Monadic Second Order (MSO) Hierarchy over infinite pictures, that is tilings. We give a characterization of existential MSO in terms of tilings and projections of tilings. Conversely, we characterise logic fragments corresponding to various classes of infinite pictures (subshifts of finite type, sofic subshifts).

[7]

Alexis Ballier, Bruno Durand, and Emmanuel Jeandel. Structural Aspects of Tilings. In Symposium on Theoretical Aspects of Computer Science (STACS), pages 61-72. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2008.
[ bib | DOI | Download ]

In this paper, we study the structure of the set of tilings produced by any given tile-set. For better understanding this structure, we address the set of finite patterns that each tiling contains. This set of patterns can be analyzed in two different contexts: the first one is combinatorial and the other topological. These two approaches have independent merits and, once combined, provide somehow surprising results. The particular case where the set of produced tilings is countable is deeply investigated while we prove that the uncountable case may have a completely different structure. We introduce a pattern preorder and also make use of Cantor-Bendixson rank. Our first main result is that a tile-set that produces only periodic tilings produces only a finite number of them. Our second main result exhibits a tiling with exactly one vector of periodicity in the countable case.

[8]

Alexis Ballier and Emmanuel Jeandel. Tilings and Model Theory. In Symposium on Cellular Automata Journées Automates Cellulaires (JAC), pages 29-39, Moscow, 2008. MCCME Publishing House.
[ bib | Download ]

In this paper we emphasize the links between model theory and tilings. More precisely, after giving the definitions of what tilings are, we give a natural way to have an interpretation of the tiling rules in first order logics. This opens the way to map some model theoretical properties onto some properties of sets of tilings, or tilings themselves.

[9]

Emmanuel Jeandel. Topological Automata. In Symposium on Theoretical Aspects of Computer Science (STACS), volume 3404 of Lecture Notes in Computer Science, pages 389-398. Springer, 2005.
[ bib | DOI | Preprint ]

We give here a new, topological, definition of automata that extends previous definitions of probabilistic and quantum automata. We then prove in an unified framework that deterministic or non-deterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.

[10]

Emmanuel Jeandel. Universality in Quantum Computation. In International Colloquium on Automata, Languages and Programming (ICALP), volume 3142 of Lecture Notes in Computer Science, pages 793-804. Springer, 2004.
[ bib | DOI | Preprint ]

" We introduce several new definitions of universality for sets of quantum gates, and prove separation results for these definitions. In particular, we prove that realisability with ancillas is different from the classical notion of completeness. We give a polynomial time algorithm of independent interest which decides if a subgroup of a classical group (SO_n, SU_n, SL_n) is Zariski dense, thus solving the decision problem for the completeness. We also present partial methods for the realisability with ancillas."

Papers

[1]

Emmanuel Jeandel. The periodic domino problem revisited. Theoretical Computer Science, 411:4010-4016, 2010.
[ bib | DOI ]

In this article, we give a new proof of the undecidability of the periodic domino problem. Compared to previous proofs, the main difference is that this one does not start from a proof of the undecidability of the (general) domino problem but only from the existence of an aperiodic tileset.

[2]

Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, and Stéphan Thomassé. Finding a Vector Orthogonal to Roughly Half a Collection of Vectors. Journal of Complexity, 24(1):39-53, February 2008.
[ bib | DOI | Research Report ]

Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E=(F₂)^d, there exists a vector in E which is orthogonal to at least N/3 and at most 2N/3 vectors of the family. We show that the range [N/3,2N/3] can be replaced by the much smaller range [N/2-√N/2,N/2+√N/2] and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.

[3]

Emmanuel Jeandel and Nicolas Ollinger. Playing with Conway's Problem. Theoretical Computer Science, 409:557-564, 2008.
[ bib | DOI | Research Report ]

The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in 1971, whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc 2005, a strong negative answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.

[4]

Emmanuel Jeandel. Topological Automata. Theory of Computing Systems, 40(4):397-407, June 2007.
[ bib | DOI | Preprint ]

We give here a new, topological, definition of automata that extends previous definitions of probabilistic and quantum automata. We then prove in an unified framework that deterministic or non-deterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.

[5]

Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Journal of Symbolic Computation, 39(3-4):357-371, March-April 2005.
[ bib | DOI | Research Report ]

We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest: we give an algorithm which, given a finite number of invertible matrices, computes the Zariski closure of the group generated by these matrices.

[6]

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. Decidable and Undecidable Problems about Quantum Automata. SIAM Journal on Computing, 34(6):1464-1473, 2005.
[ bib | DOI | Research Report ]

We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.

Research Reports

[1]

Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, and Stéphan Thomassé. Finding a Vector Orthogonal to Roughly Half a Collection of Vectors. Technical Report RR2006-05, LIP, ENS Lyon, January 2006.
[ bib | Download ]

Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E=(F₂^d), there exists a vector in E which is orthogonal to at least N/3 and at most 2N/3 vectors of the family. We show that the range [N/3,2N/3] can be replaced by the much smaller range [N/2-√N/2,N/2+√N/2] and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.

[2]

Emmanuel Jeandel and Nicolas Ollinger. Playing with Conway's Problem. Technical Report ccsd-00013788, Laboratoire d'informatique Fondamentale de Marseille, 2005.
[ bib | Download ]

The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in 1971, whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc 2005, a strong negative answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.

[3]

Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Technical Report RR2003-39, LIP, ENS Lyon, July 2003.
[ bib | Download ]

We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest: we give an algorithm which, given a finite number of invertible matrices, computes the Zariski closure of the group generated by these matrices.

[4]

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. Decidable and undecidable problems about quantum automata. Technical Report RR2003-24, LIP, ENS Lyon, April 2003.
[ bib | Download ]

We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.

[5]

Emmanuel Jeandel. Évaluation rapide de fonctions hypergéométriques. Technical Report RT-0242, INRIA - ENS Lyon, 2000.
[ bib | Download ]

Nous présentons ici l'implantation des fonctions hypergéométriques dans la bibliothèque MPFR. Ceci a été effectué à l'aide de la méthode Binary Splitting. Un algorithme générique a donc été créé, qui a permis l'amélioration de l'exponentielle, de certaines constantes, et l'implantation du sinus et du cosinus. Nous exposons l'algorithme pour le cas rationnel, puis nous montrons comment ce cas particulier permet d'obtenir l'exponentielle. Nous utilisons ensuite une méthode similaire pour les autres fonctions. Les expériences montrent que la méthode est plus efficace que celles employées précédemment dans MPFR.

Diploma Thesis

[1]

Emmanuel Jeandel. Propriétés structurelles et calculatoires des pavages. Habilitation thesis, Université Montpellier 2, 2011.
[ bib | Download ]

[2]

Emmanuel Jeandel. Techniques algébriques en calcul quantique. PhD thesis, ENS Lyon, 2005.
[ bib | Download ]

Le principal problème étudié est le calcul de l'adhérence de Zariski de groupes algébriques, et leurs applications en calcul quantique. On donne ici un algorithme en temps polynomial qui décide si un sous-groupe finiment engendré d'un groupe reductif est dense dans ce groupe. On donne également un algorithme qui calcule précisément l'adhérence d'un groupe. Ces résultats sont utilisés afin de résoudre plusieurs problèmes en calcul quantique, en particulier liés aux circuits quantiques. Ainsi divers algorithmes qui décident si des jeux de portes sont universels, ou qui permettent de séparer les différentes notions d'universalité, sont donnés. Nous nous intéressons aussi ici aux automates finis. Nous introduisons ici un nouvel modèle, les automates topologiques, qui permet de généraliser les modèles existants. Nous montrons ainsi, dans un contexte unifié, que tous les modèles d'automates finis classiques, quantiques ou probabilistes ne reconnaissent que des langages rationnels par seuil isolé.

[3]

Emmanuel Jeandel. Indécidabilité sur les automates quantiques. Master's thesis, ENS Lyon, 2002.
[ bib | Download ]

Après avoir introduit les automates quantiques MO et MM, nous discuterons ici des principaux problèmes de décision qui se posent. Alors que tous les problèmes naturels que l'on peut se poser sont indécidables pour le modèle stochastique, l'existence d'un mot accepté avec seuil strict par un automate quantique MO est montré décidable, par une méthode mathématique basée sur quelques propriétés remarquables des groupes de Lie. Tous les autres problèmes sont montrés indécidables par réduction à la correspondance de Post, en utilisant un encodage des mots par des matrices unitaires. Nous décrirons enfin comment les différents modèles rencontrés se simulent entre eux.