Preprints

[1]
Pierre Guillon and Emmanuel Jeandel. Infinite Communication Complexity. preprint.
Download ] [Show abstract]
Suppose that Alice and Bob are given each an infinite string, and they want to decide whether their two strings are in a given relation. How much communication do they need? How can communication be even defined and measured for infinite strings? In this article, we propose a formalism for a notion of infinite communication complexity, prove that it satisfies some natural properties and coincides, for relevant applications, with the classical notion of amortized communication complexity. Moreover, an application is given for tackling some conjecture about tilings and multidimensional sofic shifts.
[2]
Emmanuel Jeandel. Some Notes about Subshifts on Groups. preprint.
Download ] [Show abstract]
In this note we prove the following results: • If a finitely presented group G admits a strongly aperiodic SFT, then G has decidable word problem. • For a large class of group G, Z × G admits a strongly aperiodic SFT. In particular, this is true for the free group with 2 generators, Thompson's groups T and V , PSL2(Z) and any f.g. group of rational matrices which is bounded.
[3]
Emmanuel Jeandel and Michael Rao. An aperiodic set of 11 Wang tiles. preprint.
Download ] [Show abstract]
A new aperiodic tile set containing 11 Wang tiles on 4 colors is presented. This tile set is minimal in the sense that no Wang set with less than 11 tiles is aperiodic, and no Wang set with less than 4 colors is aperiodic.
[4]
Emmanuel Jeandel. Translation-like Actions and Aperiodic Subshifts on Groups. preprint.
Download ] [Show abstract]
It is well known that if G admits a f.g. subgroup H with a weakly aperiodic SFT (resp. an undecidable domino problem), then G itself has a weakly aperiodic SFT (resp. an undecidable domino problem). We prove that we can replace the property `H is a subgroup of G' by ` H acts translation-like on G', provided H is finitely presented. In particular: * If G1 and G2 are f.g. infinite groups, then G1×G2 has a weakly aperiodic SFT (and actually an undecidable domino problem). In particular the Grigorchuk group has an undecidable domino problem. * Every infinite f.g. p-group admits a weakly aperiodic SFT.

Book Chapters

[1]
Nathalie Aubrun, Sebastian Barbieri, and Emmanuel Jeandel. Sequences, Groups, and Number Theory, chapter About the Domino Problem for Subshifts on Groups, pages 331--389. Trends in Mathematics. Springer, 2018.
DOI ]
[2]
Emmanuel Jeandel and Pascal Vanier. Tiling Dynamical System, chapter The Undecidability of the Domino Problem. To appear.

Papers

[1]
Emmanuel Jeandel, Etienne Moutot, and Pascal Vanier. Slopes of multi-dimensional subshifts. Theory of Computing Systems, 2019.
DOI | Download ] [Show abstract]
In this paper we study the directions of periodicity of multidimensional subshifts of finite type (SFTs) and of multidimensional effectively closed and sofic subshifts. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope representing that direction. In this paper, we prove that Sigma10 sets of non-commensurable ℤ2 vectors are exactly the sets of slopes of 2D SFTs and that Σ20 sets of non-commensurable vectors are exactly the sets of slopes of 3D SFTs, and exactly the sets of slopes of 2D and 3D sofic and effectively closed subshifts.
[2]
Emmanuel Jeandel and Pascal Vanier. Characterizations of periods of multidimensional shifts. Ergodic Theory and Dynamical Systems, 35(2):431--460, April 2015.
DOI | Preprint ] [Show abstract]
We show that the sets of periods of multi-dimensional shifts of finite type are precisely the sets of integers of the complexity class NP. We also show that the functions counting their number are the functions of #P. We also give characterizations of some other notions of periodicity in terms of space complexity. We finish the paper by giving some characterizations for sofic and effective subshifts.
[3]
Emmanuel Jeandel and Pascal Vanier. Hardness of conjugacy, embedding and factorization of multidimensional subshifts. Journal of Computer and System Sciences, 81(8):1648--1664, 2015.
DOI | Preprint ] [Show abstract]
Subshifts of finite type are sets of colorings of the plane defined by local constraints. They can be seen as a discretization of continuous dynamical systems. We investigate here the hardness of deciding factorization, conjugacy and embedding of subshifts in dimensions d>1 for subshifts of finite type and sofic shifts and in dimensions d>0 for effective shifts. In particular, we prove that the conjugacy, factorization and embedding problems are Σ30-complete for sofic and effective subshifts and that they are Σ10-complete for SFTs, except for factorization which is also Σ30-complete.
[4]
Emmanuel Jeandel and Guillaume Theyssier. Subshifts as models for MSO logic. Information and Computation, 225:1--15, 2013.
DOI | Preprint ] [Show abstract]
We study the Monadic Second Order (MSO) Hierarchy over colorings of the discrete plane, and draw links between classes of formula and classes of subshifts. We give a characterization of existential MSO in terms of projections of tilings, and of universal sentences in terms of combinations of “pattern counting” subshifts. Conversely, we characterize logic fragments corresponding to various classes of subshifts (subshifts of finite type, sofic subshifts, all subshifts). Finally, we show by a separation result how the situation here is different from the case of tiling pictures studied earlier by Giammarresi et al.
[5]
Emmanuel Jeandel and Pascal Vanier. Turing degrees of multidimensional SFTs. Theoretical Computer Science, 505:81--92, 2013.
DOI | Preprint ] [Show abstract]
In this paper we are interested in computability aspects of subshifts and in particular Turing degrees of 2-dimensional SFTs (i.e. tilings). To be more precise, we prove that given any subset P of {0,1} there is a SFT X such that P×ℤ2 is recursively homeomorphic to X-U where U is a computable set of points. As a consequence, if P contains a recursive member, P and X have the exact same set of Turing degrees. On the other hand, we prove that if X contains only non-recursive members, some of its members always have different but comparable degrees. This gives a fairly complete study of Turing degrees of SFTs.
[6]
Emmanuel Jeandel. The periodic domino problem revisited. Theoretical Computer Science, 411:4010--4016, 2010.
DOI | Preprint ] [Show abstract]
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.
[7]
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.
DOI | Research Report ] [Show abstract]
Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E=(F2)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.
[8]
Emmanuel Jeandel and Nicolas Ollinger. Playing with Conway's Problem. Theoretical Computer Science, 409:557--564, 2008.
DOI | Research Report ] [Show abstract]
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.
[9]
Emmanuel Jeandel. Topological Automata. Theory of Computing Systems, 40(4):397--407, June 2007.
DOI | Preprint ] [Show abstract]
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]
Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Journal of Symbolic Computation, 39(3--4):357--371, March--April 2005.
DOI | Research Report ] [Show abstract]
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.
[11]
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.
DOI | Research Report ] [Show abstract]
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.

Proceedings

[1]
Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Generic Normal Form for ZX-Diagrams and Application to the Rational Angle Completeness. In ACM/IEEE Symposium on Logic in Computer Science (LICS), 2019. arXiv:1805.05296.
DOI | Download ] [Show abstract]
Recent completeness results on the ZX-Calculus used a third-party language, namely the ZW-Calculus. As a consequence, these proofs are elegant, but sadly non-constructive. We address this issue in the following. To do so, we first describe a generic normal form for ZX-diagrams in any fragment that contains Clifford+T quantum mechanics. We give sufficient conditions for an axiomatisation to be complete, and an algorithm to reach the normal form. Finally, we apply these results to the Clifford+T fragment and the general ZX-Calculus – for which we already know the completeness–, but also for any fragment of rational angles: we show that the axiomatisation for Clifford+T is also complete for any fragment of dyadic angles, and that a simple new rule (called cancellation) is necessary and sufficient otherwise.
[2]
Emmanuel Jeandel and Pascal Vanier. A characterization of subshifts with a computable language. In Symposium on Theoretical Aspects of Computer Science (STACS), volume 126, pages 40:1--40:16, 2019.
DOI ] [Show abstract]
Subshifts are sets of colorings of ℤd by a finite alphabet that avoid some family of forbidden patterns. We investigate here some analogies with group theory that were first noticed by the first author. In particular we prove several theorems on subshifts inspired by Higman's embedding theorems of group theory, among which, the fact that subshifts with a computable language can be obtained as restrictions of minimal subshifts of finite type.
[3]
Pierre Guillon, Emmanuel Jeandel, Jarkko Kari, and Pascal Vanier. Undecidable word problem in subshift automorphism groups. In International Computer Science Symposium in Russia (CSR), volume 11532 of Lecture Notes in Computer Science. Springer, 2019.
DOI | Download ] [Show abstract]
This article studies the complexity of the word problem in groups of automorphisms (or reversible cellular automata) of subshifts. We show in particular that for any computably enumerable Turing degree, there exists a (two-dimensional) subshift of finite type whose automorphism group contains a subgroup whose word problem has exactly this degree. In particular, there are such subshifts of finite type where this problem is uncomputable. This remains true in a large setting of subshifts over groups.
[4]
Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of Graphical Languages for Mixed States Quantum Mechanics. In International Colloquium on Automata, Languages and Programming (ICALP), 2019.
Download ] [Show abstract]
There exist several graphical languages for quantum information processing, like quantum circuits, ZX-Calculus, ZW-Calculus, etc. Each of these languages forms a †-symmetric monoidal category (†-SMC) and comes with an interpretation functor to the †-SMC of (finite dimension) Hilbert spaces. In the recent years, one of the main achievements of the categorical approach to quantum mechanics has been to provide several equational theories for most of these graphical languages, making them complete for various fragments of pure quantum mechanics. We address the question of the extension of these languages beyond pure quantum mechanics, in order to reason on mixed states and general quantum operations, i.e. completely positive maps. Intuitively, such an extension relies on the axiomatisation of a discard map which allows one to get rid of a quantum system, operation which is not allowed in pure quantum mechanics. We introduce a new construction, the discard construction, which transforms any †-symmetric monoidal category into a symmetric monoidal category equipped with a discard map. Roughly speaking this construction consists in making any isometry causal. Using this construction we provide an extension for several graphical languages that we prove to be complete for general quantum operations. However this construction fails for some fringe cases like the Clifford+T quantum mechanics, as the category does not have enough isometries.
[5]
Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Complete Axiomatisation of the ZX-Calculus for Clifford+T Quantum Mechanics. In ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 559--568, 2018.
DOI | Preprint ] [Show abstract]
We introduce the first complete and approximatively universal diagrammatic language for quantum mechanics. We make the ZX-Calculus, a diagrammatic language introduced by Coecke and Duncan, complete for the so-called Clifford+T quantum mechanics by adding four new axioms to the language. The completeness of the ZX-Calculus for Clifford+T quantum mechanics was one of the main open questions in categorical quantum mechanics. We prove the completeness of the Clifford+T fragment of the ZX-Calculus using the recently studied ZW-Calculus, a calculus dealing with integer matrices. We also prove that the Clifford+T fragment of the ZX-Calculus represents exactly all the matrices over some finite dimensional extension of the ring of dyadic rationals.
[6]
Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Diagrammatic Reasoning beyond Clifford+T Quantum Mechanics. In ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 569--578, 2018.
DOI | Preprint ] [Show abstract]
The ZX-Calculus is a graphical language for quantum mechanics. An axiomatisation has recently been proven to be complete for an approximatively universal fragment of quantum mechanics, the so-called Clifford+T fragment. We focus here on the expressive power of this axiomatisation beyond Clifford+T Quantum mechanics. We consider the full pure qubit quantum mechanics, and mainly prove two results: (i) First, the axiomatisation for Clifford+T quantum mechanics is also complete for all equations involving some kind of linear diagrams. The linearity of the diagrams reflects the phase group structure, an essential feature of the ZX-calculus. In particular all the axioms of the ZX-calculus are involving linear diagrams. (ii) We also show that the axiomatisation for Clifford+T is not complete in general but can be completed by adding a single (non linear) axiom, providing a simpler axiomatisation of the ZX-calculus for pure quantum mechanics than the one recently introduced by Ng&Wang.
[7]
Emmanuel Jeandel. Enumeration Reducibility in Closure Spaces with Applications to Logic and Algebra. In ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017.
DOI | Preprint ] [Show abstract]
In many instances in first order logic or computable algebra, classical theorems show that many problems are undecidable for general structures, but become decidable if some rigidity is imposed on the structure. For example, the set of theorems in many finitely axiomatisable theories is nonrecursive, but the set of theorems for any finitely axiomatisable complete theory is recursive. Finitely presented groups might have an nonrecursive word problem, but finitely presented simple groups have a recursive word problem. In this article we introduce a topological framework based on closure spaces to show that many of these proofs can be obtained in a similar setting. We will show in particular that these statements can be generalized to cover arbitrary structures, with no finite or recursive presentation/axiomatization. This generalizes in particular work by Kuznetsov and others. Examples from first order logic and symbolic dynamics will be discussed at length.
[8]
Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Y-Calculus: A language for real Matrices derived from the ZX-Calculus. In International Conference on Quantum Physics and Logic (QPL), number 266 in Electronic Proceedings in Theoretical Computer Science, pages 23--57, 2017.
DOI ] [Show abstract]
We introduce a ZX-like diagrammatic language devoted to manipulating real matrices (and rebits), with its own set of axioms. We prove the necessity of some non trivial axioms of these. We show that some restriction of the language is complete. We exhibit two interpretations to and from the ZX-Calculus, thus showing the consistency between the two languages. Finally, we derive from our work a way to extract the real or imaginary part of a ZX-diagram, and prove that a restriction of our language is complete if the equivalent restriction of the ZX-calculus is complete.
[9]
Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart, and Quanlong Wang. ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T quantum mechanics. In Mathematical Foundations of Computer Science (MFCS), number 83 in LIPIcs, pages 11:1 -- 11:13, 2017.
DOI ] [Show abstract]
The ZX-Calculus is a powerful graphical language for quantum mechanics and quantum information processing. The completeness of the language -- i.e. the ability to derive any true equation -- is a crucial question. In the quest of a complete ZX-calculus, supplementarity has been recently proved to be necessary for quantum diagram reasoning (MFCS 2016). Roughly speaking, supplementarity consists in merging two subdiagrams when they are parameterized by antipodal angles. We introduce a generalised supplementarity -- called cyclotomic supplementarity -- which consists in merging n subdiagrams at once, when the n angles divide the circle into equal parts. We show that when n is an odd prime number, the cyclotomic supplementarity cannot be derived, leading to a countable family of new axioms for diagrammatic quantum reasoning. We exhibit another new simple axiom that cannot be derived from the existing rules of the ZX-Calculus, implying in particular the incompleteness of the language for the so-called Clifford+T quantum mechanics. We end up with a new axiomatisation of an extended ZX-Calculus, including an axiom schema for the cyclotomic supplementarity.
[10]
Emmanuel Jeandel. Computability in Symbolic Dynamics. In Computability in Europe (CiE), volume 9709 of Lecture Notes in Computer Science, pages 124--131, 2016. Invited talk.
DOI ] [Show abstract]
We give an overview of the interplay between computability and symbolic dynamics.
[11]
Emmanuel Jeandel. Computability of the entropy of one-tape Turing machines. In Symposium on Theoretical Aspects of Computer Science (STACS), volume 25, pages 421--432, 2014.
DOI ] [Show abstract]
We prove that the maximum speed and the entropy of a one-tape Turing machine are computable, in the sense that we can approximate them to any given precision . This is counterintuitive, as all dynamical properties are usually undecidable for Turing machines. The result is quite specific to one-tape Turing machines, as it is not true anymore for two-tape Turing machines by the results of Blondel et al., and uses the approach of crossing sequences introduced by Hennie.
[12]
Emmanuel Jeandel and Pascal Vanier. Hardness of conjugacy and factorization of multidimensional subshifts of finite type. In Symposium on Theoretical Aspects of Computer Science (STACS), volume 20, pages 490--501, 2013.
DOI | Preprint ] [Show abstract]
We investigate here the hardness of conjugacy and factorization of subshifts of finite type (SFTs) in dimension d>1. In particular, we prove that the factorization problem is Σ03-complete and the conjugacy problem Σ01-complete in the arithmetical hierarchy.
[13]
Emmanuel Jeandel and Nicolas Rolin. Fixed Parameter Undecidability for Wang Tilesets. In Symposium on Cellular Automata (JAC), pages 69--85, 2012.
DOI ] [Show abstract]
Deciding if a given set of Wang tiles admits a tiling of the plane is decidable if the number of Wang tiles (or the number of colors) is bounded, for a trivial reason, as there are only finitely many such tilesets. We prove however that the tiling problem remains undecidable if the difference between the number of tiles and the number of colors is bounded by 43. One of the main new tool is the concept of Wang bars, which are equivalently inflated Wang tiles or thin polyominoes.
[14]
Emmanuel Jeandel. On Immortal configurations in Turing machines. In Computability in Europe (CiE), volume 7318 of Lecture Notes in Computer Science, pages 334--343, 2012.
DOI | Preprint ] [Show abstract]
We investigate the immortality problem for Turing machines and prove that there exists a Turing Machine that is immortal but halts on every recursive configuration. The result is obtained by combining a new proof of Hooper?s theorem [11] with recent results on effective symbolic dynamics.
[15]
Emmanuel Jeandel and Pascal Vanier. Π10 sets and tilings. In Theory and Applications of Models of Computation (TAMC), volume 6648 of Lecture Notes in Computer Science, pages 230--239, 2011.
DOI | Preprint ] [Show abstract]
In this paper, we prove that given any Π10 subset P of {0,1} there is a tileset τ with a set of configurations C such that P ×ℤ2 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.
[16]
Emmanuel Jeandel and Pascal Vanier. Slopes of tilings. In Symposium on Cellular Automata (JAC), pages 145--155, 2010.
Download ] [Show abstract]
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.
[17]
Alexis Ballier and Emmanuel Jeandel. Computing (or not) quasi-periodicity functions of tilings. In Symposium on Cellular Automata (JAC), pages 54--64, 2010.
Download ] [Show abstract]
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.
[18]
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.
DOI | Preprint ] [Show abstract]
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.
[19]
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.
DOI | Preprint ] [Show abstract]
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.
[20]
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.
DOI | Preprint ] [Show abstract]
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).
[21]
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.
Download ] [Show abstract]
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.
[22]
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.
DOI | Download ] [Show abstract]
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.
[23]
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.
DOI | Preprint ] [Show abstract]
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.
[24]
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.
DOI | Preprint ] [Show abstract]
" 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 (SOn, SUn, SLn) is Zariski dense, thus solving the decision problem for the completeness. We also present partial methods for the realisability with ancillas."

(Published) Posters

[1]
Frederic Grosshans, Ruben Y. Cohen, Emmanuel Jeandel, and Simon Perdrix. Entanglement Distribution Across a Quantum Peer-to-Peer Network. In Quantum Information and Measurement (QIM), Optical Society of America Technical Digest, page QT6A.21, 2017.
DOI ]

Research Reports

[1]
Emmanuel Jeandel. Computability of the entropy of one-tape Turing Machines. Technical Report hal-00785232, Universite de Lorraine, 2013.
Download ]
[2]
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.
Download ] [Show abstract]
Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E=(F2d), 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. Technical Report ccsd-00013788, Laboratoire d'informatique Fondamentale de Marseille, 2005.
Download ] [Show abstract]
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]
Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Technical Report RR2003-39, LIP, ENS Lyon, July 2003.
Download ] [Show abstract]
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.
[5]
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.
Download ] [Show abstract]
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.
[6]
Emmanuel Jeandel. valuation rapide de fonctions hypergomtriques. Technical Report RT-0242, INRIA - ENS Lyon, 2000.
Download ] [Show abstract]
Nous prsentons ici l'implantation des fonctions hypergomtriques dans la bibliothque MPFR. Ceci a t effectu l'aide de la mthode Binary Splitting. Un algorithme gnrique a donc t cr, qui a permis l'amlioration 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 mthode similaire pour les autres fonctions. Les expriences montrent que la mthode est plus efficace que celles employes prcdemment dans MPFR.

Diploma Thesis

[1]
Emmanuel Jeandel. Propriétés structurelles et calculatoires des pavages. Habilitation thesis, Université Montpellier 2, 2011.
Download ]
[2]
Emmanuel Jeandel. Techniques algébriques en calcul quantique. PhD thesis, ENS Lyon, 2005.
Download ] [Show abstract]
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. Indcidabilit sur les automates quantiques. Master's thesis, ENS Lyon, 2002.
Download ] [Show abstract]
Aprs avoir introduit les automates quantiques MO et MM, nous discuterons ici des principaux problmes de dcision qui se posent. Alors que tous les problmes naturels que l'on peut se poser sont indcidables pour le modle stochastique, l'existence d'un mot accept avec seuil strict par un automate quantique MO est montr dcidable, par une mthode mathmatique base sur quelques proprits remarquables des groupes de Lie. Tous les autres problmes sont montrs indcidables par rduction la correspondance de Post, en utilisant un encodage des mots par des matrices unitaires. Nous dcrirons enfin comment les diffrents modles rencontrs se simulent entre eux.

Back (Main page)