Publications
Emmanuel Jeandel
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.
Translationlike 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 translationlike on G', provided H is finitely presented.
In particular: * If G_{1} and G_{2} are f.g. infinite groups,
then G_{1}×G_{2} 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. pgroup admits a
weakly aperiodic SFT.

[4]

Emmanuel Jeandel.
Strong shift equivalence as a category notion.
preprint.
[ Download ]
[Show abstract]
In this paper, we present a completely radical way to investigate the main problem of symbolic dynamics, the conjugacy problem, by proving that this problem actually relates to a natural question in category theory regarding the theory of traced bialgebras. As a consequence of this theory, we obtain a systematic way of obtaining new invariants for the conjugacy problem by looking at existing bialgebras in the literature.
Book Chapters

[1]

Emmanuel Jeandel and Pascal Vanier.
Substitution and Tiling Dynamics: Introduction to Selfinducing
Structures, chapter The Undecidability of the Domino Problem, pages
293356.
Number 2273 in Lecture Notes in Mathematics. Springer, 2020.
[ DOI ]

[2]

Nathalie Aubrun, Sebastian Barbieri, and Emmanuel Jeandel.
Sequences, Groups, and Number Theory, chapter About the Domino
Problem for Subshifts on Groups, pages 331389.
Trends in Mathematics. Springer, 2018.
[ DOI ]
Papers

[1]

Emmanuel Jeandel and Michael Rao.
An aperiodic set of 11 Wang tiles.
Advances in Combinatorics, 1:137, January 2021.
[ DOI 
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.

[2]

Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart.
Completeness of Graphical Languages for Mixed States Quantum
Mechanics.
ACM Transactions on Quantum Computing, 2(4):128, 2021.
[ DOI ]
[Show abstract]
There exist several graphical languages for quantum information processing, like quantum circuits, ZXcalculus, ZWcalculus, etc. Each of these languages forms a †symmetric monoidal category (†SMC) and comes with an interpretation functor to the †SMC of finite dimensional Hilbert spaces. In 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 how to extend these languages beyond pure quantum mechanics, in order to reason about 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, an 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 Clifford+T quantum mechanics, as the category does not have enough isometries.

[3]

Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon
Perdrix, Marc Porcheron, and Margarita Veshchezerova.
Qualifying quantum approaches for hard industrial optimization
problems. A case study in the ﬁeld of smartcharging of electric vehicles.
EPJ Quantum Technology, 8(12):127, 2021.
[ DOI ]
[Show abstract]
In order to qualify quantum algorithms for industrial NPHard problems, comparing them to available polynomial approximate classical algorithms and not only to exact exponential ones is necessary. This is a great challenge as, in many cases, bounds on the reachable approximation ratios exist according to some highlytrusted conjectures of Complexity Theory. An interesting setup for such qualification is thus to focus on particular instances of these problems known to be “less difficult” than the worstcase ones and for which the above bounds can be outperformed: quantum algorithms should perform at least as well as the conventional approximate ones on these instances, up to very large sizes. We present a case study of such a protocol for two industrial problems drawn from the strongly developing field of smartcharging of electric vehicles. Tailored implementations of the Quantum Approximate Optimization Algorithm (QAOA) have been developed for both problems, and tested numerically with classical resources either by emulation of Pasqal’s Rydberg atom based quantum device or using Atos Quantum Learning Machine. In both cases, quantum algorithms exhibit the same approximation ratios as conventional approximation algorithms or improve them. These are very encouraging results, although still for instances of limited size as allowed by studies on classical computing resources. The next step will be to confirm them on larger instances, on actual devices, and for more complex versions of the problems addressed.

[4]

Emmanuel Jeandel, Etienne Moutot, and Pascal Vanier.
Slopes of multidimensional subshifts.
Theory of Computing Systems, 64:3561, 2020.
[ 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 _{S}igma_{1}^{0} sets of
noncommensurable ℤ^{2} vectors are exactly the sets of
slopes of 2D SFTs and that Σ_{2}^{0} sets of
noncommensurable 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.

[5]

Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart.
Completeness of the ZXCalculus.
Logical Methods in Computer Science, 16(2):11:172, 2020.
[ DOI 
Download ]
[Show abstract]
The ZXCalculus is a graphical language for diagrammatic reasoning in quantum mechanics and quantum information theory. It comes equipped with an equational presentation. We focus here on a very important property of the language: completeness, which roughly ensures the equational theory captures all of quantum mechanics. We first improve on the knowntobecomplete presentation for the socalled Clifford fragment of the language — a restriction that is not universal — by adding some axioms. Thanks to a system of backandforth translation between the ZXCalculus and a thirdparty complete graphical language, we prove that the provided axiomatisation is complete for the first approximately universal fragment of the language, namely Clifford+T. We then prove that the expressive power of this presentation, though aimed at achieving completeness for the aforementioned restriction, extends beyond Clifford+T, to a class of diagrams that we call linear with Clifford+T constants. We use another version of the thirdparty language — and an adapted system of backandforth translation — to complete the language for the ZXCalculus as a whole, that is, with no restriction. We briefly discuss the added axioms, and finally, we provide a complete axiomatisation for an altered version of the language which involves an additional generator, making the presentation simpler.

[6]

Emmanuel Jeandel and Pascal Vanier.
Characterizations of periods of multidimensional shifts.
Ergodic Theory and Dynamical Systems, 35(2):431460, April
2015.
[ DOI 
Preprint ]
[Show abstract]
We show that the sets of periods of multidimensional
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.

[7]

Emmanuel Jeandel and Pascal Vanier.
Hardness of conjugacy, embedding and factorization of
multidimensional subshifts.
Journal of Computer and System Sciences, 81(8):16481664,
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 Σ_{3}^{0}complete for
sofic and effective subshifts and that they are Σ_{1}^{0}complete
for SFTs, except for factorization which is also
Σ_{3}^{0}complete.

[8]

Emmanuel Jeandel and Guillaume Theyssier.
Subshifts as models for MSO logic.
Information and Computation, 225:115, 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.

[9]

Emmanuel Jeandel and Pascal Vanier.
Turing degrees of multidimensional SFTs.
Theoretical Computer Science, 505:8192, 2013.
[ DOI 
Preprint ]
[Show abstract]
In this paper we are interested in computability aspects
of subshifts and in particular Turing degrees of 2dimensional 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 XU 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 nonrecursive members, some of its members always have different but comparable degrees. This gives a fairly complete study of Turing degrees of SFTs.

[10]

Emmanuel Jeandel.
The periodic domino problem revisited.
Theoretical Computer Science, 411:40104016, 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.

[11]

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):3953, February 2008.
[ DOI 
Research Report ]
[Show abstract]
Dimitri Grigoriev has shown that for any family of N vectors
in the ddimensional linear space E=(F_{2})^{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.

[12]

Emmanuel Jeandel and Nicolas Ollinger.
Playing with Conway's Problem.
Theoretical Computer Science, 409:557564, 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 corecursively 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.

[13]

Emmanuel Jeandel.
Topological Automata.
Theory of Computing Systems, 40(4):397407, 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 nondeterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.

[14]

Harm Derksen, Emmanuel Jeandel, and Pascal Koiran.
Quantum automata and algebraic groups.
Journal of Symbolic Computation, 39(34):357371,
MarchApril 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.

[15]

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier.
Decidable and Undecidable Problems about Quantum Automata.
SIAM Journal on Computing, 34(6):14641473, 2005.
[ DOI 
Research Report ]
[Show abstract]
We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and nonstrict thresholds both lead to undecidable problems.
Proceedings

[1]

Emmanuel Hainry, Emmanuel Jeandel, Romain Péchoux, and Olivier Zeyen.
ComplexityParser: an automatic tool for certifying polytime
complexity of Java programs.
In International Colloquium on Theoretical Aspects of Computing
(ICTAC), volume 12819, 2021.

[2]

Titouan Carette and Emmanuel Jeandel.
A recipe for Quantum Graphical Languages.
In Proceedings of the 47th International Colloquium on Automata,
Languages, and Programming (ICALP), volume 168, pages 118:1118:17, 2020.
[ DOI ]
[Show abstract]
Different graphical calculi have been proposed to represent quantum computation. First the ZXcalculus [Coecke and Duncan, 2011], followed by the ZWcalculus [Hadzihasanovic, 2015] and then the ZHcalculus [Backens and Kissinger, 2018]. We can wonder if new ZXlike calculi will continue to be proposed forever. This article answers negatively. All those language share a common core structure we call Z^{*}algebras. We classify Z^{*}algebras up to isomorphism in two dimensional Hilbert spaces and show that they are all variations of the aforementioned calculi. We do the same for linear relations and show that the calculus of [Bonchi et al., 2017] is essentially the unique one.

[3]

Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart.
A Generic Normal Form for ZXDiagrams and Application to the
Rational Angle Completeness.
In ACM/IEEE Symposium on Logic in Computer Science (LICS),
2019.
[ DOI 
Download ]
[Show abstract]
Recent completeness results on the ZXCalculus used a
thirdparty language, namely the ZWCalculus. As a
consequence, these proofs are elegant, but sadly
nonconstructive. We address this issue in the
following. To do so, we first describe a generic
normal form for ZXdiagrams 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 ZXCalculus –
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.

[4]

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:140: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.

[5]

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 (twodimensional) 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.

[6]

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, ZXCalculus, ZWCalculus, 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.

[7]

Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart.
A Complete Axiomatisation of the ZXCalculus for
Clifford+T Quantum Mechanics.
In ACM/IEEE Symposium on Logic in Computer Science (LICS),
pages 559568, 2018.
[ DOI 
Preprint ]
[Show abstract]
We introduce the first complete and approximatively universal diagrammatic language for quantum mechanics. We make the ZXCalculus, a diagrammatic language introduced by Coecke and Duncan, complete for the socalled Clifford+T quantum mechanics by adding four new axioms to the language. The completeness of the ZXCalculus 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 ZXCalculus using the recently studied ZWCalculus, a calculus dealing with integer matrices. We also prove that the Clifford+T fragment of the ZXCalculus represents exactly all the matrices over some finite dimensional extension of the ring of dyadic rationals.

[8]

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 569578, 2018.
[ DOI 
Preprint ]
[Show abstract]
The ZXCalculus 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 socalled 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 ZXcalculus. In particular all the axioms of the ZXcalculus 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 ZXcalculus for pure quantum mechanics than the one recently introduced by Ng&Wang.

[9]

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.

[10]

Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart.
YCalculus: A language for real Matrices derived from the
ZXCalculus.
In International Conference on Quantum Physics and Logic (QPL),
number 266 in Electronic Proceedings in Theoretical Computer Science, pages
2357, 2017.
[ DOI ]
[Show abstract]
We introduce a ZXlike 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 ZXCalculus, 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 ZXdiagram, and prove that a restriction of our language is complete if the equivalent restriction of the ZXcalculus is complete.

[11]

Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart, and Quanlong Wang.
ZXCalculus: 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 ZXCalculus 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 ZXcalculus, 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 ZXCalculus, implying in particular the incompleteness of the language for the socalled Clifford+T quantum mechanics. We end up with a new axiomatisation of an extended ZXCalculus, including an axiom schema for the cyclotomic supplementarity.

[12]

Emmanuel Jeandel.
Computability in Symbolic Dynamics.
In Computability in Europe (CiE), volume 9709 of Lecture
Notes in Computer Science, pages 124131, 2016.
Invited talk.
[ DOI ]
[Show abstract]
We give an overview of the interplay between computability and symbolic dynamics.

[13]

Emmanuel Jeandel.
Computability of the entropy of onetape Turing machines.
In Symposium on Theoretical Aspects of Computer Science
(STACS), volume 25, pages 421432, 2014.
[ DOI ]
[Show abstract]
We prove that the maximum speed and the entropy of a onetape 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 onetape Turing machines, as it is not true anymore for twotape Turing machines by the results of Blondel et al., and uses the approach of crossing sequences introduced by Hennie.

[14]

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 490501, 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 Σ^{0}_{3}complete and the conjugacy problem Σ^{0}_{1}complete in the arithmetical hierarchy.

[15]

Emmanuel Jeandel and Nicolas Rolin.
Fixed Parameter Undecidability for Wang Tilesets.
In Symposium on Cellular Automata (JAC), pages 6985, 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.

[16]

Emmanuel Jeandel.
On Immortal configurations in Turing machines.
In Computability in Europe (CiE), volume 7318 of Lecture
Notes in Computer Science, pages 334343, 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.

[17]

Emmanuel Jeandel and Pascal Vanier.
Π_{1}^{0} sets and tilings.
In Theory and Applications of Models of Computation (TAMC),
volume 6648 of Lecture Notes in Computer Science, pages 230239, 2011.
[ DOI 
Preprint ]
[Show abstract]
In this paper, we prove that given any Π_{1}^{0} subset
P of {0,1}^{ℕ} there is a tileset τ with a set of configurations
C such that P ×ℤ^{2} is recursively homeomorphic to CU 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.

[18]

Emmanuel Jeandel and Pascal Vanier.
Slopes of tilings.
In Symposium on Cellular Automata (JAC), pages 145155, 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.

[19]

Alexis Ballier and Emmanuel Jeandel.
Computing (or not) quasiperiodicity functions of tilings.
In Symposium on Cellular Automata (JAC), pages 5464, 2010.
[ Download ]
[Show abstract]
We know that tilesets that can tile the plane always admit a quasiperiodic
tiling, yet they hold many uncomputable
properties.
The quasiperiodicity function is one way to measure the regularity of a
quasiperiodic tiling.
We prove that the tilings by a tileset that admits only quasiperiodic tilings
have a recursively (and uniformly) bounded quasiperiodicity function.
This corrects an error from [CervelleDurand2004] which stated the
contrary.
Instead we construct a tileset for which any quasiperiodic tiling has a
quasiperiodicity function that cannot be recursively bounded.
We provide such a construction for 1dimensional effective subshifts and
obtain as a corollary the result for tilings of the plane via recent
links between these objects.

[20]

Emmanuel Jeandel and Pascal Vanier.
Periodicity in Tilings.
In Developments in Language Theory (DLT), volume 6224 of
Lecture Notes in Computer Science, pages 243254. 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.

[21]

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 480491.
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 errorfree 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.

[22]

Emmanuel Jeandel and Guillaume Theyssier.
Subshifts, Languages and Logic.
In Developments in Language Theory (DLT), volume 5583 of
Lecture Notes in Computer Science, pages 288299. 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).

[23]

Alexis Ballier and Emmanuel Jeandel.
Tilings and Model Theory.
In Symposium on Cellular Automata Journées Automates
Cellulaires (JAC), pages 2939, 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.

[24]

Alexis Ballier, Bruno Durand, and Emmanuel Jeandel.
Structural Aspects of Tilings.
In Symposium on Theoretical Aspects of Computer Science
(STACS), pages 6172. Schloss Dagstuhl  LeibnizZentrum fuer Informatik,
Germany, 2008.
[ DOI 
Download ]
[Show abstract]
In this paper, we study the structure of
the set of tilings produced by any given tileset.
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 CantorBendixson rank.
Our first main result is that a tileset 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.

[25]

Emmanuel Jeandel.
Topological Automata.
In Symposium on Theoretical Aspects of Computer Science
(STACS), volume 3404 of Lecture Notes in Computer Science, pages
389398. 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 nondeterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.

[26]

Emmanuel Jeandel.
Universality in Quantum Computation.
In International Colloquium on Automata, Languages and
Programming (ICALP), volume 3142 of Lecture Notes in Computer Science,
pages 793804. 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 (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."
(Published) Posters

[1]

Frederic Grosshans, Ruben Y. Cohen, Emmanuel Jeandel, and Simon Perdrix.
Entanglement Distribution Across a Quantum PeertoPeer
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 onetape Turing Machines.
Technical Report hal00785232, 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 RR200605, LIP, ENS Lyon, January 2006.
[ Download ]
[Show abstract]
Dimitri Grigoriev has shown that for any family of N vectors
in the ddimensional linear space E=(F_{2}^{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.
Technical Report ccsd00013788, 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 corecursively 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 RR200339, 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 RR200324, 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 nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and nonstrict thresholds both lead to undecidable problems.

[6]

Emmanuel Jeandel.
Evaluation rapide de fonctions hypergeometriques.
Technical Report RT0242, INRIA  ENS Lyon, 2000.
[ Download ]
[Show abstract]
Nous presentons ici l'implantation des fonctions
hypergeometriques dans la bibliotheque MPFR. Ceci a ete effectue a l'aide de la methode Binary Splitting. Un algorithme generique a donc ete cree, qui a permis l'amelioration 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 methode similaire pour les autres fonctions. Les experiences montrent que la methode est plus efficace que celles employees precedemment 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 sousgroupe
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.
Indecidabilite sur les automates quantiques.
Master's thesis, ENS Lyon, 2002.
[ Download ]
[Show abstract]
Apres avoir introduit les automates quantiques MO et MM, nous
discuterons ici des principaux problemes de decision qui se posent.
Alors que tous les problemes naturels que l'on peut se poser sont
indecidables pour le modele stochastique, l'existence d'un mot accepte avec
seuil strict par un automate quantique MO est montre decidable, par une methode
mathematique basee sur quelques proprietes
remarquables des groupes de Lie. Tous les autres problemes sont montres
indecidables par reduction a la correspondance de Post, en utilisant un
encodage des mots par des matrices unitaires. Nous decrirons enfin comment
les differents modeles rencontres se simulent entre eux.
Back (Main page)